The nonnegative Q−matrix completion problem
Keywords:
Digraph, Partial matrix, Matrix completion, Nonnegative Q-matrix, Q-completion problemAbstract
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.
Downloads
References
G. Chartrand and L. Lesniak, Graphs & Digraphs, 4th ed., Chapman & Hall/CRC, Boca Raton, FL, 2005.
J. Y. Choi, L. M. DeAlba, L. Hogben, B. Kivunge, S. K. Nordstrom, and M. Shedden, The nonnegative $P_0$–matrix completion problem, Electron. J. Linear Algebra 10 (2003) 46–59.
J. Y. Choi, L. M. DeAlba, L. Hogben, M. S. Maxwell, and A. Wangsness, The $P_0$–matrix completion problem, Electron. J. Linear Algebra 9 (2002) 1–20.
L. M. DeAlba, L. Hogben, and B. K. Sarma, The $Q$–matrix completion problem, Electron. J. Linear Algebra 18 (2009) 193–203.
S. M. Fallat, C. R. Johnson, J. R. Torregrosa, and A. M. Urbano, $P$–Matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312(1–3) (2000) 73–89.
F. Harary, Graph Theory, Addison-Wesley Publishing Company, Reading, MA, 1969.
L. Hogben, Graph theoretic methods for matrix completion problems, Linear Algebra Appl. 328(1–3) (2001) 161–202.
L. Hogben, Matrix completion problems for pairs of related classes of matrices, Linear Algebra Appl. 363 (2003) 141–157.
L. Hogben and A. Wangsness Wehe, Matrix completion problems, in: L. Hogben (Ed.), Handbook of Linear Algebra, CRC Press, Boca Raton, FL, 2007, pp. 33-1–33-18.
C. R. Johnson and B. K. Kroschel, The combinatorially symmetric $P$–matrix completion problem, Electron. J. Linear Algebra 1 (1996) 59–63.
C. Jordán, J. R. Torregrosa, and A. M. Urbano, Completions of partial $P$–matrices with acyclic or non–acyclic associated graphs, Linear Algebra Appl. 368 (2003) 25–51.
