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

(1)

Volume 2012, Article ID 276386,28pages doi:10.1155/2012/276386

Research Article

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

Ling Zhang,

¹

Ting-Zhu Huang,

¹

and Zhongshan Li

^{2, 3}

1School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, Sichuan 61173, China

2Department of Mathematics, North University of China, Taiyuan, Shanxi 030051, China

3Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30302-4110, USA

Correspondence should be addressed to Ling Zhang,lvjinliang415@163.com Received 1 March 2012; Accepted 1 December 2012

Academic Editor: Nicola Guglielmi

Copyrightq2012 Ling Zhang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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.

1. Introduction

A sign pattern matrixor sign patternAis a matrix whose entries are from the set{1,−1,0}.

Notice that for a square sign pattern matrixA, in the computation ofthe signs ofthe entries of the powerA^k, an ambiguous sign may arise when a positive sign is added to a negative sign. So a new symbol # was introduced in1to 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 11 −1 #; a## ∀a∈Γ,

0·##·0; b·##·b# ∀b∈Γ\ {0}. 1.1

(2)

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 matrixAis called powerful if each power of Acontains no # entry.

In1, Li et al. introduced the concepts of base and period forpowerfulsign pattern matrices which are the generalizations of the concepts of “index of convergence” and period for square nonnegative matrices. These concepts are extended frompowerfulsign pattern matrices tosquaregeneralized sign pattern matrices by You et al. in12as follows.

Definition 1.2see12. LetAbe a square generalized sign pattern matrix of ordernand A, A², A³, . . .the sequence of powers ofA.Since there are only 4ⁿ²diﬀerent generalized sign patterns of ordern, there must be repetitions in the sequence.SupposeA^lis the first power that is repeated in the sequence, that is,lis the least positive integer such thatA^lA^lpholds for some positive integerp. Thenlis called the generalized baseor simply baseofA, and is denoted bylA. The least positive integerpsuch thatA^lA^lpholds forllAis called the generalized periodor simply periodofAand is denoted bypA.

For a sign pattern matrixA, we use|A|to denote the0,1matrix obtained fromAby replacing each nonzero entry by 1.

A nonnegative square matrixA is primitive if some power A^k > 0. The least such as k is called the primitive exponent or simply exponent of A, denoted by expA. For convenience, a square sign pattern matrixAis called primitive if|A|is primitive, and in this case we define expA exp|A|.

Definition 1.3 see 3. A square sign pattern matrix A aij_n×n is called zero-pattern symmetricabbreviated zero-symmetric, or simply ZSif|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.

Let D 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 digraphD, we obtain a signed digraphS. By a walkW in the digraphDor the signed digraphS, we mean a sequence of verticesv0, v1, v2, . . . , vksuch thatei vi−1, viis an arc ofDfori1, . . . , k. The numberk is called the length of the walkW, denoted bylW. If the verticesv0, v1, . . . , v_k−1are distinct, the walkWis called a path, ifvkv0, the pathWis called a cycle inDand inS. The sign of the walkWinS, denoted by sgnW, is defined to be_k

i1sgneiwhere sgneiis the sign of the arce_i.

LetA aijbe a sign pattern matrix of ordern. Then the associated digraphDA ofAis defined to be the digraph with vertex setV {1,2, . . . , n}and arc setE {vi, vj | a_ij/0}. The associated signed digraphSAis obtained fromDAby assigning the sign of aijto each arcvi, vjinDA.

Definition 1.4see10. LetDbe a digraphpermitting loops but no multiple arcs. Digraph Dis called primitive if there is a positive integerksuch that for all ordered pairs of vertices viandvjnot necessarily distinctinD, there exists a walk of lengthkfromvitovj. The least suchkis called the primitive exponent ofD, denoted by expD.

It is well known that a digraphD is primitive if and only ifD is strongly connected and the greatest common divisor gcd for short of the lengths of all the cycles ofD is 1 see13.

(3)

νr−2 νr

νr

−1

ν2 ν1

νr+1 · · · νn

Figure 1: The graphG.All 2-cycles inGare negative,ris odd, 3≤r≤n.

