# Primitive Zero-Symmetric Sign Pattern Matrices with Zero Diagonal Attaining the Maximum Base

Authors: Ling Zhang; Ting-Zhu Huang; Zhongshan Li
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

The base set of primitive zero-symmetric sign pattern matrices with zero diagonal is{1,2,…,2n−1}. In this paper, the primitive zero-symmetric sign pattern matrices with zero diagonal attaining the maximal base 2n−1 are characterized.


---

## Body

## 1. Introduction

A sign pattern matrix (or sign pattern)A is a matrix whose entries are from the set {1,-1,0}. Notice that for a square sign pattern matrix A, in the computation of (the signs of) the entries of the power Ak, an ambiguous sign may arise when a positive sign is added to a negative sign. So a new symbol # was introduced in [1] to denote such an ambiguous sign. The powers of a square sign pattern have been investigated to some extent, see, for example, [1–12]. In [1], the set Γ={1,-1,0,#} is defined as the generalized sign set and the matrices with entries in the set Γ are called generalized sign pattern matrices, and the addition and multiplication involving the symbol # are defined as follows:
(1.1)(-1)+1=1+(-1)=#;a+#=#(∀a∈Γ),0·#=#·=0;b·#=#·b=#(∀b∈Γ∖{0}).From now on, we assume that all the matrix operations considered in this paper are operations of the matrices over the setΓ.Definition 1.1.
Asquare generalized sign pattern matrix A is called powerful if each power of A contains no # entry.
In [1], Li et al. introduced the concepts of base and period for (powerful) sign pattern matrices which are the generalizations of the concepts of “index of convergence” and period for square nonnegative matrices. These concepts are extended from (powerful) sign pattern matrices to (square) generalized sign pattern matrices by You et al. in [12] as follows.Definition 1.2 (see [12]).
LetA be a square generalized sign pattern matrix of order n and A,A2,A3,… the sequence of powers of A. (Since there are only 4n2 different generalized sign patterns of order n, there must be repetitions in the sequence.) Suppose Al is the first power that is repeated in the sequence, that is, l is the least positive integer such that Al=Al+p holds for some positive integer p. Then l is called the generalized base (or simply base) of A, and is denoted by l(A). The least positive integer p such that Al=Al+p holds for l=l(A) is called the generalized period (or simply period) of A and is denoted by p(A).
For a sign pattern matrixA, we use |A| to denote the (0,1) matrix obtained from A by replacing each nonzero entry by 1.
A nonnegative square matrixA is primitive if some power Ak>0. The least such as  k is called the primitive exponent (or simply exponent) of A, denoted by exp(A). For convenience, a square sign pattern matrix A is called primitive if |A| is primitive, and in this case we define exp(A)=exp(|A|).Definition 1.3 (see [3]).
A square sign pattern matrixA=(aij)n×n is called zero-pattern symmetric (abbreviated zero-symmetric, or simply ZS) if |A| is symmetric.
It is well known that graph-theoretical methods are often useful in the study of the powers of square matrices, so we now introduce some graph-theoretical concepts.
LetD be a digraph with vertex set V and arc set E (which permits loops but no multiple arcs). By assigning a sign of 1 or −1 to each arc of the digraph D, we obtain a signed digraphS. By a walk W in the digraph D (or the signed digraph S), we mean a sequence of vertices (v0,v1,v2,…,vk) such that ei=(vi-1,vi) is an arc of D for i=1,…,k. The number k is called the length of the walk W, denoted by l(W). If the vertices v0,v1,…,vk-1 are distinct, the walk W is called a path, if vk=v0, the path W is called a cycle in D (and in S). The sign of the walk W in  S, denoted by sgn(W), is defined to be ∏i=1ksgn(ei) where sgn(ei) is the sign of the arc ei.LetA=(aij) be a sign pattern matrix of order n. Then the associated digraph D(A) of A is defined to be the digraph with vertex set V={1,2,…,n} and arc set E={(vi,vj)∣aij≠0}. The associated signed digraph S(A) is obtained from D(A) by assigning the sign of aij to each arc (vi,vj) in D(A).Definition 1.4 (see [10]).
LetD be a digraph (permitting loops but no multiple arcs). Digraph D is called primitive if there is a positive integer k such that for all ordered pairs of vertices vi and vj (not necessarily distinct) in D, there exists a walk of length k from vi to vj. The least such k is called the primitive exponent of D, denoted by exp(D).
It is well known that a digraphD is primitive if and only if D is strongly connected and the greatest common divisor (gcd for short) of the lengths of all the cycles of D is 1 (see [13]).Definition 1.5 (see [3]).
LetS be a signed digraph of order n. Then there is a sign pattern matrix A of order n whose associated signed digraph S(A) is S. We say that S is powerful if A is powerful. Also we define l(S)=l(A).
We say that a sign pattern matrixA=(aij) has zero diagonal if aii=0 for all i. A digraph D with vertex set {v1,…,vn} and arc set E is called symmetric provided that (vi,vj)∈E iff (vj,vi)∈E for all i,j. It is clear that a sign pattern matrix A is ZS iff its associated digraph D(A) is symmetric. For simplicity, we represent a symmetric (signed) digraph by its underlying graph.
The base set of primitive ZS sign pattern matrices and the base set of primitive ZS sign pattern matrices with zero diagonal are given, respectively, in [3, 10]. In [2], Cheng and Liu characterized the primitive ZS sign pattern matrices with the maximum base.
In this paper, we characterize the primitive sign pattern matrices with zero diagonal attaining the maximum base. Our main result is given in the following theorem.Theorem 1.6.
LetA=(aij) be an n×n primitive zero-symmetric sign pattern matrix with zero diagonal. Then
(1.2)l(A)≤2n-1
and the equality holds if and only if A is nonpowerful and skew symmetric, namely, aij=-aji for all 1≤i≤j≤n, and the associated digraph D(A) is isomorphic to G (see Figure 1).Figure 1
The graphG. (All 2-cycles in G are negative, r is odd, 3≤r≤n).The proof of Theorem1.6 will be given in Section 3.


