The $Q$-matrix completion problem

A partial matrix is a real square matrix with some specified entries while other entries are unspecified. By completion of a partial matrix, we have to choose specific values for the unspecified entries. The matrix completion problem studies those partial matrices which have desired type of completions.

A real $n×n$ matrix $A$ is a $P$-matrix (⁠$P0$-matrix) if every principal minor of $A$ is positive (nonnegative). A real $n×n$ matrix $B=[bij]$ is a $Q$-matrix if for every $k∈{1,2,…,n}$⁠, $Sk(B)>0$⁠, where $Sk(B)$ is the sum of all $k×k$ principal minors of $B$⁠. The matrix $B$ is $Q0$-matrix if for every $k∈{1,2,…,n}$⁠, $Sk(B)≥0$⁠. Clearly a $Q$-matrix is a $Q0$-matrix but not conversely.

A partial $Q$-matrix $C$ is a partial matrix in which $Sk(C)>0$ for every $k∈{1,2,…,n}$ for which all $k×k$ principal submatrices are fully specified. Similarly a partial $Q0$-matrix $C1$ is a partial matrix in which $Sk(C1)≥0$ for every $k=1,…,n$⁠.

To make a completion of a partial matrix, a specific choice of value for the unspecified entries is chosen. Thus the main motive of matrix completion problem is to investigate the properties of partial matrices and find out those partial matrices which have a particular type of completions. In the last few years, research is done for different classes of matrices in the area of Matrix Completion Problems. Several researchers have developed many results of matrix completion problems for different classes of matrices including $P$ and $P0$⁠, $Q$-matrices (e.g.,[2–5,7,8,10,14]). To see the details of the definition and properties of different classes of partial matrices (i.e $P,P0$ or $Q$-partial matrices) and results regarding matrix completion problems, we suggest [9].

From the beginning of matrix completion problems, we have found that graphs and digraphs are widely used in solving the matrix completion problems. A digraph $D$ is a pair $(V,A)$⁠, where $V$ is a finite nonempty set of objects, called vertices, and $A$ is a set of ordered pairs of vertices, called arcs or directed edges. We use $VD$ and $AD$ to denote the vertex set and the arc set of $D$ respectively and we write frequently $v∈D$ (respectively, $(u,v)∈D$⁠) to say that $v∈V(D)$ (respectively $(u,v)∈A(D)$⁠). An arc $x=(u,u)$ in the arc set of a digraph $D$⁠, which is called a loop at the vertex $u$ is allowed in our given definition. Most of the graph-theoretic terms used in this article can be found in any standard book, for example [1,6]. However for the convenience of the readers’ of this article, we request them to follow the introduction part of the article [11–13].

In this paper, we have studied the (combinatorial) $Q0$-matrix problem. In Section 2, we have defined the partial $Q0$-matrix and the $Q0$-matrix completion problem. We have discussed the relationship between digraphs and $Q0$-completion in Section 3. We have discussed some necessary and sufficient conditions for $Q0$-matrix completion problem in Section 4. In Section 5, we tried to find out the relationship between $Q$ and $Q0$-matrix completion problem. Finally in Section 6, we have singled out of all digraphs of order up to 4 with $Q0$-matrix completion.

A partial $Q0$-matrix $C=[cij]$ is a partial matrix in which $Sk(C)≥0$ for every $k=1,…,n$ for which all $k×k$ principal submatrices of $C$ are fully specified. In Proportion 2.1, we characterize $C=[cij]$ as follows.

Proposition 2.1. Suppose $C=[cij]$ is a partial matrix. Then $C$ is a partial $Q0$-matrix if and only if exactly one of the following holds:

• (i) At least one diagonal entry of $C$ is not specified.

• (ii) All diagonal entries are specified so that $Tr(M)≥0$ and $C$ has an off diagonal unspecified entry.

• (iii) All entries of $C$ are specified and $C$ is a $Q0$-matrix.