Definition 1.5 see3. LetS be a signed digraph of order n. Then there is a sign pattern matrixAof ordernwhose associated signed digraphSAisS. We say thatSis powerful if Ais powerful. Also we definelS lA.

We say that a sign pattern matrix A a_ij has zero diagonal if a_ii 0 for all i. A digraphDwith vertex set{v1, . . . , v_n}and arc setEis called symmetric provided thatv_i, v_j∈ E iﬀ vj, vi ∈ E for alli, j. It is clear that a sign pattern matrix A is ZS iﬀ its associated digraphDAis symmetric. For simplicity, we represent a symmetricsigneddigraph 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, in3,10. In2, 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 a_ijbe ann×nprimitive zero-symmetric sign pattern matrix with zero diagonal. Then

lA≤2n−1 1.2

and the equality holds if and only ifAis nonpowerful and skew symmetric, namely,a_ij −a_jifor all 1≤i≤j≤n, and the associated digraphDAis isomorphic toG(seeFigure 1).

The proof ofTheorem 1.6will be given inSection 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 inSection 3.

In1, Li et al. showed that if an irreducible sign pattern matrixAis powerful, then lA l|A|. That is to say the study of the base for a primitive powerful sign pattern matrix is essentially the study of the basei.e., exponentfor primitive0,1matrices. Therefore, for a primitive powerful ZS sign pattern matrix with zero diagonal,Theorem 2.1gives the base.

Theorem 2.1see8. LetAbe ann×nprimitive symmetric0,1matrix with zero diagonal. Then expA≤2n−4 and the primitive exponent set ofn×nprimitive symmetric0,1matrix with zero diagonal is{2,3, . . . ,2n−4} \D, whereDis the set of odd numbers in{n−2, n−1, . . . ,2n−5}.

(4)

Theorem 2.2see10. LetAbe ann×nprimitive ZS sign pattern matrix with zero diagonal.

ThenlA≤2n−1.

By Theorems2.1and2.2, the sign pattern matrices with zero diagonal attaining this upper boundlA 2n−1 must be nonpowerful. So it remains to consider nonpowerful sign pattern matrices with zero diagonal.

Definition 2.3. Two walksW1 andW2 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 diﬀerent signs.

Lemma 2.4see8. LetDbe a symmetric digraph. ThenDis primitive if and only ifDis strongly connected and there exists an odd cycle inD.

Lemma 2.5see1,12. IfSis a primitive signed digraph, then Sis nonpowerful if and only ifS contains a pair of cyclesC1andC2, with lengthsp1andp2, respectively, satisfying one of the following conditions:

A1 p1is odd andp2is even and sgnC2 −1;

A2 bothp1andp2are odd and sgnC1 −sgnC2.

Lemma 2.6see12. LetSbe a primitive, nonpowerful signed digraph. Then we have the following.

1There is an integerksuch that there exists a pair of SSSD walks of lengthkfrom each vertex xto each vertexyinS.

2If there exists a pair of SSSD walks of lengthk from each vertexxto each vertexy, then there also exists a pair of SSSD walks of lengthk1 from each vertexuto each vertexvin S.

3The minimal suchk(as in (1)) is justlS, the base ofS.

Lemma 2.7see7. Suppose that ann×nsign pattern matrixA aijis skew symmetric. Let SAbe the associated signed digraph ofA. Letr be an odd integer with 3 ≤ r ≤ n(n ≥ 3). Then lSA 2n−1 if and only ifSAis isomorphic toG(seeFigure 1).

3. Main Results

For an undirected walkWof graphGand two verticesx,yonW, we denote byQWx → y a shortest path fromxtoyonW and byQx → ya shortest path fromxtoyonG. For a cycleCofG, ifxandyare twonot necessarily distinctvertices onCandPis a path fromx toyalongC, thenC\P denotes the path or cycle fromxtoyalongCobtained by deleting the edges ofP.

Lemma 3.1. LetAbe ann×nprimitive nonpowerful ZS sign pattern matrix with zero diagonal. If all the 2 cycles inSAare positive, thenlA≤2n−2.

