# Characterization of the Existence of anN0-Completion of a Partial N0-Matrix with an Associated Directed Cycle

Authors: Cristina Jordán; Juan R. Torregrosa
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Ann×n matrix is called an N0-matrix if all its specified principal minors are nonpositive. In the context of partial matrices, a partial matrix is called a partial N0-matrix if all its specified principal minors are nonpositive. In this paper we characterize the existence of an N0-matrix completion of a partial N0-matrix whose associated graph is a directed cycle.


---

## Body

## 1. Introduction

Apartial matrix is a rectangular array, some of whose entries are specified while the remaining unspecified entries are free to be chosen (from a certain set). In this paper we are going to work on the set of the real numbers and to assume that all diagonal entries are prescribed. A completion of a partial matrix is the matrix resulting from a particular choice of values for the unspecified entries. A completion problem asks if we can obtain a completion of a partial matrix with some prescribed properties.The technics to obtain this completion depend on the pattern of the partial matrix which can becombinatorially symmetric (i.e., aij is specified if and only if aji is) or noncombinatorially symmetric. Here we are going to work with this second class of partial matrices.A natural way to describe ann×n partial matrix A=(aij) is via a graph GA=(V,E), where the set of vertices V is {1,2,…,n} and there is an arc from i to j if and only if position (i,j) of A is specified. In general, a directed graph (resp., nondirected graph) is associated with a noncombinatorially symmetric (resp., combinatorially symmetric) partial matrix. Since all main diagonal entries are specified we omit loops.Acycle in a directed graph G is a sequence of arcs (i1,i2),(i2,i3),…,(ik-1,i1), where ik≠il for all k≠l.In the last years many completions problems have been analysed. The completion problem for partialM-matrices, P-matrices, N-matrices, …, has been studied by Johnson, Hogben, Urbano, Mendes, …, among others. See, for instance [1–9] and the references therein.As a class of square real matrices that contains theN-matrices we define the N0-matrices, n×n real matrices A=(aij), where all its principal minors are nonpositive. Since N0-matrices are preserved by principal submatrices we define a partialN0-matrix as a partial matrix whose completely specified principal submatrices are N0-matrices.In general it is not always true that a partialN0-matrix has an N0-matrix completion as the following matrix shows (see [7]):
(1)A=[-11-10x2-11-100-0.110-111-101-1].A is a partial N0-matrix that has an N0-matrix completion that leads us to analyze the N0-matrix completion problem depending on the pattern of the partial matrix. We have studied in [7] when a combinatorially symmetric partial N0-matrix with no null main diagonal entries such that the graph of its specified entries is a 1-chordal graph or a cycle has an N0-matrix completion.In this paper we study the mentioned problem for partialN0-matrices that can have zeros at the main diagonal and whose associated graph is a directed cycle of length equal to the order of the matrix. In this case we may suppose without loss of generality that these matrices have the form:
(2)[a11a12x13⋯x1nx21a22a23⋯x2n⋮⋮⋮⋮xn-1,1xn-1,2xn-1,3⋯an-1,nan1xn2xn3⋯ann],
where aij denotes a specified entry and xij an unspecified one.Observe that when we say “ai,i+1, i=1,2,…,n, where the subscripts are expressed module n”, we are using the congruence module n; that is, we are considering the entries a12,a23,…,an-1n,an1.Given a matrixA of size n×n the submatrix lying in rows α and columns β, α, β⊆N={1,2,…,n} is denoted by A[α∣β] and the principal submatrix A[α∣α] is abbreviated to A[α].We denotea¯=1 if a=0 and a¯=a if a≠0.In the next section we introduce necessary and sufficient conditions in order to guarantee the existence of anN0-matrix completion of a partial N0-matrix whose associated graph is a directed cycle.


## 2. Completion of PartialN0-Matrices