## 2. Preliminary Results

In this section, we introduce some theorems, definitions, and lemmas which we need to use in the proof of our main result in Section3.In [1], Li et al. showed that if an irreducible sign pattern matrix A is powerful, then l(A)=l(|A|). That is to say the study of the base for a primitive powerful sign pattern matrix is essentially the study of the base (i.e., exponent) for primitive (0,1) matrices. Therefore, for a primitive powerful ZS sign pattern matrix with zero diagonal, Theorem 2.1 gives the base.Theorem 2.1 (see [8]).
LetA be an n×n primitive symmetric (0,1) matrix with zero diagonal. Then exp(A)≤2n-4 and the primitive exponent set of n×n primitive symmetric (0,1) matrix with zero diagonal is {2,3,…,2n-4}∖D, where D is the set of odd numbers in {n-2,n-1,…,2n-5}.Theorem 2.2 (see [10]).
LetA be an n×n primitive ZS sign pattern matrix with zero diagonal. Then l(A)≤2n-1.By Theorems2.1 and 2.2, the sign pattern matrices with zero diagonal attaining this upper bound l(A)=2n-1 must be nonpowerful. So it remains to consider nonpowerful sign pattern matrices with zero diagonal.Definition 2.3.
Two walksW1 and W2 in a signed digraph are called a pair of SSSD walks, if they have the same initial vertex, same terminal vertex, and same length, but they have different signs.Lemma 2.4 (see [8]).
LetD be a symmetric digraph. Then D is primitive if and only if D is strongly connected and there exists an odd cycle in D.Lemma 2.5 (see [1, 12]).
IfS is a primitive signed digraph, then  S  is nonpowerful if and only if S contains a pair of cycles C1 and C2, with lengths p1 and p2, respectively, satisfying one of the following conditions:(A1)
p1 is odd and p2 is even and sgn(C2)=-1;(A2)
bothp1 and p2 are odd and sgn(C1)=-sgn(C2).Lemma 2.6 (see [12]).
LetS be a primitive, nonpowerful signed digraph. Then we have the following.(1)
There is an integerk such that there exists a pair of SSSD walks of length k from each vertex x to each vertex y in S.(2)
If there exists a pair of SSSD walks of lengthk from each vertex x to each vertex y, then there also exists a pair of SSSD walks of length k+1 from each vertex u to each vertex v in S.(3)
The minimal suchk (as in (1)) is just l(S), the base of S.Lemma 2.7 (see [7]).
Suppose that ann×n sign pattern matrix A=(aij) is skew symmetric. Let S(A) be the associated signed digraph of A. Let r be an odd integer with 3≤r≤n (n≥3). Then l(S(A))=2n-1 if and only if S(A) is isomorphic to G (see Figure 1).


## 3. Main Results