Proof. SinceAis primitive, it follows fromLemma 2.4thatSAis strongly connected and there is an odd cycleCinSAsuch thatlC l. SinceAhas zero diagonal, there are no loops inSAand sol≥3. Without loss of generality, we assume thatCis an odd cycle with the least length inSA.

(5)

Case 1. There exists at least one negative even cycle inSA.

LetCbe a negative even cycle inSA. Without loss of generality, we assume thatC is a negative even cycle with the least length inSA. Since all 2 cycles inSAare positive, lC l≥4.

Subcase 1.1.CandChave no common vertices.

Let P be the shortest path from C to C. Suppose P intersects C at vertex u and intersects Cat vertex vand there are k vertices on P wherek ≥ 2. LetG0 C∪P ∪C. Let xand y be any twonot necessarily distinctvertices in SA. Suppose thatP1 is the shortest path fromxtoG0and intersectsG0at vertexxandP2is the shortest path fromyto G0and intersectsG0at vertexy. Then 0≤lP1,lP2≤n−l−l−k2, wherel≥4 andl≥3.

By the proof of Case 1 of Lemma 4.5 in3, there exists a pair of SSSD walks fromxtoyof length 2n−2. Therefore, byLemma 2.6,lA≤2n−2.

Subcase 1.2.CandChave at least one common vertex.

LetG1 C∪C. Let xandybe any twonot necessarily distinctvertices inSA.

Suppose thatP1is the shortest path fromxtoG1and intersectsG1at vertexxandP2is the shortest path fromytoG1and intersectsG1at vertexy. DenoteC∩CbyR. AssumeRhas mvertices, where 1≤m≤minl, l, then

0≤lP1, lP2≤n−l−lm. 3.1

If m ≥ 2, then R is a path with vertex set VR {v1, v2, . . . , v_m} and edge set ER {v1, v2,v2, v3, . . . ,v_m−1, v_m}. In this case, ifm minl, l l, then there exists another odd cycle with lengthl−l2< l, which contradicts our assumption thatCis an odd cycle with the least length inSA. Therefore,m < land ifmminl, l, thenml.

Subcase 1.2.1.xyand 1≤m≤minl, l. Subcase 1.2.1.1.xy∈C\R. SeeFigure 2a.

We consider two subcases: the subcase 1 ≤ m < minl, l and the subcase m minl, l l.

First, we consider the subcase 1≤m <minl, l. Without loss of generality, we assume thatlQ_C\Rx → v1≤lQ_C\Rx → v_m. LetwlP1 lC lP2. Ifwis even, set

WP1CP2. 3.2

Otherwise, set

WP1Q_C\R

x−→v1

Q_C_\Rv1 −→v_m Q_C\R

v_m−→y

P2. 3.3 Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.4

(6)

whereC2is a positive 2-cycle that contains vertexx. SinceCis odd,lQC\Rv1 → vmand lQ_Rv1 → v_mhave diﬀerent parity. Therefore, bothlW1andlW2are even. Then, ifw is even,

lW1 lW2≤2

n−l−lm

2l2n−2l2m. 3.5

Otherwise,

lW1 lW2≤2

n−l−lm

l−m1

l2n−l2. 3.6

Since bothlW1andlW2are even, it follows thatlW1 lW2≤2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Then, we consider the subcasemminl, l l. Without loss of generality, we assume thatlQC\Rx → v1≤lQC\Rx → vm. Let

wlP1 2l Q_C\R

x−→v1

lP2. 3.7

Ifwis even, set

WP1QC\R

x−→v1

QC\R

v1 −→x

P2. 3.8

Otherwise, set

WP1QC\R

x−→v1

QC\Rv1−→vm QC\R

vm−→x

P2. 3.9

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.10 whereC2is a positive 2-cycle that contains vertexx. SinceQ_C\Rx → v1Q_C_\Rv1 → v_m QC\Rvm → xis an odd cycle,lQC\Rx → v1andlQC\Rv1 → vm QC\Rvm → x have diﬀerent parity. Therefore, bothlW1andlW2are even. Then, ifwis even,

lW1 lW2≤2n−l