A completion $A$ of a partial $Q0$-matrix $C$ is called a $Q0$-completion of $C$⁠, if $A$ is a $Q0$-matrix. If $A$ is a $Q0$-matrix, then any matrix which is permutation similar to $A$ is a $Q0$-matrix. As a consequence any digraph isomorphic to $D$ which has $Q0$-completion also has $Q0$-completion.

Any partial $Q0$ matrix $C$ with all unspecified diagonal entries has $Q0$-completion. By choosing sufficiently large values for the unspecified diagonal entries, the desired $Q0$-completion of $C$ is obtained. Now consider a partial $Q0$-matrix $C$ with unspecified diagonal entries at $(i,i)$ positions $(i=k+1,…,n)$⁠. We may not get a $Q0$-completion of $C$ in case $C[1,…,k]$ is fully specified. To see this, the partial matrix,

where $?$ denotes an unspecified entry, does not have $Q0$-completion. For any completion $A$ of $C$⁠, we have $S2(A)≤0$⁠. However, if $C[1,…,k]$ has an unspecified entry and has a $Q$-completion, then $C$ has a $Q0$-completion. By choosing sufficiently large values for the unspecified diagonal entries, a $Q0$-completion of $C$ can be obtained. We write our observations in the following results:

The following example shows that the converse of Corollary 2.4 is not true.

where $?$ denotes the unspecified entries. We show that $C$ has $Q0$-completions, though there are occasions when $C[2,4]$ does not have $Q$-completion. For $t>0$⁠, consider the completion $B(t)$ of $C$ defined as follows:

Then,

where $fi(t)$ is a polynomial in $t$ of degree at most $i,i=1,2,3$⁠. Consequently, $B(t)$ is a $Q0$-matrix for sufficiently large $t$⁠, and therefore, $C$ has $Q0$-completion. However, the partial $Q$-matrix

with unspecified entry $x42$⁠, is the principal submatrix of $C$ induced by its diagonal ${2,4}$⁠. That $C[2,4]$ does not have $Q$-completion is evident, because $S2(M[2,4])=0$ for any completion of $C[2,4]$⁠.

Remark 2.6. We can see that $C[1,2,…,r]$ in Theorem 2.3 may not be a partial $Q$-matrix. If all the specified diagonal entries are zero, then Theorem 2.3 does not hold automatically. Also Example 2.5 shows that $C[2,4]$ may not have $Q0$-completion. To see that consider a partial $Q0$-matrix

with unspecified entry $x42$⁠. $C[2,4]$ does not have $Q0$-completion since for any completion $B1$ of $C[2,4]$⁠, we have $S2(C[2,4])≤0$⁠.

An $n×n$ partial matrix $C$ specifies a digraph $D=({1,2,…,n},AD)$ if for $1≤i,j≤n$⁠, $(i,j)∈AD$ if and only if the $(i,j)$th entry of $C$ is specified. As an example, we can see that the partial $Q0$-matrix $C$ in Example 2.5 specifies the digraph $D$ in Figure 1.

Theorem 3.1. Suppose $C$ is a partial matrix specifying the digraph $D$ . If the partial submatrix of $C$ induced by every strongly connected induced subdigraph of $D$ has $Q0$-completion, then $C$ has $Q0$-completion.

Proof. First we consider the case when $D$ has two strong components say, $D1$ and $D2$⁠. Later on the general result will automatically follow from induction. If required, by a relabelling of the vertices of $D$⁠, we have

where $Cii$ is a partial $Q0$-matrix specifying $Di,i=1,2$⁠, and $X$ contains all unspecified entries. Now, we have $Cii$ has a $Q0$-completion $Bii$⁠. Consider the completion

by choosing all entries in $X$ as well as all unspecified entries in $C12$ as $0$⁠. Then, for $2≤k≤|D|$ we have,

Here, we mean $Sk(Bii)=0$ whenever $k$ exceeds the size of $Bii$⁠. Thus $C$ can be completed to a $Q0$-matrix ■.

