The nonnegative Q−matrix completion problem

Abstract

In this paper, the nonnegative $Q$-matrix completion problem is studied. A real $n\times n$ matrix is a $Q$-matrix if for $k\in \{1,\ldots, n\}$, the sum of all $k \times k$ principal minors is positive. A digraph $D$ is said to have nonnegative $Q$-completion if every partial nonnegative $Q$-matrix specifying $D$ can be completed to a nonnegative $Q$-matrix. For nonnegative $Q$-completion problem, necessary conditions and sufficient conditions for a digraph to have nonnegative $Q$-completion are obtained. Further, the digraphs of order at most four that have nonnegative $Q$-completion have been studied.

Keywords

• Digraph,Partial matrix,Matrix completion,Nonnegative Q-matrix,Q-completion problem

References

1. [1] G. Chartrand, L. Lesniak, Graphs and Digraphs, Fourth Edition, Chapman & Hall/CRC, London, 2005.
2. [2] J. Y. Choi, L. M. DeAlba, L. Hogben, B. Kivunge, S. Nordstrom, M. Shedenhelm, The nonnegative P_0−matrix completion problem, Electron. J. Linear Algebra 10 (2003) 46–59.
3. [3] J. Y. Choi, L. M. DeAlba, L. Hogben, M. S. Maxwell, A. Wangsness, The P_0−matrix completion problem, Electron. J. Linear Algebra 9 (2002) 1–20.
4. [4] L. M. Dealba, L. Hogben, B. K. Sarma, The Q−matrix completion problem, Electron. J. Linear Algebra 18 (2009) 176–191.
5. [5] S. M. Fallat, C. R. Johnson, J. R. Torregrosa, A. M. Urbano, P−matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312(1–3) (2000) 73–91.
6. [6] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
7. [7] L. Hogben, Graph theoretic methods for matrix completion problems, Linear Algebra Appl. 328(1–3) (2001) 161–202.
8. [8] L. Hogben, Matrix completion problems for pairs of related classes of matrices, Linear Algebra Appl. 373 (2003) 13–29.

9. [9] L. Hogben, A. Wangsness, Matrix completion problems, in Handbook of Linear Algebra, L. Hogben, Editor, Chapman and Hall/CRC Press, Boca Raton, 2007.
10. [10] C. R. Johnson, B. K. Kroschel,The combinatorially symmetric P−matrix completion problem, Electron. J. Linear Algebra 1 (1996) 59–63.
11. [11] C. Jordon, J. R. Torregrosa, A. M. Urbano, Completions of partial P−matrices with acyclic or non–acyclic associated graph, Linear Algebra Appl. 368 (2003) 25–51.