l−l1

l2n−l1. 3.11

Otherwise,

lW1 lW2≤2n−l

l−l2

l2n−l2. 3.12

(7)

y x

P2 P1

C C^′

x^′(y^′)

ν1

νm

a

C

y x

P2 P1

C^′

x^′(y^′)

ν1

νm

b

C

y x

P2

P1

C^′ x^′(y^′)

ν1

νm

c Figure 2: Illustrate for Subcase 1.2.1 ofLemma 3.1.

Subcase 1.2.1.2.xy∈C\R. SeeFigure 2b.

The proof for this subcase is similar to that of the Subcase 1.2.1.1 and is omitted.

Subcase 1.2.1.3.xy∈R. SeeFigure 2c.

LetwlP1 lP2. Ifwis even, set

WP1P2. 3.13

Otherwise, set

WP1P2C. 3.14

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.15 whereC2 is a positive 2-cycle that contains vertexx. Sincelis odd, we see that bothlW1 andlW2are even. Then, ifwis even,

lW1 lW2≤2

n−l−lm

l2n−l−2l2m. 3.16

Otherwise,

lW1 lW2≤2

n−l−lm

ll2n−l−l2m. 3.17

(8)

x y

y^′ x^′

P2 P1

C^′

ν1

νm

C

a

x

y y^′

x^′

P2

P1

C^′

ν1

νm

C

b

x

y y^′

x^′

P2

P1

C^′

ν1

νm

C

c

x y

y^′

x^′ P2

P1

C^′

ν1 νm

C d

x y

y^′

x^′ P2

P1

C^′

ν1 νm

C e

y x

y^′ x^′

P2 P1

C^′ ν1

νm

C

f Figure 3: Illustration for Subcases 1.2.2 and 2.2 ofLemma 3.1.

Subcase 1.2.2.x/yand 2≤m≤minl, l.

Subcase 1.2.2.1.x∈C\Randy∈C\R. SeeFigure 3a.

Without loss of generality, we assume thatlQC\Rx → v1≤lQC\Ry → v1. Let wlP1 lQC\Rx → v1 lQRv1 → vm lQC\Rvm → y lP2. Ifwis even, set

WP1Q_C\R

x−→v1

Q_Rv1 −→v_m Q_C\R

v_m−→y

P2. 3.18 Otherwise, set

W P1Q_C\R

x−→v1

Q_C_\Rv1 −→v_m Q_C\R

v_m−→y

P2. 3.19 Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise,

3.20

whereC2is a positive 2-cycle that contains vertexx. SinceCis odd,lQC\Rv1 → vmand lQ_Rv1 → v_mhave diﬀerent parity. Therefore, bothlW1andlW2are even. Noting that

(9)

W3 P1 QC\Rx → v1 QRv1 → vm QC\Rvm → yand W4 P1 QC\Rx → v1Q_C_\Rv1 → v_mQ_C\Rv_m → yare paths ofSA, we havelW3,lW4≤n−1. Then

lW1 lW2≤n−1

n−l−lm

l2n−lm−1. 3.21

Subcase 1.2.2.2.x∈C\Randy∈R. SeeFigure 3b.

Without loss of generality, we assume thatlQC\Rx → v1 ≤ lQC\Rx → vm. Then we consider two subcases: the subcasex ∈ C\R,y ∈Randy/v1and the subcase x∈C\Randyv1.

First, we consider the subcasex∈C\R,y∈Randy/v1. LetwlP1lQC\Rx → v1 lQRv1 → y lP2. Ifwis even, set

WP1Q_C\R

x−→v1

Q_R

v1−→y

P2. 3.22

Otherwise, set

WP1Q_C\R

x−→v1

Q_C_\Rv1−→v_m Q_R

v_m−→y

P2. 3.23

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎨

⎪⎪

⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.24 whereC2 is a positive 2-cycle that contains vertexx. SinceC is odd,lQRv1 → yand lQ_C_\Rv1 → v_m lQ_Rv_m → yhave diﬀerent parity. Therefore, bothlW1andlW2 are even. Noting thatW3 P1QC\Rx → v1 QRv1 → yandW4 P1QC\Rx → v1QC\Rv1 → vmQRvm → yare two paths ofSA, then we havelW3,lW4≤n−1.