The proof of the following result is similar.

Theorem 3.2. Suppose $C$ is a partial matrix specifying the digraph $D$. If the partial submatrix of $C$ induced by each component of $D$ has a $Q0$-completion, then $C$ has a $Q0$-completion.

The converse of Theorem 3.1 is not true. For example, every partial $Q0$-matrix specifying the digraph $D$ in Figure 1 has $Q0$-completion, although the strong component $D1$ induced by vertices ${1,2}$ does not have $Q0$-completion (see Example 3.3).

Example 3.3. Consider the digraph $D$ in Figure 1. We show that $D$ has $Q0$-completion, but the strong component $D1$ induced by vertices ${1,2}$ does not have $Q0$-completion. Let $C=[cij]$ be a partial $Q0$-matrix specifying $D$⁠. Then for $t>0$⁠, $C$ can be completed to a $Q0$-matrix $B(t)$ (see Example 2.5) but the principal submatrix induced by the digraph $D1$ i.e. $C[1,2]$ does not have $Q0$-completion. To see that $C[1,2]$ does not have $Q0$-completion, consider the partial $Q0$-matrix

with unspecified entry $x$⁠. Then for any $Q0$-completion $B$ of $C[1,2]$⁠, we have $S2(B)≤0$ and hence $C[1,2]$ does not have $Q0$-completion.

The property of having $Q0$-completion is not hereditary which can be also seen from Example 2.5.

A digraph $D$ has $Q0$-completion, if every partial $Q0$-matrix specifying $D$ can be completed to a $Q0$-matrix. The main motive of $Q0$-matrix completion problem is to study and classify all digraphs $D$ based on $Q0$-completion.

Theorem 4.1. If a digraph $D≠Kn$ of order $n$ has $Q0$-completion, then any spanning subdigraph of $D$ has $Q0$-completion.

Proof. Suppose $H$ be a spanning subdigraph of $D$ and $CH$ be a partial $Q0$-matrix specifying the digraph $H$⁠. Consider a partial matrix $CD$ obtained from $CH$ by specifying the entries corresponding to $(i,j)∈CD\CH$ as $0$⁠. Since $D≠Kn$⁠, by Proposition 2.1, $CD$ is a partial $Q0$-matrix specifying $D$⁠. Let $B$ be a $Q0$-completion of $CD$⁠. Clearly, $B$ is a $Q0$-completion of $CH$⁠. ■

Theorem 4.2. Suppose $D≠Kn$ be a digraph such that $D¯$ is stratified. If it is possible to sign the arcs of $D¯$ so that the sign of every cycle in $D$ is of positive sign, then $D$ has $Q0$-completion.

Proof. Suppose $C$ be a partial $Q0$-matrix specifying the digraph $D$⁠. For any $t>0$⁠, consider a completion $B$ of $C$ by choosing the unspecified entry $xij=sgn(i,j)t$ (using the sign of the arc in $D¯$⁠). Then for each $k=2,3,…,n$⁠, we have,

where $ck$ is the number of permutation subdigraphs of order $k$ in $D$ and $rk(t)$ is a polynomial of degree less than $k$⁠. If $D$ contains all loops, then the trace of any partial $Q0$-matrix specifying $D$ is nonnegative; if $D$ omits a loop, then $S1(B)=c1t+r0$⁠, where $c1$ is the number of loops in $D$ and $r0∈R$⁠. Now by choosing $t$ sufficiently large results, $B$ becomes a $Q0$-matrix. ■

Example 4.3. Consider the complement $D¯$ in Figure 2 of the digraph $D$ in Figure 1. It can be easily seen that the digraph $D¯$ is stratified. Also it is possible to sign the arcs of $D¯$ with positive sign, thus by Theorem 4.2 the digraph $D$ has $Q0$-completion.

