ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.05630 J. Algebra Comb. Discrete Appl. 4(1) • 61–74 Received: 25 January 2016 Accepted: 4 June 2016 Journal of Algebra Combinatorics Discrete Structures and Applications The nonnegative Q−matrix completion problem Research Article Bhaba Kumar Sarma, Kalyan Sinha Abstract: In this paper, the nonnegative Q-matrix completion problem is studied. A real n × n matrix is a Q-matrix if for k ∈ {1, . . . , n}, the sum of all k × 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. 2010 MSC: 05C20, 05C50 Keywords: Digraph, Partial matrix, Matrix completion, Nonnegative Q-matrix, Q-completion problem 1. Introduction A partial matrix is a rectangular array of numbers in which some entries are specified while others are free to be chosen. A partial matrix M is fully specified if all entries of M are specified, i.e., if M is a matrix. Let 〈n〉 = {1, . . . ,n} and M be an n × n partial matrix, i.e., one with n rows and n columns. For a subset α of 〈n〉, the principal partial submatrix M(α) is the partial matrix obtained from M by deleting all rows and columns not indexed by α. A principal minor of M is the determinant of a fully specified principal submatrix of M. A partial nonnegative (positive) matrix is a partial matrix whose specified entries are nonnegative (positive). A real n × n matrix B is a P-matrix (P0-matrix ) if every principal minor of B is positive (nonneg- ative). The matrix B is a Q-matrix, if for each k ∈ {1, . . . ,n} the sum of all k × k principal minors of B is positive. A nonnegative Q-matrix is a Q-matrix whose all entries are nonnegative. The property of being P , P0 or Q-matrix is invariant under permutation similarity. For a given class Π of matrices (e.g., P , P0 or Q-matrices) a partial Π-matrix is a partial matrix for which the specified entries fulfill the requirements of a Π-matrix. Thus, a partial P0-matrix (partial P-matrix ) is one in which all fully specified principal minors are nonnegative (positive). Similarly, a Bhaba Kumar Sarma, Kalyan Sinha (Corresponding Author); Department of Mathematics, Indian Institute of Technology Guwahati, Guwahat, Assam 781039, India (email: bks@iitg.ernet.in, kalyansinha90@gmail.com). 61 http://dx.doi.org/10.13069/jacodesmath.05630 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 partial Q-matrix is a partial matrix M in which Sk(M) > 0 for every k ∈ {1,2, . . . ,n} for which all k ×k principal submatrices are fully specified. A completion of a partial matrix is a specific choice of values for the unspecified entries. A Π- completion of a partial Π-matrix M is a completion of M which is a Π-matrix. Matrix completion problems for several classes of matrices including the classes of P and P0-matrices have been studied by a number of authors (e.g., [2, 3, 5, 7, 8, 10, 11]). In 2009, DeAlba et al. [4] considered the Q-matrix completion problem. Since the property of being a Q-matrix is not inherited by principal submatrices, the authors observed that the Q-matrix completion problem is substantially different from the completion problems studied earlier and attracts special attention. In their paper, it was shown that for Q-matrix completion of a digraph, stratification (see Section 2) of its complement is necessary and positive signing of the stratified complement of the digraph is sufficient. (Here, positive signing of a digraph means a signing of each of its arcs with the property that for each even (resp. odd) cycle the product of the signs of arcs on the cycle is negative (resp. positive).) Further, the authors classified all digraphs of order up to order 4 as to Q-matrix completion. Theorem 1.1. [4] Let D be a digraph of order n that omits at least one loop. (i) If D has Q-completion, then D is stratified. (ii) If n ≤ 4 and D is stratified, then D has Q-completion. Theorem 1.2. [4] Let D 6= Kn be an order n digraph that includes all loops and has Q-completion. Then for each k = 2,3, . . . ,n, either, (i) D has a permutation digraph of order k, or (ii) for each v ∈ V (D), D − v has a permutation digraph of order k − 1. Theorem 1.3. [4] Let D 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 is +, then D has Q-completion. For an extensive survey of matrix completion problems, we refer the relevant sections in Handbook of Linear Algebra [9] published by Chapman and Hall/CRC Press. In this paper, we make a combina- torial study of the completion problem of partial nonnegative Q-matrices in which digraphs will play an important role. 2. Preliminaries Most of the definitions of the graph-theoretic terms used in this paper can be found in any standard reference, for example, in [1] and [6]. For our purpose, a directed graph or digraph D = (V (D),A(D)) of order n > 0 is a finite nonempty set V (D), with |V (D)| = n of objects called vertices together with a (possibly empty) set A(D) of ordered pairs of vertices (not necessarily distinct), called arcs or directed edges. Sometimes, we simply write v ∈ D (resp. (u,v) ∈ D) to mean v ∈ V (D) (resp. (u,v) ∈ A(D)). If x = (u,v) is an arc in D, we say that x is incident with u and v. If x = (u,u), then x is called a loop at the vertex u. By K∗n we denote the digraph with vertex set 〈n〉 = {1, . . . ,n} and arc set 〈n〉 × 〈n〉, i.e., one with all possible arcs including loops on the vertex set 〈n〉. A digraph H is a subdigraph of the digraph D if V (H) ⊆ V (D), A(H) ⊆ A(D). If V (W) ⊆ V (D), the subdigraph induced by V (W), i.e. W , is the digraph W = (V (W),A(W)) with A(W) the set of all arcs of D between the vertices in W . The digraph W is a spanning subdigraph if V (W) = V (D). The complement of a digraph D is the digraph D, where V (D) = V (D) and (v,w) ∈ A(D) if and only if (v,w) /∈ A(D). Two digraphs D1 = (V1,A1) and D2 = (V2,A2) are isomorphic, if there is a bijection ψ : V1 → V2 such that A2 = {(ψ(u),ψ(v)) : (u,v) ∈ A1}. 62 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 A (directed) u-v path P of length k ≥ 0 in D is an alternating sequence (u = v0,x1,v1, . . . , xk,vk = v) of vertices and arcs, where vi, 1 ≤ i ≤ k, are distinct vertices and xi = (vi−1,vi). Then, the vertices vi and the arcs xi are said to be on P . Further, if k ≥ 2 and u = v, then a u-v path is a cycle of length k. We then write Ck = 〈v1,v2, . . . ,vk〉 and call Ck a k-cycle in D. Paths and cycles in a digraph D are considered to be subdigraphs of D in a natural way. A cycle C is even (resp. odd) if its length is even (resp. odd). A digraph D is said to be connected (resp. strongly connected) if for every pair u,v of vertices, D contains a u-v path (resp. both a u-v path and a v-u path). The maximal connected (resp. strongly connected) subdigraphs of D are called components (resp. strong components) of D. Let π be a permutation of a nonempty finite set V . The digraph Dπ = (V,Aπ), where Aπ = { ( v,π(v) ) : v ∈ V }, is called a permutation digraph. Clearly, each component of a permutation digraph is a loop or a cycle. The digraph Dπ is said to be positive (resp. negative) if π is an even permutation (resp. an odd permutation). It is clear that Dπ is negative if and only if it has odd number of even cycles. A permutation subdigraph H (of order k) of a digraph D is a permutation digraph that is a subdigraph of D (of order k). Further, H is positive (negative) if the corresponding permutation is even (odd). A digraph D is (positively) stratified if D has a (positive) permutation subdigraph of order k for every k = 2,3, . . . , |D|. By Pk we denote the collection of all permutation subdigraphs of order k of K ∗ n. Further, we denote by P+ k (resp. P− k ) the collection of all positive (resp. negative) permutation subdigraphs of order k of K∗n. Let B = [bij] be an n × n matrix. We have detB = ∑ (sgnπ)b1π(1) · · ·bnπ(n) (1) where the sum is taken over all permutations π of 〈n〉. For a permutation digraph P of K∗n we denote the product ∏ {bij : (i,j) ∈ A(P)} by w(P,B). For k ∈ {1, . . . ,n} we denote the sum of all k × k principal minors of B by Sk(B). In view of (1), we have Sk(B) = ∑ P ∈P + k w(P,B) − ∑ P ∈P − k w(P,B). (2) 3. Partial nonnegative Q-matrices and their completions Recall that a partial Q-matrix M is a partial matrix such that Sk(M) > 0 for every k ∈ {1, . . . ,n} for which all k ×k principal submatrices are fully specified. Let M be a partial nonnegative Q-matrix. If all 1 × 1 principal submatrices (i.e., all diagonal entries) in M are specified, then their sum S1(M) (the trace of M) must be positive. If all k × k principal submatrices are fully specified for some k ≥ 2, then M is fully specified and, therefore, is a nonnegative Q-matrix. Thus, a partial nonnegative Q-matrix is characterized as follows. Proposition 3.1. Let M be a partial nonnegative matrix. Then, M is a partial nonnegative Q-matrix if and only if exactly one of the following holds: (i) At least one diagonal entry of M is not specified. (ii) All diagonal entries are specified, at least one diagonal entry is positive and M has an off-diagonal unspecified entry. (iii) All entries of M are specified and M is a Q-matrix. A completion B of a partial nonnegative Q-matrix M is called a nonnegative Q-completion of M, if B is a nonnegative Q-matrix. Since any matrix which is permutation similar to a Q-matrix is a Q-matrix, it is evident that if a partial nonnegative Q-matrix has a nonnegative Q-completion, so does any partial matrix which is permutation similar to M. 63 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 Any partial nonnegative matrix M with all diagonal entries unspecified has nonnegative Q- completion. A completion of M can be obtained by choosing sufficiently large values for the unspecified diagonal entries. Let M = [mij] be a partial nonnegative Q-matrix which contains both specified and unspecified diag- onal entries. Consider the principal partial submatrix M(α) of M induced by α = {i : mii is specified} ⊆ 〈n〉. In case M(α) is fully specified, M may not have a nonnegative Q-completion. For example, the partial matrix M =   1 0 0 0 0 0 0 0 ∗   where ∗ denotes an unspecified entry, M(1,2) is fully specified. That M does not have a nonnegative Q-completion is evident; because for any completion B of M, S3(B) = detB = 0. For the case when M(α) is not fully specified or itself a Q-matrix, we have the following. Theorem 3.2. Let M = [mij] be a partial nonnegative Q-matrix and α = {i : mii is specified}. If the principal partial submatrix M(α) of M has nonnegative Q-completion, then M has nonnegative Q- completion. Proof. If α = {1, . . . ,n}, then M = M(α) has a nonnegative Q-completion, by the hypothesis. Other- wise, without any loss of generality, we assume α = {1, . . . ,r} for some 1 ≤ r ≤ n − 1 and M = [ M11 M12 M21 M22 ] , where M11 = M(1, . . . ,r) and M22 = M(r + 1, . . . ,n). Let B11 be a nonnegative Q-completion of M(1, . . . ,r). Then, M′ = [ B11 M12 M21 M22 ] is a partial nonnegative Q-matrix, since M22 has unspecified diagonal entries. For t > 0, consider the completion B(t) = [ B11 B12 B21 B22 ] of M obtained by taking bii = t, i = r+1, . . . ,n, and bij = 0 for all other unspecified entries in M. Since B11 is a nonnegative Q-matrix we have Si(B11) > 0 for 1 ≤ i ≤ r. Now, for 1 ≤ j ≤ n, Sj(B(t)) = { ( n−r j ) tj + pj(t), if j ≤ n − r, Sj−n+r(B11)t n−r + pj(t), if j > n − r, where pj(t) is a polynomial in t of degree at most j − 1, if j ≤ n − r, and of degree at most n − r − 1, if j > n − r. As a consequence, for sufficiently large values of t, Sj(B(t)) > 0 for 1 ≤ j ≤ n and B(t) is a nonnegative Q-completion of M. The converse of Theorem 3.2 is not true. The following example shows that a partial nonnegative Q-matrix M may have Q-completion, even when M(α) does not have. Example 3.3. Consider the partial matrix, M =   ∗ b12 b13 b14 b21 d2 b23 ∗ ∗ ∗ d3 b34 ∗ b42 ∗ ∗   , (3) 64 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 where ∗ denotes the unspecified entries. Here, α = {2,3} and M(α) does not have a Q-completion for d2 = b23 = 0 and d3 = 1. However, we show that for any choice of nonnegative values of the specified entries bij, M has nonnegative Q-completions. For t > 0 consider the completion B(t) =   t b12 b13 b14 b21 d2 b23 t t t d3 b34 t b42 t t   of M. Then, S1(B(t)) = 2t + d2 + d3, S2(B(t)) = t 2 + f1(t), S3(B(t)) = t 3 + f2(t), S4(B(t)) = t 4 + f3(t), where fi(t) is a polynomial in t of degree at most i, i = 1,2,3. Consequently, B(t) is a nonnegative Q-matrix for sufficiently large t, and therefore, M has nonnegative Q-completions. 4. Digraphs and nonnegative Q-completions It is useful to associate a partial matrix with a digraph that describes the positions of the specified entries in the partial matrix. We say that an n×n partial matrix M specifies a digraph D = (〈n〉,A(D)), if for 1 ≤ i,j ≤ n, (i,j) ∈ A(D) if and only if the (i,j)-th entry of M is specified. For example, the partial nonnegative Q-matrix M in Example 3.3 specifies the digraph D1 in Figure 1. b 4 b 3 b 2 b1 Figure 1. The digraph D1 Theorem 4.1. Suppose M is a partial nonnegative Q-matrix specifying the digraph D. If the partial sub- matrix of M induced by every strongly connected induced subdigraph of D has nonnegative Q-completion, then M has nonnegative Q-completion. Proof. We prove the result for the case when D has two strong components H1 and H2. The general result will then follow by induction. By a relabelling of the vertices of D, if required, we have M = [ M11 M12 X M22 ] , where Mii is a partial nonnegative Q-matrix specifying Hi, i = 1,2, and all entries in X are unspecified. By the hypothesis, Mii has a nonnegative Q-completion Bii. Consider the completion B = [ B11 B12 B21 B22 ] , 65 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 by choosing all unspecified entries in M12 and X as 0. Then, for 2 ≤ k ≤ |D| we have Sk(B) = Sk(B11) + Sk(B22) + k−1∑ r=1 Sr(B11)Sk−r(B22) > 0, Here, we mean Sk(Bii) = 0 whenever k exceeds the size of Bii. Thus M can be completed to a nonnegative Q-matrix. The proof of the following result is similar. Theorem 4.2. Suppose M is a partial nonnegative Q-matrix specifying the digraph D. If the partial sub- matrix of M induced by each component of D has a nonnegative Q-completion, then M has a nonnegative Q-completion. That the converse of Theorem 4.1 is not true can be seen from the following example. Example 4.3. Consider the digraph D2 in Figure 2. We show that every partial nonnegative Q-matrix b 1 b 2 b 3 b 4 b 5 b 6 D2 Figure 2. A digraph having nonnegative Q-completion specifying the digraph D2 has nonnegative Q-completion. To see this consider any partial nonnegative Q-matrix M = [aij] specifying D2. For t > 1 consider the completion B(t) =   t a12 0 0 a15 0 0 a22 t 0 a25 a26 0 a32 t a34 t 0 0 0 0 t a45 0 0 t 0 0 a55 a56 a61 0 0 0 0 t   of M. Then, we have S1(B(t)) = 4t + a22 + a55, S2(B(t)) = 6t 2 + f1(t), S3(B(t)) = 5t 3 + f2(t), S4(B(t)) = 4t 4 + f3(t), S5(B(t)) = 3t 5 + f4(t), S6(B(t)) = t 6 + f5(t), 66 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 where fi are polynomials of degree at most i in t. It is clear that Sk(B(t)) > 0, 1 ≤ k ≤ 6, for sufficiently large values of t. Hence M has nonnegative Q-completions. On the other hand, the vertices 1,2,5 and 6 induce a strong component H of D2. Consider the partial nonnegative Q-matrix M1 specifying H and with all specified entries as zero and B1 =   x11 0 0 x16 x21 0 0 0 x51 x52 0 0 0 x62 x65 x66   , any nonnegative completion of M1. Then S4(B1) = −x16x21x52x65 ≤ 0, and consequently B1 is not a nonnegative Q-matrix. 5. The nonnegative Q-completion problem For a class Π of matrices (e.g., P , P0 or Q-matrices) a digraph D is said to have Π-completion, if every partial Π-matrix specifying D can be completed to a Π-matrix. The Π-matrix completion problem refers to the study of digraphs which have Π-completion. We say that a digraph D has nonnegative (positive) Q-completion, if every partial nonnegative (positive) Q-matrix specifying D can be completed to a nonnegative (positive) Q-matrix. The nonnegative (positive) Q-matrix completion problem aims at studying and classifying all digraphs D which have nonnegative (positive) Q-completion. Example 5.1. It follows from Example 4.3 that the digraph D2 in Figure 2 has nonnegative Q-completion. However, its strong component H induced by the vertices 1,2,5 and 6 does not have nonnegative Q- completion. In particular, this exhibits that the property of having nonnegative Q-completion is not preserved to induced subdigraphs. It is clear that if a digraph D has (nonnegative, positive) Q-completion, then any digraph which is isomorphic to D has (nonnegative, positive) Q-completion. 5.1. Sufficient conditions for nonnegative Q-completion Proposition 5.2. If a digraph D 6= K∗n of order n has nonnegative Q-completion, then any spanning subdigraph of D has nonnegative Q-completion. Proof. Let H be a spanning subdigraph of D. Let MH be a partial nonnegative Q-matrix specifying the digraph H. Consider the partial matrix MD obtained from MH by specifying the entries corresponding to (i,j) ∈ A(D) \ A(H) as 0. Since D 6= K∗n, by Proposition 3.1, MD is a partial nonnegative Q-matrix specifying D. Let B be a nonnegative Q-completion of MD. Clearly, B is a nonnegative Q-completion of MH. For a digraph D = (V,A), a weight function on D is a real valued function φ defined on A. The triplet (V,A,φ) is then called a weighted digraph. For e ∈ A, φ(e) is called the weight of e. Further, for any permutation subdigraph P of D, we denote the sum of the weights of the edges on P by φ∗(P). Theorem 5.3. Let D be a digraph of order n. Suppose there is a weight function φ on D satisfying the following: for each k ∈ {1, . . . ,n}, there is a positive permutation subdigraph Pk of order k in D such that, 67 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 b 1 b 2 b 3 b 4 D3 b1 b 2 b 3 b 4 D3 1 1 1 11 Figure 3. The digraph D3 and its complement D3 (i) φ∗(Pk) > φ ∗(P) for every negative permutation subdigraph P of D of size k, and (ii) φ∗(Pk) > ∑ e∈S φ(e), for any subset S ⊆ A(D) with |S| ≤ k − 1. Then, D has nonnegative Q-completion. Proof. Let M = [mij] be a partial nonnegative Q-matrix specifying D. For x > 1 consider the completion B(x) = [bij] of M defined by, bij = { mij, if (i,j) ∈ D xφ(e), if e = (i,j) ∈ D. For k ∈ {1, . . . ,n}, we have Sk(B(x)) = ∑ P ∈P + k w(P,B(x)) − ∑ P ∈P − k w(P,B(x)). Since Pk ∈ P + k , w(Pk,B(x)) = x φ ∗(Pk) is a term with a positive coefficient in Sk(B(x)). On the other hand, any P ∈ P− k is one of the following: (i) a negative permutation subdigraph of D of order k, (ii) a permutation subdigraph of K∗n with at most k − 1 arcs from D. In view of the properties of φ, we have, w(P,B(x)) = αxt, where α ≥ 0 and t < φ∗(Pk). Consequently, for large values of x, we have Sk(B(x)) > 0 for k = 1, . . . ,n and hence D has nonnegative Q-completion. Example 5.4. Consider the digraph D3 in Figure 3. Consider the weight function φ on the arcs of D3 obtained by assigning unit weights to the arcs (1,4),(4,2), (2,1) and to the loops at 3 and 4, and assigning zero weights to all other arcs. The nonzero weights have been marked in bold-faces in D3 in Figure 3. We choose the following positive permutation digraphs with their respective weights in D3. P1 - the loop at 3, φ ∗(P1) = 1 P2 - the union of the loops at 3 and 4, φ ∗(P2) = 2 P3 - the 3-cycle [1,4,2], φ ∗(P3) = 3 P4 - the union of the loop at 3 and the 3-cycle [1,4,2], φ ∗(P4) = 4. Further, the only even cycles in D3 are the cycles [2,3] and [1,3,4,2] of weights 0 and 2, respectively. It is clear that φ satisfies the conditions (i) and (ii) in Theorem 5.3, and therefore, D3 has nonnegative Q-completion. 68 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 Corollary 5.5. Let D be a digraph of order n such that (i) D is stratified, and (ii) D does not have an even cycle. Then D has nonnegative Q-completion. Proof. Let 2 ≤ k ≤ n. Since D is stratified, D has a permutation subdigraph Pk of order k. Since D does not have an even cycle, D does not have any negative permutation subdigraph. Thus, Pk is positive. Further, P2 being even, it must be composed of two loops, and therefore, D has a (positive) permutation subdigraph of order 1 as well. We define φ(e) = 1 for each e ∈ A(D). Then the weight function φ in D satisfies conditions (i) and (ii) of Theorem 5.3. Remark 5.6. One does not expect the converse of Theorem 5.3 to be true. However, the converse holds for all digraphs we have examined, including all digraphs of order at most four. That is, for each of these digraphs which have nonnegative Q-completion, there is a weight function on its complement satisfying the conditions (i) and (ii) in Theorem 5.3. 5.2. Necessary conditions for nonnegative Q-completion Proposition 5.7. Let D be a digraph with at least two vertices. If D has nonnegative Q-completion, then D omits at least two loops. Proof. Suppose D omits at most one loop. Let M be a partial nonnegative Q-matrix specifying the digraph D with all specified entries as 0. Then for any nonnegative completion B of M, S2(B) ≤ 0. The converse of the Proposition 5.7 is not true. The digraph D4 in Figure 4 omits 2 loops but does not have nonnegative Q-completion. For example, M =   0 0 0 0 x22 x23 x31 0 x33   is a partial nonnegative Q-matrix specifying D4 which has no nonnegative Q-completion. In fact, a b 1 b 2 b 3 D4 Figure 4. A digraph which does not have nonnegative Q-completion digraph needs to satisfy stronger conditions to have nonnegative Q-completion, as the following result shows. Theorem 5.8. If a digraph D of order n (n ≥ 2) has nonnegative Q-completion, then D is positively stratified. 69 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 Proof. Suppose D has nonnegative Q-completion. Assume D has no positive permutation digraph of order k for some k ≥ 2. If M is the partial matrix that specifies D with all specified entries zero, and B is a nonnegative completion of M, then all k × k principal minors of B are nonpositive implying that B is not a nonnegative Q-matrix. Corollary 5.9. Let D be a digraph of order n such that |A(D)| > n(n − 1). Then D does not have nonnegative Q-completion. Proof. If D has more than n(n − 1) arcs (including loops), then D has fewer than n2 − n(n − 1) = n arcs. Thus D does not contain permutation subdigraph of order n. Therefore, by Theorem 5.8, D does not have nonnegative Q-completion. The converse of the Theorem 5.8 is not true, which can be seen from the following example. b 1 b 2 b 3 b 4 b5 D5 b 1 b 2 b 3 b 4 b 5 D5 Figure 5. A digraph whose complement is positively stratified Example 5.10. The complement D5 of the digraph D5 in Figure 5 is positively stratified. However, we show that D5 does not have nonnegative Q-completion. Let M be the partial nonnegative Q-matrix specifying D5 with all specified entries as zero. Consider a nonnegative completion B =   0 x12 0 x14 0 0 0 0 x24 0 x31 0 d3 0 x35 0 0 x43 0 0 x51 0 0 0 d5   of M. For B to be a nonnegative Q-matrix, we have S1(B) = d3 + d5 > 0, (4) S2(B) = d3d5 > 0, (5) S3(B) = x14x43x31 > 0, (6) S4(B) = d5x14x43x31 − x12x24x43x31 − x14x43x35x51 > 0, (7) S5(B) = x12x24x43x35x51 − x12x24x43x31d5 > 0. (8) Clearly, the entries in B against all unspecified entries in M must be positive. Now, from (7) we have d5x14x31 > x12x24x31 + x14x35x51 which yields d5x31 > x35x51. On the other hand, (8) implies that x35x51 > d5x31. Hence B cannot be a nonnegative Q-matrix. Theorem 5.11. Let D be a digraph with at least four vertices. Suppose D has more than one 2-cycle and does not have a 3-cycle. If D has nonnegative Q-completion, then D must omit more than three loops. 70 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 Proof. For D to have nonnegative Q-completion, D must omit at least two loops, by Proposition 5.7. We prove that if D omits exactly three loops, then D does not have nonnegative Q-completion. Then, the result for the case when D omits exactly two loops will follow from Proposition 5.2. Suppose D omits loops at the vertices 1,2 and 3. Now, we label the 2-cycles as E1, . . . ,Ek (k > 1) such that the number of vertices among 1,2 and 3 that Ej is incident with is in ascending order in j. Let M be the partial nonnegative Q-matrix specifying the digraph D with all specified entries as zero. Suppose that M has a nonnegative Q-completion B = [bij]. We put d1 = b11, d2 = b22, d3 = b33. For a 2-cycle E = 〈r,s〉 in D, we write w(E) = w(E,B) = brsbsr. Then, by (2) we have S3(A) = d1d2d3 − (d1σ1 + d2σ2 + d3σ3), (9) where σt = ∑ { w(Ei) : Ei is not incident with t } , t = 1,2,3. Since S3(B) > 0, (9) implies d1d2 > σ3, d2d3 > σ1, d3d1 > σ2, (10) and therefore d1d2 + d2d3 + d3d1 > σ1 + σ2 + σ3. (11) For 1 ≤ j ≤ k, let βj = ∑ { w(Ei) : Ei ∩ Ej = ∅ and i > j } γj = ∑ { dsdt : Ej is incident with none of s and t } . Then, by (2) we have S4(A) = k∑ j=1 βj w(Ej) − k∑ j=1 γj w(Ej) = k∑ j=1 (βj − γj)w(Ej). (12) However, we show that βj − γj ≤ 0 for 1 ≤ j ≤ k. Then, it will follow from (12) that S4(B) ≤ 0, a contradiction to the fact that B is a Q-matrix. Fix j ∈ {1,2, . . . ,k}. We have γj =    d1d2 + d2d3 + d3d1, if Ej is not incident with any of the vertices 1,2,3, (d1d2d3)/dt, if Ej is incident with only t, t = 1,2 or 3, 0, if Ej is incident with two of the vertices 1,2 and 3. If Ej is not incident with any of the vertices 1,2 and 3, then from (11) we get βj ≤ k∑ i=1 w(Ei) ≤ σ1 + σ2 + σ3 < d1d2 + d2d3 + d3d1 = γj. Next, suppose Ej is incident with exactly one vertex t in {1,2,3}. Consider the case t = 1. Since {Ei : Ei ∩ Ej = ∅, i > j} ⊆ {Ei : 1 is not incident with Ei}, we have βj ≤ σ1. Therefore, from (10) we get βj ≤ σ1 < d2d3 = γj. The cases when t = 2 and 3 are similar. Finally, assume that Ej is incident to two among the vertices 1,2 and 3 so that γj = 0. Now, for any i > j the 2-cycle Ei is incident with two vertices among 1,2 and 3. Consequently, by our choice of the ordering of the 2-cycles, Ei and Ej have a vertex in common yielding βj = 0. Therefore, our assertion that βj − γj ≤ 0 for 1 ≤ j ≤ k holds. 71 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 6. Nonnegative Q-completion of digraphs of small order We have examined the digraphs of order at most four to nonnegative Q-completion. Clearly, any digraph of order 1 (with or without a loop) has nonnegative Q-completion. Any digraph of order 2 without a loop has nonnegative Q-completion. There are only four non-isomorphic digraphs of order 3 without loops for which the digraphs obtained by attaching a loop at any of the vertices have nonnegative Q-completion. These digraphs are precisely the spanning subdigraphs of a 3-cycle. Some types of digraphs of order four with respect to nonnegative Q-completion are presented below. (a) Let D̂6 be a digraph obtained from the digraph D6 in Figure 6 by adding at most two loops at any of its vertices. Then, D̂6 has nonnegative Q-completion. (In fact, D̂6 satisfies the conditions of Theorem 5.3.) There are 41 non-isomorphic digraphs of order 4 without loops having similar property as D6, i.e., all digraphs obtained from them by attaching at most two loops at any of the vertices have nonnegative Q-completion. b1 b 2 b 3 b 4 b1 b 2 b 3 b 4 Figure 6. The digraph D6 and its complement D6 (b) Let D̂7 be any digraph obtained from the digraph D7 in Figure 7 by attaching two loops. If D̂7 has nonnegative Q-completion, then it must omit a loop at the vertex 2. In fact, in that case D̂7 satisfies the conditions of Theorem 5.3. There are 66 non-isomorphic digraphs D of order 4 without loops having similar property as D7, i.e., a digraph obtained from D by attaching at most two loops at its vertices has nonnegative Q-completion only when D omits a loop at a particular vertex. b1 b 2 b 3 b 4 b1 b 2 b 3 b 4 Figure 7. The digraph D7 and its complement D7 (c) Let D̂8 be any digraph obtained from the digraph D8 in Figure 8 by adding a loop at any of the vertices. Then, D̂8 does not have nonnegative Q-completion (by Theorem 5.11). There are 22 non-isomorphic digraphs of order 4 without loops having similar property as D8, i.e., any digraph obtained from them by attaching a loop at a vertex does not have nonnegative Q-completion. 72 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 b1 b 2 b 3 b 4 b1 b 2 b 3 b 4 Figure 8. The digraph D8 and its complement D8 7. Comparison between Q-completion, and nonnegative and pos- itive Q-completion problems In this section, we compare the nonnegative Q-completion problem with the Q-completion and the positive Q-completion problems. Proposition 7.1. If a digraph D has nonnegative Q-completion, then D has positive Q-completion. Proof. Suppose D has nonnegative Q-completion. Let M = [aij] be a partial positive Q-matrix specifying the digraph D. Then M is a partial nonnegative Q-matrix specifying D. Let B be a nonnegative Q-completion of M. Then, perturbing the zero entries in B by small positive quantities, a positive Q- completion of M can be obtained. However, the converse is not true which can be seen from the following example. Example 7.2. Consider the digraph D9 in Figure 9. Let M = [mij] be a partial positive Q-matrix specifying D9. We write M =   m11 m12 x13 x21 m22 m23 m31 x32 m33   , where xij are unspecified. It is easy to see that putting sufficiently small values for xij, M can be completed to a positive Q-matrix, implying that D9 has positive Q-completion. However, in view of Proposition 5.7, D9 does not have nonnegative Q-completion, since D9 has all loops. b 1 b 2 b 3 D9 Figure 9. A digraph having positive Q-completion, but not nonnegative Q-completion The following example shows that a digraph having Q-completion may fail to have nonnegative Q-completion. Example 7.3. Consider the digraph D10 in Figure 10. Let M = [mij] be a partial Q-matrix specifying D10. We write, M =   x11 x12 x13 x21 m22 m23 m31 x32 m33   , 73 B. K. Sarma, K. Sinha / J. Algebra Comb. Discrete Appl. 4(1) (2016) 61–74 where xij are unspecified. We put x12 = −x and all other unspecified entries as x. It is easy to see that with sufficiently large values for x, M can be completed to a Q-matrix, implying that D10 has Q- completion. However, in view of Proposition 5.7, D10 does not have nonnegative Q-completion, because it omits only one loop. b 1 b 2 b 3 D10 Figure 10. A digraph having Q-completion, but not nonnegative Q-completion Suppose D is a digraph having nonnegative Q-completion. Then, D is stratified and omits at least two loops. For all small digraphs (including all digraph of order 4) having these properties are seen to have Q-completion. Whether a stratified digraph omitting a loop necessarily have Q-completion is not known (see Question 2.9 in [4]). We do not know whether there is a digraph having nonnegative Q completion, but not Q-completion. 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 P0−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 P0−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, Elec- tron. 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. 74 http://dx.doi.org/10.13001/1081-3810.1095 http://dx.doi.org/10.13001/1081-3810.1068 http://dx.doi.org/10.13001/1081-3810.1303 http://dx.doi.org/10.1016/S0024-3795(00)00088-4 http://dx.doi.org/10.1016/S0024-3795(00)00299-8 http://dx.doi.org/10.1016/S0024-3795(02)00531-1 http://dx.doi.org/10.13001/1081-3810.1004 http://dx.doi.org/10.1016/S0024-3795(02)00654-7 http://dx.doi.org/10.13001/1081-3810.1095 http://dx.doi.org/10.13001/1081-3810.1068 http://dx.doi.org/10.13001/1081-3810.1303 http://dx.doi.org/10.1016/S0024-3795(00)00088-4 http://dx.doi.org/10.1016/S0024-3795(00)00299-8 http://dx.doi.org/10.13001/1081-3810.1004 http://dx.doi.org/10.1016/S0024-3795(02)00654-7 http://dx.doi.org/10.1016/S0024-3795(02)00531-1 http://dx.doi.org/10.1016/S0024-3795(02)00654-7 Introduction Preliminaries Partial nonnegative Q-matrices and their completions Digraphs and nonnegative Q-completions The nonnegative Q-completion problem Nonnegative Q-completion of digraphs of small order Comparison between Q-completion, and nonnegative and positive Q-completion problems References