For an undirected walkW of graph G and two vertices x, y on W, we denote by QW(x→y) a shortest path from x to y on W and by Q(x→y) a shortest path from x to y on G. For a cycle C of G, if x and y are two (not necessarily distinct) vertices on C and P is a path from x to y along C, then C∖P denotes the path or cycle from x to y along C obtained by deleting the edges of P.Lemma 3.1.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. If all the 2 cycles in S(A) are positive, then l(A)≤2n-2.Proof.
SinceA is primitive, it follows from Lemma 2.4 that S(A) is strongly connected and there is an odd cycle C′ in S(A) such that l(C′)=l′. Since A has zero diagonal, there are no loops in S(A) and so l′≥3. Without loss of generality, we assume that C′ is an odd cycle with the least length in S(A).
Case  1. There exists at least one negative even cycle in S(A).
LetC be a negative even cycle in S(A). Without loss of generality, we assume that C is a negative even cycle with the least length in S(A). Since all 2 cycles in S(A) are positive, l(C)=l≥4.
Subcase  1.1. C and C′ have no common vertices.
LetP be the shortest path from C to C′. Suppose P intersects C at vertex u and intersects C′ at vertex v and there are k vertices on P where k≥2. Let G0=C∪P∪C′. Let x and y be any two (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G0 and intersects G0 at vertex x′ and P2 is the shortest path from y to G0 and intersects G0 at vertex y′. Then 0≤l(P1),  l(P2)≤n-l-l′-k+2, where l≥4 and l′≥3. By the proof of Case  1 of Lemma  4.5 in [3], there exists a pair of SSSD walks from x to y of length 2n-2. Therefore, by Lemma 2.6, l(A)≤2n-2.
Subcase  1.2. C and C′ have at least one common vertex.
LetG1=C∪C′. Let x and y be any two (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G1 and intersects G1 at vertex x′ and P2 is the shortest path from y to G1 and intersects G1 at vertex y′. Denote C∩C′ by R. Assume R has m vertices, where 1≤m≤min(l,l′), then
(3.1)0≤l(P1),l(P2)≤n-l-l′+m.
If m≥2, then R is a path with vertex set V(R)={v1,v2,…,vm} and edge set E(R)={(v1,v2),(v2,v3),…,(vm-1,vm)}. In this case, if m=min(l,l′)=l, then there exists another odd cycle with length l′-l+2<l′, which contradicts our assumption that C′ is an odd cycle with the least length in S(A). Therefore, m<l and if m=min(l,l′), then m=l′.
Subcase  1.2.1. x′=y′ and 1≤m≤min(l,l′).
Subcase  1.2.1.1. x′=y′∈C∖R. See Figure 2(a).
We consider two subcases: the subcase1≤m<min(l,l′) and the subcase m=min(l,l′)=l′.
First, we consider the subcase1≤m<min(l,l′). Without loss of generality, we assume that l(QC∖R(x′→v1))≤l(QC∖R(x′→vm)). Let w=l(P1)+l(C)+l(P2). If w is even, set
(3.2)W′=P1+C+P2.
Otherwise, set
(3.3)W′′=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→y′)+P2.
Let
(3.4)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QC′∖R(v1→vm)) and l(QR(v1→vm)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is even,
(3.5)l(W1)=l(W2)≤2(n-l-l′+m)+2l=2n-2l′+2m.
Otherwise,
(3.6)l(W1)=l(W2)≤2(n-l-l′+m)+(l-m+1)+(l′-m+1)+l=2n-l′+2.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Then, we consider the subcasem=min(l,l′)=l′. Without loss of generality, we assume that l(QC∖R(x′→v1))≤l(QC∖R(x′→vm)). Let
(3.7)w=l(P1)+2l(QC∖R(x′→v1))+l(P2).
If w is even, set
(3.8)W′=P1+QC∖R(x′→v1)+QC∖R(v1→x′)+P2.
Otherwise, set
(3.9)W′′=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→x′)+P2.
Let
(3.10)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→x′) is an odd cycle, l(QC∖R(x′→v1)) and l(QC′∖R(v1→vm)+QC∖R(vm→x′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is even,
(3.11)l(W1)=l(W2)≤2(n-l)+(l-l′+1)+l=2n-l′+1.
Otherwise,
(3.12)l(W1)=l(W2)≤2(n-l)+(l-l′+2)+l=2n-l′+2.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.1.2. x′=y′∈C′∖R. See Figure 2(b).
The proof for this subcase is similar to that of the Subcase1.2.1.1 and is omitted.
Subcase  1.2.1.3. x′=y′∈R. See Figure 2(c).
Letw=l(P1)+l(P2). If w is even, set
(3.13)W′=P1+P2.
Otherwise, set
(3.14)W′′=P1+P2+C′.
Let
(3.15)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since l′ is odd, we see that both l(W1) and l(W2) are even. Then, if w is even,
(3.16)l(W1)=l(W2)≤2(n-l-l′+m)+l=2n-l-2l′+2m.
Otherwise,
(3.17)l(W1)=l(W2)≤2(n-l-l′+m)+l′+l=2n-l-l′+2m.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.2. x′≠y′ and 2≤m≤min(l,l′).
Subcase  1.2.2.1. x′∈C∖R and y′∈C∖R. See Figure 3(a).
Without loss of generality, we assume thatl(QC∖R(x′→v1))≤l(QC∖R(y′→v1)). Let w=l(P1)+l(QC∖R(x′→v1))+l(QR(v1→vm))+l(QC∖R(vm→y′))+l(P2). If w is even, set
(3.18)W′=P1+QC∖R(x′→v1)+QR(v1→vm)+QC∖R(vm→y′)+P2.
Otherwise, set
(3.19)W′′=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→y′)+P2.
Let
(3.20)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QC′∖R(v1→vm)) and l(QR(v1→vm)) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC∖R(x′→v1)+QR(v1→vm)+QC∖R(vm→y′) and W4=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→y′) are paths of S(A), we have l(W3),  l(W4)≤n-1. Then
(3.21)l(W1)=l(W2)≤(n-1)+(n-l-l′+m)+l=2n-l′+m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.2.2. x′∈C∖R and y′∈R. See Figure 3(b).
Without loss of generality, we assume thatl(QC∖R(x′→v1))≤l(QC∖R(x′→vm)). Then we consider two subcases: the subcase x′∈C∖R, y′∈R and y′≠v1 and the subcase x′∈C∖R and y′=v1.
First, we consider the subcasex′∈C∖R, y′∈R and y′≠v1. Let w=l(P1)+l(QC∖R(x′→v1))+l(QR(v1→y′))+l(P2). If w is even, set
(3.22)W′=P1+QC∖R(x′→v1)+QR(v1→y′)+P2.
Otherwise, set
(3.23)W′′=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QR(vm→y′)+P2.
Let
(3.24)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QR(v1→y′)) and l(QC′∖R(v1→vm))+l(QR(vm→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC∖R(x′→v1)+QR(v1→y′) and W4=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QR(vm→y′) are two paths of S(A), then we have l(W3),  l(W4)≤n-1. Then
(3.25)l(W1)=l(W2)≤(n-1)+(n-l-l′+m)+l=2n-l′+m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Then, we consider the subcasex′∈C∖R and y′=v1. Let w=l(P1)+l(QC∖R(x′→vm))+l(QR(vm→v1(y′)))+l(P2). If w is even, set
(3.26)W′=P1+QC∖R(x′→vm)+QR(vm→v1(y′))+P2.
Otherwise, set
(3.27)W′′=P1+QC∖R(x′→vm)+QC′∖R(vm→v1(y′))+P2.
Let
(3.28)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QR(vm→v1(y′))) and l(QC′∖R(vm→v1(y′))) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC∖R(x′→vm)+QR(vm→v1(y′)) and W4=P1+QC∖R(x′→vm)+QC′∖R(vm→v1(y′)) are two paths of S(A), we have l(W3),  l(W4)≤n-1. Then
(3.29)l(W1)=l(W2)≤(n-1)+(n-l-l′+m)+l=2n-l′+m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.2.3. x′∈C∖R and y′∈C′∖R. See Figure 3(c).
The proof for this subcase is similar to that of the Subcase1.2.2.1 and is omitted.
Subcase  1.2.2.4. x′∈R and y′∈R. See Figure 3(d).
Letw=l(P1)+l(QC′(x′→y′))+l(P2). If w is even, set
(3.30)W′=P1+QC′(x′→y′)+P2.
Otherwise, set
(3.31)W′′=P1+C′∖QC′(x′→y′)+P2.
Let
(3.32)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QC′(x′→y′)) and l(C′∖QC′(x′→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then if w is even,
(3.33)l(W1)=l(W2)≤2(n-l-l′+m)+l′-12+l=2n+2m-l-3l′2-12.
Otherwise,
(3.34)l(W1)=l(W2)≤2(n-l-l′+m)+(l′-1)+l=2n-l-l′+2m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.2.5. x′∈R and y′∈C′∖R. See Figure 3(e).
The proof for this subcase is similar to that of Subcase1.2.2.4, so we omit it.
Subcase  1.2.2.6. x′∈C′∖R and y′∈C′∖R. See Figure 3(f).
Without loss of generality, we assume thatl(QC′∖R(x′→v1))≤l(QC′∖R(y′→v1)). Let w=l(P1)+l(QC′∖R(x′→v1))+l(QR(v1→vm))+l(QC′∖R(vm→y′))+l(P2). If w is even, set
(3.35)W′=P1+QC′∖R(x′→v1)+QR(v1→vm)+QC′∖R(vm→y′)+P2.
Otherwise, set
(3.36)W′′=P1+QC′∖R(x′→y′)+QC′∖R(y′→vm)+QC′∖R(vm→y′)+P2.
Let
(3.37)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(QC′∖R(x′→y′)) and l(QC′∖R(x′→v1))+l(QR(v1→vm))+l(QC′∖R(vm→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC′∖R(x′→v1)+QR(v1→vm)+QC′∖R(vm→y′) and W4=P1+QC′∖R(x′→y′)+QC′∖R(y′→vm) are two paths of S(A), then we have l(W3)≤n-1 and l(W4)≤n-m. Then, if w is even,
(3.38)l(W1)=l(W2)≤(n-1)+(n-l-l′+m)+l=2n-l′+m-1.
Otherwise,
(3.39)l(W1)=l(W2)≤(n-l-l′+m)+(n-m)+(l′-m-1)+l=2n-m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.3. m=1 and x′≠y′. We assume that V(C)∩V(C′)={u}.
Subcase  1.2.3.1. x′∈C and y′∈C. See Figure 4(a).
Letw=l(P1)+l(QC(x′→u))+l(QC(u→y′))+l(P2). If w is even, set
(3.40)W′=P1+QC(x′→u)+QC(u→y′)+P2.
Otherwise, set
(3.41)W′′=P1+QC(x′→u)+QC(u→y′)+P2+C′.
Let
(3.42)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since l′ is odd, both l(W1) and l(W2) are even. Then, if w is even,
(3.43)l(W1)=l(W2)≤2(n-l-l′+1)+(l-1)+l=2n-2l′+1.
Otherwise,
(3.44)l(W1)=l(W2)≤2(n-l-l′+1)+(l-1)+l′+l=2n-l′+1.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.3.2. x′∈C, y′∈C′, and x′≠y′≠u. See Figure 4(b).
Letw=l(P1)+l(QC(x′→u))+l(QC′(u→y′))+l(P2). If w is even, set
(3.45)W′=P1+QC(x′→u)+QC′(u→y′)+P2.
Otherwise, set
(3.46)W′′=P1+QC(x′→u)+C′∖QC′(u→y′)+P2.
Let
(3.47)W1={W′+C,wiseven,W′′+C,otherwise,W2={W′+l2C2,wiseven,W′′+l2C2,otherwise,
where C2 is a positive 2-cycle that contains vertex x. Since C′ is odd, l(C′∖QC′(u→y′)) and l(QC′(u→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC(x′→u)+QC′(u→y′) and W4=P1+QC(x′→u)+C′∖QC′(u→y′) are two paths of S(A), we have l(W3),  l(W4)≤n-1. Then,
(3.48)l(W1)=l(W2)≤(n-1)+(n-l-l′+1)+l=2n-l′.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2.3.3. x′∈C′ and y′∈C′. See Figure 4(c).
The proof for this subcase is similar to that of the Subcase1.2.3.1 and is omitted.
Thus in each of the above subcases, there exists a pair of SSSD walks fromx to y with length 2n-2. Therefore, we get l(A)≤2n-2 by Lemma 2.6.
Case  2. There exists no negative even cycle in S(A).
SinceA is primitive, nonpowerful and there exist no negative even cycles in S(A), it follows from Lemma 2.5 that there exist two odd cycles C and C′ with different signs in S(A). We assume that l(C)=l and l(C′)=l′. Since the trace of A is zero, there are no loops in S(A) and so l,  l′≥3. Without loss of generality, we assume l≥l′≥3.
Subcase  2.1. C and C′ have no common vertices.
LetP be the shortest path from C to C′. Suppose P intersects C at vertex u and intersects C′ at vertex v and there are k vertices on P where k≥2. Let G2=C∪P∪C′. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G2 and intersects G2 at vertex x′ and P2 is the shortest path from y to G2 and intersects G2 at vertex y′. Then
(3.49)0≤l(P1),l(P2)≤n-l-l′-k+2.
Since C and C′ have diffident signs, if there exists an even walk W with length l(W)≤2n-2-l, then W1=W+C and W2=W+((l-l′)/2)C2+C′ have the same length l(W1)=l(W2)≤2n-2 and different signs. As the proof of Subcase  1.1, we can construct an even walk W with length l(W)≤2n-2-l. So there exists a pair of SSSD walks from x to y of length 2n-2. It remains to consider the following subcase.
Subcase  2.2. C and C′ have at least one common vertex.
LetG3=C∪C′. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G3 and intersects G3 at vertex x′ and P2 is the shortest path from y to G3 and intersects G3 at vertex y′. Denote C∩C′ by R. Assume R has m vertices, where 1≤m≤min(l1,l2), then
(3.50)0≤l(P1),l(P2)≤n-l1-l2+m.
If m>1, then R is a path with vertex set V(R)={v1,v2,…,vm} and edge set E(R)={(v1,v2),(v2,v3),…,(vm-1,vm)}. If m=l′, since there exists no negative even cycles in S(A), then C and C′ have the same sign, a contradiction. Therefore, 1≤m<l′.
Subcase  2.2.1. x′∈C∖R and y′∈C∖R. See Figure 3(a).
Without loss of generality, we assume thatl(QC∖R(x′→v1))≤l(QC∖R(y′→v1)). Let w=l(P1)+l(QC∖R(x′→v1))+l(QR(v1→vm))+l(QC∖R(vm→y′))+l(P2). If w is odd, set
(3.51)W′=P1+QC∖R(x′→v1)+QR(v1→vm)+QC∖R(vm→y′)+P2.
Otherwise, set
(3.52)W′′=P1+QC∖R(x′→v1)+QC′∖R(v1→vm)+QC∖R(vm→y′)+P2.
Let
(3.53)W1={W′+C,wisodd,W′′+C,otherwise,W2={W′+C′+l-l′2C2,wisodd,W′′+C′+l-l′2C2,otherwise,
where C2 is a positive 2-cycle that contains x. Since C′ is odd, l(QR(v1→vm)) and l(QC′∖R(v1→vm)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.54)l(W1)=l(W2)≤2(n-l-l′+m)+l+l=2n-2l′+2m.
Otherwise,
(3.55)l(W1)=l(W2)≤2(n-l-l′+m)+(l-m+1)+(l′-m+1)+l=2n-l′+2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  2.2.2. x′∈C∖R and y′∈R. See Figure 3(b).
Letw=l(P1)+l(QC(x′→y′))+l(P2). If w is odd, set
(3.56)W′=P1+QC(x′→y′)+P2.
Otherwise, set
(3.57)W′′=P1+C∖QC(x′→y′)+P2.
Let
(3.58)W1={W′+C,wisodd,W′′+C,otherwise,W2={W′+C′+l-l′2C2,wisodd,W′′+C′+l-l′2C2,otherwise,
where C2 is a positive 2-cycle that contains x. Since C is odd, C∖QC(x′→y′) and QC(x′→y′) have different parity, Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.59)l(W1)=l(W2)≤2(n-l-l′+m)+l-12+l=2n-2l′+2m-l+12.
Otherwise,
(3.60)l(W1)=l(W2)≤2(n-l-l′+m)+(l-1)+l=2n-2l′+2m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  2.2.3. x′∈C∖R and y′∈C′∖R. See Figure 3(c).
Without loss of generality, we assume thatl(QC∖R(x′→v1))≤l(QC∖R(x′→vm)). Let w=l(P1)+l(QC∖R(x′→v1))+l(QC′∖R(v1→y′))+l(P2). If w is odd, set
(3.61)W′=P1+QC∖R(x′→v1)+QC′∖R(v1→y′)+P2.
Otherwise, set
(3.62)W′′=P1+QC∖R(x′→v1)+QR(v1→vm)+QC′∖R(vm→y′)+P2.
Let
(3.63)W1={W′+C,wisodd,W′′+C,otherwise,W2={W′+C′+l-l′2C2,wisodd,W′′+C′+l-l′2C2,otherwise,
where C2 is a positive 2-cycle that contains x. Since C′ is odd, l(QC′∖R(v1→y′)) and l(QR(v1→vm))+l(QC′∖R(vm→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Noting that W3=P1+QC∖R(x′→v1)+QC′∖R(v1→y′) and W4=P1+QC∖R(x′→v1)+QR(v1→vm)+QC′∖R(vm→y′) are paths of S(A), then we have l(W3),  l(W4)≤n-1. Therefore,
(3.64)l(W1)=l(W2)≤(n-1)+(n-l-l′+m)+l=2n-l′+m-1.
Since both l(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  2.2.4. x′∈R and y′∈R. See Figure 3(d).
The proof for this subcase is similar to that of Subcase2.2.2, so we omit it.
Subcase  2.2.5. x′∈R and y′∈C′∖R. See Figure 3(e).
The proof for this subcase is similar to that of Subcase2.2.2, so we omit it.
Subcase  2.2.6. x′∈C′∖R and y′∈C′∖R. See Figure 3(f).
The proof for this subcase is similar to that of Subcase2.2.1, so we omit it.
From all the above subcases, there exists a pair of SSSD walks fromx to y with length 2n-2. Therefore, we get l(A)≤2n-2 by Lemma 2.6.Illustrate for Subcase1.2.1 of Lemma 3.1.
(a)
(b)
(c)Illustration for Subcases1.2.2 and 2.2 of Lemma 3.1.
(a)
(b)
(c)
(d)
(e)
(f)Illustrate for Subcase1.2.3 of Lemma 3.1.
(a)
(b)
(c)Lemma 3.2.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. If there exist a negative 2-cycle and a positive 2-cycle in S(A), then l(A)≤2n-2.Proof.
SinceA is primitive, it follows from Lemma 2.4 that S(A) is strongly connected and there is an odd cycle C in S(A) with length l(C)=l. Since A has zero diagonal, there are no loops in S(A) and so l≥3. Without loss of generality, we assume that C is an odd cycle with the least length in S(A). Since A is ZS and S(A) contain a positive 2-cycle and a negative 2-cycle, there exists a positive 2-cycle C2′ and a negative 2-cycle C2′′ such that V(C2′)∩V(C2′′)≠∅. Let u∈V(C2′)∩V(C2′′).
LetP be the shortest path from u to C. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose there are k vertices on P and P intersects C at v, where k≥1. Suppose P1 is the shortest path from x to P∪C and P1 intersects P∪C at x′ and P2 is the shortest path from y to P∪C and P2 intersects P∪C at y′ where 0≤l(P1),  l(P2)≤n-l-k+1. We consider the following three cases.
Case  1. x′∈P and y′∈P.
By the Subcase 2.1 of Lemma  4.2 in [3], there exists a pair of SSSD walks from x to y of length 2n-2.
Case  2. Only one of x′ and y′ belongs to P.
By the Subcase2.2 of Lemma  4.2 in [3], there exists a pair of SSSD walks from x to y of length 2n-2.
It remains to consider the following case.
Case  3. x′∉P and y′∉P. See Figure 5.
Subcase  3.1. x′=y′.
Letw=l(P1)+l(QC(x′→v))+2l(P)+l(QC(v→y′))+l(P2). If w is even, set
(3.65)W′=P1+QC(x′→v)+2P+QC(v→y′)+P2.
Otherwise, set
(3.66)W′′=P1+QC(x′→v)+2P+C∖QC(v→y′)+P2.
Let
(3.67)W1={W′+C2′,wiseven,W′′+C2′,otherwise,W2={W′+C2′′,wiseven,W′′+C2′′,otherwise.
Since C is odd, l(QC(v→x′)) and l(C∖QC(v→x′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.68)l(W1)=l(W2)≤2(n-l-k+1)+2(k-1)+(l-1)+2=2n-l+1.
Otherwise,
(3.69)l(W1)=l(W2)≤2(n-l-k+1)+2(k-1)+l+2=2n-l+2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  3.2. x′≠y′.
Without loss of generality, we assume thatl(QC(x′→v))≤l(QC(y′→v)). Let P3=QC(x′→v) and P4=QC∖P3(v→y′). Let w=l(P1)+l(P3)+l(P4)+2l(P)+l(P2), If w is odd, set
(3.70)W′=P1+QC(x′→v)+2P+P4+P2.
Otherwise, set
(3.71)W′′=P1+QC(x′→v)+2P+QC(v→x′)+QC∖{P3+P4}(x′→y′)+P2.
Let
(3.72)W1={W′+C2′,wiseven,W′′+C2′,otherwise,W2={W′+C2′′,wiseven,W′′+C2′′,otherwise.
Since C is odd, l(P3)+l(P4) and l(QC∖{P3+P4}(x′→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.73)l(W1)=l(W2)≤2(n-l-k+1)+2(k-1)+(l-1)+2=2n-l+1.
Otherwise,
(3.74)l(W1)=l(W2)≤2(n-l-k+1)+2(k-1)+(l-1)+(l-2)+2=2n-1.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Therefore,l(A)≤2n-2 by Lemma 2.6.Figure 5
Illustration for Case 3 of Lemma3.2.Lemma 3.3.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. If l(A)=2n-1, then all 2-cycles in S(A) are negative.Proof.
Assume thatl(A)=2n-1. By Lemma 3.1, S(A) has at least one negative 2-cycle. It then follows from Lemma 3.2 that all 2-cycles in S(A) are negative.Lemma 3.4.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. Suppose that l(A)=2n-1. Then there exists an odd cycle C in S(A) and C is the only cycle of length at least 3 in S(A).Proof.
SinceA is primitive, it follows from Lemma 2.4 that S(A) is strongly connected and there is an odd cycle C=(v1,v2,…,vl) in S(A) with length l(C)=l. Since A has zero diagonal, there is no loop in S(A) and so l≥3. Consider the following two directed cycles:
(3.75)C1=(v1,v2,…,vl,v1),C2=(v1,vl,…,v2,v1).
Since there exists no positive 2-cycle in S(A) by Lemma 3.3, the arcs (vi,vi+1) and (vi+1,vi) have different signs. Thus sgn(C1)=-sgn(C2) by the fact that l is odd. Without loss of generality, we assume that C is an odd cycle with the least length in S(A).
Ifl(A)=2n-1, suppose there exists another cycle C′ with length l(C′)=l′≥3, we consider the following two cases.
Case  1. C and C′ have no common vertices.
LetP be the shortest path from C to C′. Suppose P intersects C at vertex u and intersects C′ at vertex v and there are k vertices on P where k≥2. Let G4=C∪P∪C′. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G4 and intersects G4 at vertex x′ and P2 is the shortest path from y to G4 and intersects G4 at vertex y′. Then
(3.76)0≤l(P1),l(P2)≤n-l-l′-k+2.
We consider the following six subcases.
Subcase  1.1. x′∈C and y′∈C. See Figure 6(a).
Letw=l(P1)+l(QC(x′→y′))+l(P2). If w is odd, set
(3.77)W′=P1+QC(x′→y′)+P2.
Otherwise, set
(3.78)W′′=P1+C∖QC(x′→y′)+P2.
Let
(3.79)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, l(QC(x′→y′)) and l(C∖QC(x′→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.80)l(W1)=l(W2)≤2(n-l-l′-k+2)+l-12+l=2n-2l′-2k-l2+72.
Otherwise,
(3.81)l(W1)=l(W2)≤2(n-l-l′-k+2)+l+l=2n-2l′-2k+4.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.2. x′∈C and y′∈P. See Figure 6(b).
LetW=l(P1)+l(QC(x′→u))+l(QP(u→y′))+l(P2). If w is odd, set
(3.82)W′=P1+QC(x′→u)+QP(u→y′)+P2.
Otherwise, set
(3.83)W′=P1+C∖QC(x′→u)+QP(u→y′)+P2.
Let
(3.84)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, l(QC(x′→u)) and l(C∖QC(x′→u)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.85)l(W1)=l(W2)≤2(n-l-l′-k+2)+l-12+(k-1)+l=2n-2l′-k-l2+52.
Otherwise,
(3.86)l(W1)=l(W2)≤2(n-l-l′-k+2)+(k-1)+l+l=2n-2l′-k+3.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.3. x′∈C and y′∈C′. See Figure 6(c).
Letw=l(P1)+l(QC(x′→u))+l(P)+l(QC′(v→y′))+l(P2). If w is odd, set
(3.87)W′=P1+QC(x′→u)+P+QC′(v→y′)+P2.
Otherwise, set
(3.88)W′′=P1+C∖QC(x′→u)+P+QC′(v→y′)+P2.
Let
(3.89)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, l(QC(x′→u)) and l(C∖QC(x′→u)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.90)l(W1)=l(W2)≤2(n-l-l′-k+2)+l-12+(k-1)+l′2+l=2n-k-l2-3l′2+52.
Otherwise,
(3.91)l(W1)=l(W2)≤2(n-l-l′-k+2)+l+(k-1)+l′2+l=2n-k-3l′2+3.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.4. x′∈P and y′∈P. See Figure 6(d).
Without loss of generality, we assume thatl(QP(x′→u))≤l(QP(y′→u)). Let w=l(P1)+l(QP(x′→u))+l(P)+l(QP(v→y′))+l(P2). If w is odd, set
(3.92)W′=P1+QP(x′→u)+P+QP(v→y′)+P2.
Otherwise, set
(3.93)W′′=P1+QP(x′→u)+P+QP(v→y′)+P2+C.
Let
(3.94)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.95)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l=2n-l-2l′+2.
Otherwise,
(3.96)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l+l=2n-2l′+2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.5. x′∈P and y′∈C′. See Figure 6(e).
Letw=l(P1)+l(QP(x′→u))+l(P)+l(QC′(v→y′))+l(P2), if w is odd, set
(3.97)W′=P1+QP(x′→u)+P+QC′(v→y′)+P2.
Otherwise, set
(3.98)W′′=P1+QP(x′→u)+P+QC′(v→y′)+P2+C.
Let
(3.99)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, both l(W1) and l(W2) are even. Then, if w is odd,
(3.100)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l′2+l=2n-l-3l′2+2.
Otherwise,
(3.101)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l′2+l+l=2n-3l′2+2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  1.6. x′∈C′ and y′∈C′. See Figure 6(f).
Letw=l(P1)+l(QC′(x′→v))+l(QC′(v→y′))+2l(P)+l(P2). If w is odd, set
(3.102)W′=P1+QC′(x′→v)+2P+QC′(v→y′)+P2.
Otherwise, set
(3.103)W′′=P1+QC′(x′→v)+2P+QC′(v→y′)+P2+C.
Let
(3.104)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, both l(W1) and l(W2) are even. Then if w is odd,
(3.105)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l′+l=2n-l-l′+2.
Otherwise,
(3.106)l(W1)=l(W2)≤2(n-l-l′-k+2)+2(k-1)+l′+l+l=2n-l′+2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Therefore,l(A)≤2n-2 by Lemma 2.6, a contradiction.
Case  2. C and C′ have at least one common vertex.
LetG5=C∪C′. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to G5 and intersects G5 at vertex x′ and P2 is the shortest path from y to G5 and intersects G5 at vertex y′. Denote C∩C′ by R. Assume R has m vertices, where 1≤m≤min(l1,l2), then
(3.107)0≤l(P1),l(P2)≤n-l1-l2+m.
If m>1, then R is a path with vertex set V(R)={v1,v2,…,vm} and edge set E(R)={(v1,v2),(v2,v3),…,(vm-1,vm)}. If l′ is odd, m=min(l,l′)=l by the minimality of C. If l′ is even, suppose min(l,l′)=l′, then there exists an odd cycle C′ with l(C′)<l which contradicts our assumption that C is an odd cycle with the least length in S(A). Therefore, if m=min(l,l′), then m=l<l′. We consider the following three subcases.
Subcase  2.1. x′∈C and y′∈C.
Letw=l(P1)+l(QC(x′→y′))+l(P2). If w is odd, set
(3.108)W′=P1+QC(x′→y′)+P2.
Otherwise, set
(3.109)W′′=P1+C∖QC(x′→y′)+P2.
Let
(3.110)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, l(QC(x′→y′)) and l(C∖QC(x′→y′)) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.111)l(W1)=l(W2)≤2(n-l-l′+m)+l-12+l=2n-2l′+2m-l2-12.
Otherwise,
(3.112)l(W1)=l(W2)≤2(n-l-l′+m)+l+l=2n-2l′+2m.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  2.2. x′∈C∖R and y′∈C′∖R.
Without loss of generality, we assume thatl(QC∖R(x′→v1))≤l(QC∖R(x′→vm)). Let w=l(P1)+l(QC∖R(x′→v1))+l(QC′∖R(v1→y′))+l(P2). If w odd, set
(3.113)W′=P1+QC∖R(x′→v1)+QC′∖R(v1→y′)+P2.
Otherwise, set
(3.114)W′′=P1+QC∖R(x′→vm)+QR(vm→v1)+QC′∖R(v1→y′)+P2.
Let
(3.115)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, l(QC∖R(x′→v1)) and l(QC∖R(x′→vm))+l(QR(vm→v1)) have different parity. Therefore, both l(W1) and l(W2) are even.
Then, ifw is odd,
(3.116)l(W1)=l(W2)≤2(n-l-l′+m)+(l-m+1)+(l′-m+1)+l=2n-l′+2.
Otherwise,
(3.117)l(W1)=l(W2)≤2(n-l-l′+m)+(l-m)+(l′-1)+l=2n-l′+m-1.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Subcase  2.3. x′∈C′∖R and y′∈C′∖R.
The verification for this subcase is similar to that of the Subcase 2.2 and is omitted.
Therefore,l(A)≤2n-2 by Lemma 2.6, a contradiction.Illustration for Lemma3.4.
(a)
(b)
(c)
(d)
(e)
(f)Lemma 3.5.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. If l(A)=2n-1, then S(A) is isomorphic to G (see Figure 1).Proof.
LetA be an n×n primitive nonpowerful ZS sign pattern matrix with zero diagonal. Since A is primitive, it follows from Lemma 2.4 that S(A) is strongly connected and there is an odd cycle C=(v1,v2,…,vl) in S(A) with length l(C)=l. Since A has zero diagonal, there is no loop in S(A) and so 3≤l≤n. Without loss of generality, we assume that C is an odd cycle with the least length in S(A). If l(A)=2n-1, then by Lemma 3.3, there exists no positive 2-cycle in S(A). Then S(A) is isomorphic to G by Lemma 2.7. We will give anther proof of the theorem.
Denote the vertex set ofS(A) by V and the vertex set of C by V′. By Lemmas 3.4 and 3.3, the cycle C is the only cycle of length at least 3 in S(A) and there exists no positive 2-cycle in S(A). Consider the two directed cycles C1=(v1,v2,…,vl,v1) and C2=(v1,vl,…,v2,v1). Since there exists no positive 2-cycle in S(A), the arcs (vi,vi+1) and (vi+1,vi) have different signs. Thus sgn(C1)=-sgn(C2) by the fact that l is odd. Let x and y be two arbitrary (not necessarily distinct) vertices in S(A). Suppose that P1 is the shortest path from x to C and intersects C at vertex x′ and P2 is the shortest path from y to C and intersects C at vertex y′. If l=n, S(A) is isomorphic to an odd cycle of length n. If l<n, it is enough to show that there exists a vertex u∉V′ in S(A) such that l(P)=n-l where P is the shortest path from u to C and P intersects C at v. Suppose not, then
(3.118)l(P1),l(P2)≤n-l-1.
Now we consider the following three cases.
Case  1. x∈V∖V′ and y∈V∖V′.
Letw=l(P1)+l(QC(x′→y′))+l(P2)). If w is odd, set
(3.119)W′′=P1+QC(x′→y′)+P2.
Otherwise, set
(3.120)W′=P1+C∖QC(x′→y′)+P2.
Let
(3.121)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, QC(x′→y′) and C∖QC(x′→y′) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.122)l(W1)=l(W2)≤2(n-l-1)+l-12+l=2n-l2-52.
Otherwise,
(3.123)l(W1)=l(W2)≤2(n-l-1)+l+l=2n-2.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Case  2. x∈V∖V′ and y∈V.
In this case,y′=y. Let w=l(P1)+l(QC(x′→y)). If w is odd, set
(3.124)W′′=P1+QC(x′→y).
Otherwise, set
(3.125)W′=P1+C∖QC(x′→y).
Let
(3.126)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, QC(x′→y) and C∖QC(x′→y) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.127)l(W1)=l(W2)≤(n-l-1)+l-12+l=n+l2-32.
Otherwise,
(3.128)l(W1)=l(W2)≤(n-l-1)+l+l=n+l-1.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
Case  3. x∈V and y∈V.
In this case,x′=x and y′=y. Let w=QC(x→y). If w is odd, set
(3.129)W′′=QC(x→y).
Otherwise, set
(3.130)W′=C∖QC(x→y).
Let
(3.131)W1={W′+C1,wisodd,W′′+C1,otherwise,W2={W′+C2,wisodd,W′′+C2,otherwise.
Since C is odd, QC(x→y) and C∖QC(x→y) have different parity. Therefore, both l(W1) and l(W2) are even. Then, if w is odd,
(3.132)l(W1)=l(W2)≤l-12+l=3l2-12.
Otherwise,
(3.133)l(W1)=l(W2)≤l+l=2l.
Since bothl(W1) and l(W2) are even, it follows that l(W1)=l(W2)≤2n-2. We see that the pair W1, W2 is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks from x to y with length 2n-2.
From all the above cases, there exists a pair of SSSD walks fromx to y with length 2n-2, therefore, l(A)≤2n-2 by Lemma 2.6, a contradiction.Proof of Theorem1.6.
We getl(A)≤2n-1 from Theorem 2.2. Suppose that A is nonpowerful and skew symmetric and S(A) is isomorphic to G. Then l(A)=2n-1 by Lemma 2.7.
Conversely, suppose thatl(A)=2n-1. We need to prove that A is nonpowerful and skew symmetric and S(A) is isomorphic to G. In [1], Li et al. showed that if an irreducible sign pattern matrix A is powerful, then l(A)=l(|A|). Therefore, if A is powerful, then l(A)≤2n-4 by Theorem 2.1, which contradicts l(A)=2n-1. Hence A is nonpowerful. Consequently, A is skew symmetric by Lemma 3.3 and S(A) is isomorphic to G by Lemma 3.5.



---

*Source: 276386-2012-12-31.xml*