Then

lW1 lW2≤n−1

n−l−lm

l2n−lm−1. 3.25

Then, we consider the subcasex ∈ C\R andy v1. Letw lP1 lQ_C\Rx → vm lQRvm → v1y lP2. Ifwis even, set

WP1QC\R

x−→vm QR

vm−→v1

y

P2. 3.26

(10)

Otherwise, set

WP1Q_C\R

x−→v_m

Q_C_\R

v_m−→v1

y

P2. 3.27

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.28

whereC2 is a positive 2-cycle that contains vertexx. SinceC is odd,lQRvm → v1y andlQ_C_\Rv_m → v1yhave diﬀerent parity. Therefore, bothlW1andlW2are even.

Noting thatW3 P1 Q_C\Rx → v_m Q_Rv_m → v1yand W4 P1 Q_C\Rx → vm QC\Rvm → v1yare two paths ofSA, we havelW3,lW4≤n−1. Then

lW1 lW2≤n−1

n−l−lm

l2n−lm−1. 3.29

Subcase 1.2.2.3.x∈C\Randy∈C\R. SeeFigure 3c.

Subcase 1.2.2.4.x∈Randy∈R. SeeFigure 3d.

LetwlP1 lQCx → y lP2. Ifwis even, set WP1Q_C

x−→y

P2. 3.30

Otherwise, set

WP1C\Q_C

x−→y

P2. 3.31

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

(11)

whereC2 is a positive 2-cycle that contains vertexx. SinceCis odd,lQCx → yand lC\Q_Cx → yhave diﬀerent parity. Therefore, bothlW1andlW2are even. Then if wis even,

lW1 lW2≤2

n−l−lm l−1

2 l2n2m−l−3l 2 −1

2. 3.33

Otherwise,

lW1 lW2≤2

n−l−lm

l−1

l2n−l−l2m−1. 3.34 Since bothlW1andlW2are even, it follows thatlW1 lW2≤2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Subcase 1.2.2.5.x∈Randy∈C\R. SeeFigure 3e.

The proof for this subcase is similar to that of Subcase 1.2.2.4, so we omit it.

Subcase 1.2.2.6.x∈C\Randy∈C\R. SeeFigure 3f.

Without loss of generality, we assume thatlQC\Rx → v1≤lQC\Ry → v1. Let wlP1 lQC\Rx → v1 lQRv1 → vm lQC\Rvm → y lP2. Ifwis even, set

WP1QC\R

x−→v1

QRv1 −→vm QC\R

vm−→y

W P1Q_C_\R

x−→y

Q_C_\R

y−→v_m

Q_C_\R

v_m−→y

P2. 3.36 Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.37 whereC2 is a positive 2-cycle that contains vertexx. SinceCis odd,lQ_C_\Rx → yand lQ_C_\Rx → v1lQ_Rv1 → v_mlQ_C_\Rv_m → yhave diﬀerent parity. Therefore, both lW1andlW2are even. Noting thatW3 P1QC\Rx → v1QRv1 → vmQC\Rvm → yandW4 P1Q_C_\Rx → y Q_C_\Ry → v_mare two paths ofSA, then we have lW3≤n−1 andlW4≤n−m. Then, ifwis even,

lW1 lW2≤n−1

n−l−lm

l2n−lm−1. 3.38 Otherwise,

lW1 lW2≤

n−l−lm

n−m

l−m−1

l2n−m−1. 3.39

(12)

u

x y^′ y

x^′ P2

P1

C^′ C

a

u

y x

y^′ x^′

P2

P1

C^′ C

b

y x

u y^′ x^′

P2

P1

C^′

C

c

Figure 4: Illustrate for Subcase 1.2.3 ofLemma 3.1.

Subcase 1.2.3.m1 andx/y. We assume thatVC∩VC {u}.

Subcase 1.2.3.1.x∈Candy∈C. SeeFigure 4a.

LetwlP1 lQCx → u lQCu → y lP2. Ifwis even, set WP1Q_C

