The nonnegative Q−matrix completion problem

Year 2017, Volume: 4 Issue: 1, 61 - 74, 11.01.2017

Bhaba Kumar Sarma Kalyan Sinha

https://doi.org/10.13069/jacodesmath.05630

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] 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.