Corollary 4.4. If $D$ is a digraph and $D$ has a stratified spanning subdigraph that has a signing in which the sign of every cycle is +, then $D$ has $Q0$-completion.

In this section we provide some necessary conditions for a digraph to have $Q0$-completion.

Theorem 4.5. Suppose $D$ be a digraph of order $n$ which includes all loops. If $D¯$ has no $2$-cycle, then $D$ does not have $Q0$-completion.

Proof. Let $D$ be a digraph of order $n$ which includes all loops. Suppose $C=[cij]$ be a partial $Q0$-matrix specifying the digraph $D$ which is defined as follows:

It is clear that $C$ is a partial $Q0$-matrix specifying $D$⁠. Now $D¯$ does not contain a $2$-cycle, then for any completion $B$ of $C$⁠, we have $S2(B)≤0$⁠. Thus $D$ does not have $Q0$-completion. ■

be a partial $Q0$-matrix specifying the digraph $D2$⁠. Then for any completion $B$ of $C$⁠, we have $S2(B)≤0$ by Theorem 4.5. Hence, $C$ cannot be completed to a $Q0$-matrix.

Corollary 4.7. If a digraph $D$ of order $n$ includes all loops and has $Q0$-completion, then $D¯$ must not be a tournament or subdigraph of a tournament.

Proof. If $D¯$ is a tournament or a subdigraph of a tournament, then it does not contain a $2$-cycle. Hence, the result follows. ■

The converse of Theorem 4.5 is not true which follows from Example 4.8.

Example 4.8. Consider the digraph $D3$ in Figure 4. The complement of the digraph $D3$ i.e. $D¯3$ contains a $2$-cycle. But $D3$ does not have $Q0$-completion. Consider a partial $Q0$-matrix

specifying the digraph $D3$⁠. Then for any completion $B$ of $C$⁠, we have $S3(B)≤0$⁠. Hence, $C$ cannot be completed to a $Q0$-matrix.

Although every $Q$-matrix is a $Q0$-matrix, but the completion problem of these two classes is different. We list these observations in the following result.

Theorem 5.1. If a digraph $D$ has $Q0$-completion, then it must also have $Q$-completion.

Proof. Suppose $D$ be a digraph that has $Q0$-completion and $M$ be a partial $Q$-matrix specifying the digraph $D$⁠. Then, the sums of all fully specified principal minor of same order of $M$ are positive. Since the determinant and each principal minor of a matrix are a continuous function of its entries, there is $ϵ>0$ such that the partial matrix $M0$ obtained from $M$ by decreasing the specified diagonal entries by $ϵ$ is a partial $Q$-matrix. Since a partial $Q$-matrix is a partial $Q0$-matrix, $M0$ is a partial $Q0$-matrix specifying $D$⁠. Consequently, $M0$ has a $Q0$-completion $B0$⁠. We now have a $Q$-completion of $M$⁠, namely, $B=B0+ϵI$⁠, where $I$ is the identity matrix. ■

The following equivalent corollary is immediate.

Corollary 5.2. Any digraph which does not have $Q$-completion does not have $Q0$-completion.

But the converse of Theorem 5.1 is not completely true which can be seen in the following two cases.

Case 1. Suppose $D$ includes all loops. In this case $D$ has $Q$-completion but does not have $Q0$-completion.

Example 5.3. Consider the symmetric $4$-cycle $C4$ (Figure 5) which includes all loops. Now $C4$ has $Q$-completion (see Example 2.2 of [4]). To see that $C4$ does not have $Q0$-completion, consider the partial $Q0$-matrix

specifying $C4$⁠. For a completion $B$ of $M$⁠, the 3 × 3 principal minor is given by

Then we have $S3(B)=−1≤0$ and $M$ cannot be completed to a $Q0$-matrix.

Case 2. Suppose $D$ omits at least a loop. Then we have the following theorem:

Theorem 5.4. Suppose $D$ be a digraph such that $D$ omits at least a loop. If $D$ has $Q$-completion, then $D$ must have $Q0$-completion.