x−→u Q_C

u−→y

P2. 3.40

Otherwise, set

WP1Q_C

x−→u Q_C

u−→y

P2C. 3.41

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

(13)

whereC2is a positive 2-cycle that contains vertexx. Sincelis odd, bothlW1andlW2are even. Then, ifwis even,

lW1 lW2≤2

n−l−l1

l−1 l2n−2l1. 3.43

Otherwise,

lW1 lW2≤2

n−l−l1

l−1 ll2n−l1. 3.44 Since bothlW1andlW2are even, it follows thatlW1 lW2 ≤ 2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Subcase 1.2.3.2.x∈C,y∈C, andx/y/u. SeeFigure 4b.

LetwlP1 lQCx → u lQCu → y lP2. Ifwis even, set WP1QC

x−→u QC

u−→y

WP1QC

x−→u

C\QC

u−→y

P2. 3.46

Let

W1

WC, wis even,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩ W l

2C2, wis even, W l

2C2, otherwise, 3.47 whereC2is a positive 2-cycle that contains vertexx. SinceCis odd,lC\QCu → yand lQCu → yhave diﬀerent parity. Therefore, bothlW1andlW2are even. Noting that W3P1Q_Cx → u Q_Cu → yandW4P1Q_Cx → u C\Q_Cu → yare two paths ofSA, we havelW3,lW4≤n−1. Then,

lW1 lW2≤n−1

n−l−l1

l2n−l. 3.48

Since bothlW1andlW2are even, it follows thatlW1 lW2 ≤ 2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Subcase 1.2.3.3.x∈Candy∈C. SeeFigure 4c.

Thus in each of the above subcases, there exists a pair of SSSD walks fromxtoywith length 2n−2. Therefore, we getlA≤2n−2 byLemma 2.6.

Case 2. There exists no negative even cycle inSA.

(14)

SinceAis primitive, nonpowerful and there exist no negative even cycles inSA, it follows fromLemma 2.5that there exist two odd cyclesCandCwith diﬀerent signs inSA.

We assume thatlC landlC l. Since the trace ofAis zero, there are no loops inSA and sol,l≥3. Without loss of generality, we assumel≥l≥3.

Subcase 2.1.CandChave no common vertices.

Let P be the shortest path from C to C. Suppose P intersects C at vertex u and intersects Cat vertex vand there are k vertices on P wherek ≥ 2. LetG2 C∪P ∪C. Letxandybe two arbitrarynot necessarily distinctvertices inSA. Suppose thatP1is the shortest path fromxtoG2and intersectsG2at vertexxandP2is the shortest path fromyto G2and intersectsG2at vertexy. Then

0≤lP1, lP2≤n−l−l−k2. 3.49

SinceCandChave diﬃdent signs, if there exists an even walkWwith lengthlW≤2n−2−l, thenW1WCandW2Wl−l/2C2Chave the same lengthlW1 lW2≤2n−2 and diﬀerent signs. As the proof of Subcase 1.1, we can construct an even walkWwith length lW≤2n−2−l. So there exists a pair of SSSD walks fromxtoyof length 2n−2. It remains to consider the following subcase.

Subcase 2.2.CandChave at least one common vertex.

LetG3C∪C. Letxandybe two arbitrarynot necessarily distinctvertices inSA.

Suppose thatP1is the shortest path fromxtoG3and intersectsG3at vertexxandP2is the shortest path fromytoG3and intersectsG3at vertexy. DenoteC∩CbyR. AssumeRhas mvertices, where 1≤m≤minl1, l2, then

0≤lP1, lP2≤n−l1−l2m. 3.50

If m > 1, then R is a path with vertex set VR {v1, v2, . . . , vm} and edge set ER {v1, v2,v2, v3, . . . ,v_m−1, v_m}. Ifml, since there exists no negative even cycles inSA, thenCandChave the same sign, a contradiction. Therefore, 1≤m < l.

Subcase 2.2.1.x∈C\Randy∈C\R. SeeFigure 3a.

