The nonnegative Q−matrix completion problem

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,

PDF

___

[1] G. Chartrand, L. Lesniak, Graphs and Digraphs, Fourth Edition, Chapman & Hall/CRC, London, 2005.
[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] 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] L. M. Dealba, L. Hogben, B. K. Sarma, The Q−matrix completion problem, Electron. J. Linear Algebra 18 (2009) 176–191.
[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] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.
[7] L. Hogben, Graph theoretic methods for matrix completion problems, Linear Algebra Appl. 328(1–3) (2001) 161–202.
[8] L. Hogben, Matrix completion problems for pairs of related classes of matrices, Linear Algebra Appl. 373 (2003) 13–29.
[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] C. R. Johnson, B. K. Kroschel,The combinatorially symmetric P−matrix completion problem, Electron. J. Linear Algebra 1 (1996) 59–63.
[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.