It is easy to prove thatN0-matrices as well as partial N0-matrices satisfy the following properties.Proposition 1.
LetA=(aij) be an n×nN0-matrix. (1)
IfPis a permutation matrix, thenPAPTis anN0-matrix.(2)
IfDis a positive diagonal matrix, thenDAandADareN0-matrices.(3)
IfDis a nonsingular diagonal matrix, thenDAD-1is anN0-matrix.(4)
Ifaii≠0,i=1,2,…,n, thenaij≠0, for alli,j∈{1,2,…,n}.(5)
Every principal submatrix ofAis anN0-matrix.In [7] the authors proved that any n×n  N0-matrix with no null diagonal entries is diagonally similar to an N0-matrix in the set:
(3)Sn={A=(aij):sign(aij)=(-1)i+j+1,∀i,j}.
But since there are N0-matrices with some entries equal to zero we need to introduce the following set:
(4)wSn={A=(aij):aij=0orsign(aij)=(-1)i+j+1,∀i,j}.We also extend the definition ofwSn matrices to partial matrices; that is, PwSn consists of the n×n partial matrices A=(aij) such that if aij≠0 then sign(aij)=(-1)i+j+1, for all specified entry (i,j), i, j∈{1,2,…,n}. The following matrix B is an example of a matrix of PwS4,
(5)B=[-11-10x2y0-100z10-111-101-1].The following results, consequence of Proposition1, allow us to transform a partial N0-matrix A=(aij), whose associated graph is a directed cycle, into a matrix whose diagonal nonzero values are −1; the nonzero elements of the first upperdiagonal are 1 and the element in position (n,1) is a¯12a¯23⋯a¯n1.Proposition 2.
LetA=(aij) be an n×n partial N0-matrix. There exists a positive diagonal matrix D such that matrix B=DA=(bij) is also an N0-partial matrix with bii equal to −1 or to zero, for all i=1,2,…,n.Proof.
It suffices to considerD={d1,d2,…,dn} defined di=-1/aii if aii≠0 and di=0 if aii=0.Proposition 3.
LetA=(aij) be an n×n partial N0-matrix, whose associated graph is a directed cycle, such that aii is −1 or 0, for all i=1,2,…,n. Then there exists a diagonal matrix D such that DAD-1=(cij) is a partial N0-matrix with cii=aii for all i=1,2,…,n, cii+1=1 or zero for all i=1,2,…,n-1 and cn1=a¯12a¯23⋯a¯n1.Proof.
It suffices to considerD=diag(1,a¯12,a¯12a¯23,…,a¯12a¯23⋯a¯n-1n).Therefore, ifA=(aij) is an n×n partial N0-matrix whose associated graph is a directed cycle, we will assume, without loss of generality, that A has the following structure: −1 or zeros on the main diagonal, 1’s or zeros in the first upper diagonal and a¯12a¯23⋯a¯n1 in position (n,1).The following theorem characterizes thePwSn matrices as an intermediate step to obtain the desired completion. It can be easily obtained from the transformations of Propositions 2 and 3.Theorem 4.
LetA be an n×n partial matrix, n even (resp., odd), whose associated graph is a directed cycle. If all entries aii+1, i=1,2,…,n, where the indices are expressed module n, are nonzero the matrix A is diagonally similar to an element of PwSn if and only if a12a23⋯an1>0 (resp., a12a23⋯an1<0).Now we analyze the existence of anN0-matrix completion of a partial N0-matrix with an associated directed cycle, by distinguishing between matrices with no null main diagonal entries and matrices with some null values in the main diagonal.Theorem 5.
LetA be an n×n partial N0-matrix, with nonzero main diagonal entries such that its associated graph is a directed cycle. The following statements are equivalent: (1)
a12a23⋯an1>0 if n is even (a12a23⋯an1<0 if n is odd),(2)
A is diagonally similar to an element of PwSn,(3)
there exists anN0-matrix completion of A.Proof.
Observe that from (4) of Proposition1, we have that all the specified entries are nonzero. Then, from commentary after Proposition 3, we assume that all the elements in the main diagonal are −1 and the first upper diagonal is formed by 1’s.
Let us suppose thatn is even; the case n odd is analogous. Since the upper diagonal and the element in position (n,1) are nonzero, by applying Theorem 4, the condition a12a23⋯an1>0 is equivalent to item 2.
Now, we assume that the second statement is true. We considerA′=(aij′), where aij′=aij if aij is a specified value of A, ai+1i′=1 for i=1,2,…,n, where subscripts are expressed module n and an1′=1/(a12a23⋯an1). Then A′ is an n×n partial N0-matrix, with nonzero main diagonal entries such that its associated graph is a nondirected cycle. Theorem 4.3 of [7] assures that A′, and therefore A has an N0-matrix completion.
Finally, from the note after Proposition1, the third statement implies the second one.Now, it arises the question about establishing an analogous result to Theorem5, when zero entries appear in the main diagonal. The answer is negative since if we admit a zero diagonal element and a zero entry in the upper diagonal, there exist matrices in PwSn, n is even, such that a¯12a¯23⋯a¯n1 is negative, but that admits an N0-matrix completion. For example, matrix A=(aij) defined
(6)A=[00x13x14x21-11x24x31x32-11-1x42x43-1]
is diagonally similar to an element of PwS4 by using D=diag(-1,1,1,1) and it has an N0-matrix completion, Ac, although a¯12a¯23a¯34a¯41 is negative,
(7)Ac=[00000-11-101-11-1-11-1].The following results characterize this type of matrices. Note that, if there are some null main diagonal entries, the existence of anN0-matrix completion implies that if aiiai+1i+1≠0, then aii+1≠0. So, we add this condition as a hypothesis. In addition, recall that we are going to assume that aii=-1 or zero for all i∈{1,2,…,n}; the entries in the first upper diagonal are 1 or zero and the value of the element in position (n,1) is a¯12a¯23⋯a¯n1.Theorem 6.
LetA be an n×n, n even (resp., odd), n≥3, partial N0-matrix with some null main diagonal entries, whose associated graph is a directed cycle. Let one suppose that if aiiai+1i+1≠0 for all i=1,2,…,n, where the indices are expressed module n, then aii+1≠0. If there exists aii+1=0, i∈{1,2,…,n}, where the indices are expressed module n, then there exists an N0-matrix completion.Proof.
LetNp={i1,i2,…,ip} be, with ik<ik′ for all 1≤k<k′≤p, the corresponding indices to the negative diagonal values of matrix A and Nl={ip+1,…,ip+l}, where p+l=n and ih<ih′ for all p+1≤h<h′≤p+l, the corresponding ones to the zero diagonal entries. Since there is i, i∈{1,2,3,…,n-1}, such that aii+1=0, the diagonal similarity allows us to assume, without loss of generality, that an1=1 if p is even and that an1=-1 if p is odd. Let B be the matrix PAPT where P is the permutation matrix P=[eip+1,eip+2,…,eip+l,ei1,ei2,…,eip], being ek the canonical vector for all k∈{1,2,…,n}. Consider B partitioned in a 2×2 block matrix, where B11 is of size l×l and B22 is p×p.
Note that elements of the first upper diagonalaii+1, i∈{1,2,…,n-1}, are moved to blocks Bkl, k,l∈{1,2}, depending on the value of aii and ai+1i+1: if both entries are zero, after the permutation Paii+1 will be in B11; if aii=0 and aii+1=1 the element aii+1 will be in B12; if aii=-1 and aii+1=0 then aii+1 will be in B21 and in other cases aii+1 will be in B22. This is shown in Table 1(a). In Table 1(b) we can see the position that the element an1 of A will occupy after the permutation.
Then we can be sure that each of thel first lines of the permutated matrix B will have as maximum a nonzero value and the last p ones will have exactly one −1 and only another nonzero value as maximum.
We complete with zeros the unspecified entries of blocksB11, B12, and B21. In order to complete B22 we distinguish two cases.(a)
The elementan1 of A is at position (n,l+1). If aii≠0 and ai+1i+1≠0, then aii+1≠0 and, after the permutation, it will be in submatrix B22. If ij+1≠ij+1 then position (ij,ij+1) of the permutated matrix B will be unspecified. Now we partially complete B22 as follows: a1n=1/an1 and aijij+1=1 for all j∈{1,2,…,p}, and by Theorem 5 we get that there exists an N0-completion of B22 named B22c.(b)
The elementan1 of A is not at position (n,l+1). We complete B22 with 1’s and −1’s in order to obtain a matrix with all their diagonals formed alternatively by 1’s and −1’s. All the principal minors of this new matrix will be zero.
The completion ofB, Bc, is an N0-matrix since (a)
the principal minors lying rows and columns with indices inNl are zero, as we can prove by developing by the nonzero elements (there is as maximum one nonzero entry by line);(b)
the principal minors lying rows and columns with indices inNp are less than or equal to zero, since B22c is an N0-matrix completion either an1 of A is at position (n,l+1) or not;(c)
the principal minors with rows and columns with indices inNl and Np are zero, because of they have a row of zeros or, as before, by developing by the only nonzero element of each row, the minor is reduced to one of submatrix B21.
So, matrixA has an N0-matrix completion.Table 1
(a)
a
i
i
+
1
a
i
+
1
i
+
1
=
0
a
i
+
1
i
+
1
≠
0
a
i
i
=
0
B
11
B
12
a
i
i
≠
0
B
21
B
22
(b)
a
n
1
a
11
=
0
a
11
≠
0
a
n
n
=
0
(
l
,
1
)
(
in
B
11
)
(
l
,
l
+
1
)
(
in
B
12
)
a
n
n
≠
0
(
n
,
1
)
(
in
B
21
)
(
n
,
l
+
1
)
(
in
B
22
)Theorem 7.
LetA be an n×n, n even (resp., odd), n≥3, partial N0-matrix with some null main diagonal entries, whose associated graph is a directed cycle. Let one suppose that if aiiai+1i+1≠0 for all i=1,2,…,n where the indices are expressed module n, then aii+1≠0. If aii+1≠0 for all i∈{1,2,…,n}, where the indices are expressed module n, then the condition a12a23⋯an1>0 for n even (resp., a12a23…an1<0 for n odd) is necessary and sufficient for the existence of an N0-matrix completion.Proof.
Letn be even. If a12a23…an1>0 some changes in the proof of the above theorem gives the desired completion. Specifically, choose the zero diagonal entry akk with less index. If 1≤k≤n-1 since a12a23⋯an1>0 matrix A can be transformed by diagonal similarity in a matrix such that if p is even, an1=1 and akk+1 are equal to a positive value and if p is odd, an1=-1 and akk+1 are equal to a negative value. By permutation similarity we get a block-matrix analogous to the previous result and by a similar reasoning we get that there exists an N0-matrix completion of A. If k=n we transform A by the permutation P=[en,e1,…,en-2,en-1], where ek is the canonical vector for all k∈{1,2,…,n} and we proceed in a similar way to the previous result.
Now, we are going to prove the necessity of the condition by induction onn; that is, if there exists an N0-completion of A, Ac=(cij), then c12c23⋯cn1>0 if n is even and c12c23⋯cn1<0 if n is odd. We denote α=c12c23⋯cn1.
Forn=3, if we suppose that α>0 by analyzing the seven different cases that arise depending on the number of zeros, one, two, or three in the main diagonal, we get that detAc>0, that is a contradiction. Then α<0.
Letn>3 be. Suppose n is even (if n is odd the process is analogous). We are showing that in the mentioned conditions if there exists an N0-completion of A, then α>0. Let Ac be an N0-completion of A.
Let us suppose by hypothesis of induction (HI) that the statement is true for all3≤k≤n-1. Since Ac is an N0-matrix, we obtain, from the 2×2 principal minors, that all the entries of the first under diagonal are greater than or equal to zero; that is, ci-1i≥0 for all i∈{1,2,…,n}.
In addition, if we considerdetA[{i,i+1,…,i+p}] with i∈{1,2,…,n-p}, p∈{2,…,n-2}, we get that cij>0 if i-j is odd and cij<0 if i-j is even for i∈{1,2,…,n-1}, j∈{1,2,…,n-2}, i>j.
From the nonpositivity ofdetA[{i,j}] for all i∈{1,2,…,n-2}, j∈{3,…,n}, we obtain that the upper diagonals follow the same rule of signs of the under diagonals, alternatively positive and negative, but with the option of zero; that is, cij≥0 if j-i is odd and cij≤0 if j-i is even for i∈{1,2,…,n-2}, j∈{3,…,n}, i<j.
Now we study the case in which there existsi∈{3,…,n} such that a1i≠0.(a)
Ifi∈{3,…,n-1} we consider detA[{1,i,i+1,…,n}]. The (n-i+2)×(n-i+2) submatrix of Ac,A′=Ac[{1,i,i+1,…,n}] can be considered as a completion of a partial N0 matrix of size strictly smaller than n with all the first upper diagonal formed by 1’s. If A′ has at least a zero diagonal entry, taking into account that c1i≤0 if i is odd and c1i≥0 if i is even, the hypothesis of induction allows us to assure that the entry in position (n-i+2,1) of A′; that is, α is positive. In the other case, if all the diagonal entries are nonzero we get the same conclusion by Theorem 5. This ends the proof in this case.(b)
Ifi=n and c1i=0 with i∈{1,…,n-1}, we analyze two cases: (b.1) c11=0 or cnn=0 and (b.2) c11≠0 and cnn≠0. In the first one, we get α>0 from detAc[{1,3,n}]. If c11≠0, cnn≠0 and c22=0 and cii≠0 for all i∈{3,…,n-1} we get α>0 from detAc[{1,n-1,n}]≤0. If c11≠0, cnn≠0 and there exists i∈{3,…,n-1} such that cii=0 we get also the same result from detAc[{1,i,n}]≤0.
In this casec1i=0 for all i∈{3,…,n} if some entry cij of the upper triangular part of Ac is nonzero, we also obtain that α>0 by using detAc[{1,2,…,i-1,i,j,j+1,…,n}]≤0 and HI.
Therefore, it remains to analyze the case in which all the upper triangular part except the first upper diagonal is zero. As we will see now, most of the cases can not be given.
Letcii be the nonzero diagonal entry with less index. If i≥5 from detAc[{1,2,3,i}]≤0 or if i∈{1,2,3,4} and n≥i+4 from detAc[{1,n-2,n-1,n}]≤0 we get a contradiction. Now we study the remaining cases depending on the values of n and i.
Ifn=4 from detAc≤0 we get α>0 (if i=4 to show it we also use detAc[{1,2,4}]≤0).
Ifn=5 and ci+1i+1=0 from detAc≤0 we obtain α<0 (if i=3 to show it we also use detAc[{1,2,4,5}]≤0 and detAc[{1,2,4}]≤0 if i=4). If n=5, ci+1i+1≠0 and i∈{2,3} from detAc≤0 we get α<0 (if i=2 to show it we also use detAc[{2,4,5}]≤0 and detAc[{1,2,4}]≤0 if i=3); if i=4detAc[{1,2,4}]≤0 and detAc[{1,2,3,5}]≤0 leads a contradiction.
Ifn=6 and i=3 from detAc≤0 we get α>0 (if ci+1i+1=0 to show it we also use detAc[{1,2,5,6}]≤0 and detAc[{1,2,4,5,6}]≤0 and if ci+1i+1≠0, the nonpositivity of detAc[{1,2,4}]. If n=6, i=4 and ci+1i+1=0 from detAc≤0 and detAc[{1,2,4}]≤0 we get α>0. In this case if ci+1i+1≠0 the nonpositivity of detAc[{1,2,4}] and detAc[{1,2,3,5}] leads to a contradiction.
Finally, ifn=7 and i=4 we get a contradiction by using detAc[{1,2,4}]≤0 and also detAc[{1,2,3,5}]≤0 if ci+1i+1≠0, or if ci+1i+1=0 the nonpositivity of detAc[{1,2,3,5,6}] and detAc[{1,2,3,5,6,7}].We sum up the results of Theorems6 and 7 in Table 2. One can consider a similar one for n odd.Table 2
*Under the assumption thataiiai+1i+1≠0 implies aii+1≠0.
∀
i
a
i
i
+
1
≠
0
∃
i
a
i
i
+
1
=
0
*
∀
i
a
i
i
≠
0
a
12
a
23
…
a
n
1
>
0 iff∃N0-matrix completion(Theorem 5)
N
0-matrix completion has no sense(Proposition 1)
∃
i
a
i
i
=
0
a
12
a
23
…
a
n
1
>
0 iff∃N0-matrix completion(Theorem 7)
∃
N
0-matrix completion(Theorem 6)
A is an n×n, neven, partial N0-matrix, whose associated graph is a directed cycle.



---

*Source: 835017-2014-02-04.xml*