Without loss of generality, we assume thatlQ_C\Rx → v1≤lQ_C\Ry → v1. Let wlP1 lQC\Rx → v1 lQRv1 → vm lQC\Rvm → y lP2. Ifwis odd, set

WP1Q_C\R

x−→v1

Q_Rv1 −→v_m Q_C\R

v_m−→y

P2. 3.51

Otherwise, set

W P1QC\R

x−→v1

QC\Rv1 −→vm QC\R

vm−→y

P2. 3.52

(15)

Let

W1

WC, w is odd,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

WCl−l

2 C2, wis odd, WCl−l

2 C2, otherwise, 3.53 where C2 is a positive 2-cycle that contains x. Since C is odd, lQRv1 → vm and lQC\Rv1 → vmhave diﬀerent parity. Therefore, bothlW1 andlW2are even. Then, ifwis odd,

lW1 lW2≤2

n−l−lm

ll2n−2l2m. 3.54 Otherwise,

lW1 lW2≤2

n−l−lm

l−m1

l2n−l2. 3.55 Since bothlW1andlW2are even, it follows thatlW1 lW2 ≤ 2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Subcase 2.2.2.x∈C\Randy∈R. SeeFigure 3b.

LetwlP1 lQCx → y lP2. Ifwis odd, set WP1Q_C

x−→y

WP1C\QC

x−→y

P2. 3.57 Let

W1

WC, w is odd,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

WCl−l

2 C2, otherwise, 3.58 whereC2is a positive 2-cycle that containsx. SinceCis odd,C\Q_Cx → yandQ_Cx → yhave diﬀerent parity, Therefore, bothlW1andlW2are even. Then, ifwis odd,

lW1 lW2≤2

n−l−lm l−1

2 l2n−2l2m−l1

2 . 3.59

Otherwise,

lW1 lW2≤2

n−l−lm

l−1 l2n−2l2m−1. 3.60

(16)

Subcase 2.2.3.x∈C\Randy∈C\R. SeeFigure 3c.

Without loss of generality, we assume thatlQ_C\Rx → v1≤lQ_C\Rx → v_m. Let wlP1 lQC\Rx → v1 lQC\Rv1 → y lP2. Ifwis odd, set

WP1Q_C\R

x−→v1

Q_C_\R

v1−→y

P2. 3.61

Otherwise, set

WP1Q_C\R

x−→v1

Q_Rv1 −→v_m Q_C_\R

v_m−→y

P2. 3.62

Let

W1

WC, w is odd,

WC, otherwise, W2

⎧⎪

⎪⎪

⎨

⎪⎪

⎪⎩

WCl−l

2 C2, otherwise, 3.63 where C2 is a positive 2-cycle that contains x. Since C is odd, lQC\Rv1 → y and lQ_Rv1 → v_m lQ_C_\Rv_m → yhave diﬀerent parity. Therefore, bothlW1andlW2 are even. Noting thatW3 P1QC\Rx → v1 QC\Rv1 → yandW4 P1QC\Rx → v1 QRv1 → vm QC\Rvm → yare paths ofSA, then we havelW3,lW4≤n−1.

Therefore,

lW1 lW2≤n−1

n−l−lm

l2n−lm−1. 3.64 Since bothlW1andlW2are even, it follows thatlW1 lW2≤2n−2. We see that the pairW1,W2is a pair of SSSD walks with even length. Therefore, there exists a pair of SSSD walks fromxtoywith length 2n−2.

Subcase 2.2.4.x∈Randy∈R. SeeFigure 3d.

The proof for this subcase is similar to that of Subcase 2.2.2, so we omit it.

Subcase 2.2.5.x∈Randy∈C\R. SeeFigure 3e.

Subcase 2.2.6.x∈C\Randy∈C\R. SeeFigure 3f.

From all the above subcases, there exists a pair of SSSD walks fromxtoywith length 2n−2. Therefore, we getlA≤2n−2 byLemma 2.6.

Lemma 3.2. LetAbe ann×nprimitive nonpowerful ZS sign pattern matrix with zero diagonal. If there exist a negative 2-cycle and a positive 2-cycle inSA, thenlA≤2n−2.