1 The Q-matrix completion problem

By Luz DeAlba, Leslie Hogben, Bhaba Sharma.

A partial matrix is a matrix that contains some specified entries, while all other entries remain unspecified and can be freely assingned a value. An n×n partial matrix, B, specifies a digraph D = (V_{D}, A_{D}), if V_{D} = {1, 2, …, n}, and (i, j) ∈ A_{D} if and only if the entry b_{ij} of B is specified. A real n × n matrix is a Q-matrix if for every k = 1, 2, …, n, the sum of all k ×k principal minors is positive. A partial matrix is a partial Q-matrix if the sum of all k × k principal minors is positive for every k for which all k × k principal matrices are fully specified. A digraph D is said to have Q-completion if every partial Q-matrix specifying D can be completed to a Q-matrix. In this presentation we give sufficient conditions for a digraph to have Q-completion, we also give necessary conditions for a digraph to have Q-completion, and characterize those digraphs of order at most four that have Q-completion.