Proof. Suppose $M$ be a partial $Q0$-matrix specifying $D$⁠. Since $D$ omits at least a loop, thus at least a diagonal entry of $M$ is unspecified. Thus $M$ is a partial $Q$-matrix. Since $D$ has $Q$-completion, $M$ can be completed to a $Q$-matrix $B$⁠. Consequently, $B$ is a $Q0$-matrix. ■

With the help of the results obtained in the previous sections, we will sort out all digraphs of order $≤4$ which have loops at all its vertices and have $Q0$-completion. In this regard we will take the help of the nomenclature of the digraphs as per their order in [6, Appendix, p. $233$]. Here, $Dp(q,n)$ denotes the $n$th member digraph with loop at each $p$ vertices and it has $q$ (non-loop) arcs.

As we know that any matrix under permutation similarity to a $Q0$-matrix is also a $Q0$-matrix, if a digraph $D$ has $Q0$-completion, then any isomorphic digraph of $D$ has $Q0$-completion, that is, any digraph obtained by labelling the unlabelled digraph associated to $D$ has $Q0$-completion.

Clearly, any digraph of order $1$ (with or without a loop) has $Q0$-completion. There are only two non-isomorphic digraphs of order $2$ with loops say, $D2(0,1)$ and $D2(2,1)$ have $Q0$-completion.

The rest of the section is broken up into a series of lemmas.

Lemma 6.1. For $1≤p≤4$ , the digraphs $Dp(q,n)$ which are listed below do not have $Q0$-completion.

Proof. Each of the digraphs listed above satisfies Theorem 4.5 and hence the result follows. ■

Lemma 6.2. The digraphs $D4(7,2)$ and $D4(8,2)$ do not have $Q0$-completion.

Proof. In Example 5.3, it is seen that the digraph $D4(8,2)$ (i.e. $C4$⁠) does not have $Q0$-completion. Suppose

be a partial $Q0$-matrix specifying the digraph $D4(7,2)$⁠. Now for any $Q0$-completion $B$ of $M$⁠, we have $S3(B)=−1$⁠. Hence $D4(7,2)$ does not have $Q0$-completion. ■

Lemma 6.3. For $1≤p≤4$ , the digraphs $Dp(q,n)$ which are listed below do not have $Q0$-completion.

Proof. Each of the digraphs does not have $Q$-completion, thus by Corollary 5.2 the above digraphs do not have $Q0$-completion. ■

Theorem 6.4. For $1≤p≤4$⁠, the digraphs $Dp(q,n)$ which are listed below have $Q0$-completion.

Proof. The complement $Dp(q,n)¯$ of each of the digraphs $Dp(q,n)$ is stratified and it is possible to sign the arcs of the $Dp(q,n)¯$ with positive sign, thus by Theorem 4.2, each of the digraphs listed above has $Q0$-completion. ■

Remark 6.5. In this paper, the $Q0$-matrix completion is discussed. Some necessary and sufficient conditions for a digraph to have $Q0$-completion are discussed. Although these conditions helped us to single out the digraphs of order at most $4$ as to $Q0$-completion, the problem is far from being completely solved. A complete characterization for a digraph to have $Q0$-completion is still unresolved. Out of 218 digraphs of order $4$⁠, only 11 digraphs are still not singled out to have $Q0$-completion or not. Since the $Q0$-completion problem is not still fully solved, thus the following digraphs $Dp(q,n)$⁠, $1≤p≤4$ are not classified according to the $Q0$-completion.

The publisher wishes to inform readers that the article “The Q₀-matrix completion problem” was originally published by the previous publisher of the Arab Journal of Mathematical Sciences and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Sinha, K. (2019), “The Q₀-matrix completion problem”, Arab Journal of Mathematical Sciences, Vol. 27 No. 1, pp. 119-128. The original publication date for this paper was 26/08/2019.