Zero-nonzero patterns, Nilpotent, Ideal saturation, Gr¨obner basis, Finite fields

ZERO-NONZERO PATTERNS FOR NILPOTENT MATRICES OVER FINITE FIELDS^∗

KEVIN N. VANDER MEULEN^† AND ADAM VAN TUYL^‡

Abstract. Fix a fieldF. A zero-nonzero pattern Ais said to be potentiallynilpotent overF if there exists a matrix with entries inF with zero-nonzero pattern Athat allows nilpotence. In this paper an investigation is initiated into which zero-nonzero patterns are potentiallynilpotent overFwith a special emphasis on the case thatF=Zp is a finite field. A necessarycondition on F is observed for a pattern to be potentiallynilpotent when the associated digraph hasm loops but no smallk-cycles, 2≤k≤m−1. As part of this investigation, methods are developed, using the tools of algebraic geometryand commutative algebra, to eliminate zero-nonzero patterns Aas being potentiallynilpotent over anyfieldF. These techniques are then used to classifyall irreducible zero-nonzero patterns of order two and three that are potentiallynilpotent overZpfor each primep.

Key words. Zero-nonzero patterns, Nilpotent, Ideal saturation, Gr¨obner basis, Finite fields.

AMS subject classifications.15A18, 13P10, 05C50, 11T06.

1. Introduction. Azero-nonzero (znz) patternAis a square matrix whose en- tries come from the set {∗,0} where ∗ denotes a nonzero entry. Fix a field F. We then set

Q(A,F) ={A∈M_n(F)|(A)_i,j= 0⇔(A)i,j=∗ for alli, j}.

The set Q(A,F),sometimes denoted Q(A) when F is known,is usually called the qualitative classof A. An element A∈ Q(A,F) is called a matrix realization of A. A znz-pattern A is said to be potentially nilpotent over F if there exists a matrix A ∈Q(A,F) such thatA^k = 0 for some positive integer k. In this paper we study the question of what patterns A are potentially nilpotent over a field F. Although we will present some results for arbitrary fields,we are particularly interested in the case thatFis a finite field.

One motivation to study this question is to provide a step in understanding spectrally arbitrary patterns in the context of fields other than R. An n×n znz- patternAis aspectrally arbitrary pattern(SAP) if given any monic polynomialp(x) of

∗Received bythe editors December 18, 2008. Accepted for publication October 8, 2009. Handling Editor: Michael J. Tsatsomeros.

†Department of Mathematics, Redeemer UniversityCollege, Ancaster, ON L9K 1J4 Canada (kvanderm@redeemer.ca). Research supported in part byan NSERC DiscoveryGrant.

‡Department of Mathematical Sciences, Lakehead University, Thunder Bay, ON P7B 5E1 Canada (avantuyl@lakeheadu.ca). Research supported in part byan NSERC DiscoveryGrant.

628

degreenwith coefficients inF,there exists a matrixA∈Q(A,F) whose characteristic polynomial isp(x). Note that every SAP is potentially nilpotent. There is a growing body of literature (see,for example,[2,5,7,18,19] and their references) interested in identifying SAPs whenF=R(with much focus onsign patterns: patterns whose entries come from the set {+,−,0}). Recently,work has begun on the problem of identifying SAPs over finite fields [1] and overC[21].

We now cursorily survey the problem of identifying potentially nilpotent patterns over F=R. Determining when a sign pattern is potentially nilpotent was listed as an open problem in [9]. Potentially nilpotent star sign patterns were introduced in [20] and fully characterized in [17]. Potentially nilpotent sign patterns of order up to 3 were characterized in [10]. Included in [10] is an investigation of sign patterns that allow nilpotence of index 2,where the index of matrixA is the smallest integer ksuch that A^k = 0; this was later extended to index 3 in [11] (see also [3]). In [18], it was shown that all potentially nilpotent full sign patterns (i.e. patterns with no zero entries) are also SAPs. Consequently,recent work [15] presents constructions of potentially nilpotent full sign patterns. Much work in determining when a pattern is potentially nilpotent occurs in the literature on SAPs. Identifying potentially nilpo- tent patterns over Ris in part an important subproblem in the study of SAPs due to a technique developed in [8],usually referred to as the Nilpotent-Jacobi Method.

Roughly speaking,ifAis a nilpotent realization overRof a patternA,then one can determine if A is spectrally arbitrary by evaluating the entries of A in a Jacobian matrix constructed from A. Note that this technique requires the Implicit Func- tion Theorem,which holds overR,so one should not expect a generalization of this approach to finite fields.

We begin in Section 2 by reviewing some basic results concerning nilpotent ma- trices over a fieldF. Many of the results that are known to hold inRcontinue to hold over an arbitrary field.

In Section 3 we introduce some techniques to eliminate certain patterns as being potentially nilpotent over a field. We use some tools from commutative algebra and algebraic geometry to carry out this program. Starting with a znz-pattern A with nonzero entries at (i₁, j₁), . . . ,(i_t, j_t),we define an ideal I_A in a polynomial ring R_A=F[z_i1,j1, . . . , z_it,jt] over the fieldF. In Theorem 3.2 we show thatAis potentially nilpotent over a fieldFif and only if a certain subset of the affine variety defined byI_A is nonempty. With this characterization,we can use the technique of ideal saturation (see Definition 3.4) to determine if a given pattern isnotpotentially nilpotent:

Theorem 3.5. Let Fbe any field and Aa znz-pattern. Let J = (z_i1,j1· · ·z_it,jt)be the ideal generated by the product of the variables of R_A. If 1∈I_A:J^∞, then Ais not potentially nilpotent over any extension ofF.

Since many computer algebra programs can compute the saturation of ideals, Theorem 3.5 promises to be a useful tool for future experimentation. In the last part of Section 3 we review the basics of Gr¨obner bases,and show how Gr¨obner bases can also be used to eliminate znz-patterns as being potentially nilpotent (see Example 3.13).

As an aside,we hope that our results,along with the work of Shader [19] and Kaphle [13],will highlight the usefulness of techniques from commutative algebra and algebraic geometry in the study of SAPs. Shader uses a result about the number of algebraically independent elements over the polynomial ring R[x1, . . . , x_n] to prove a lower bound on the number of nonzero entries in a SAP. Kaphle’s MSc thesis uses Gr¨obner bases to eliminate sign patterns as being potentially nilpotent. Note that one difference between our work and the work of Kaphle is that we use the equations constructed from the characteristic polynomials when forming the Gr¨obner basis,while Kaphle uses equations constructed from the traces of the matricesA^k for k= 1, . . . , n.

In Section 4 we introduce a necessary condition for a znz-patternAto be nilpotent over a field F. Precisely,we look at znz-patternsA where A is irreducible and the digraph D(A) has no 2-cycles (see Section 2). When F = R,if A has at least two nonzero entries on the diagonal andAis potentially nilpotent,then it is known (see [7]) that D(A) must to have a 2-cycle. We explore the fact that this is no longer true over an arbitrary field: what is important is that the polynomial x³−1 factors completely overF. In fact,we prove a more general result:

Theorem 4.4. LetAbe a znz-pattern withm≥2nonzero entries on the diagonal, and suppose that D(A)has no k-cycles with 2≤k≤m−1. IfA is potentially nilpotent overF, then the polynomial x^m−1factors into mlinear forms over F.

Our paper culminates with Section 5 which uses the above techniques to classify all potentially nilpotent patterns of order at most three when F = Z_p is the finite field withpelements,wherepis a prime (see Theorems 5.1 and 5.3). One interesting by-product of this classification is the discovery thatAmay be potentially nilpotent in a field F,but asuperpattern ofA,that is,a znz-patternA such that (A)_i,j = 0 whenever (A)_i,j= 0,might not be potentially nilpotent over the same fieldF.

2. Basic Properties. In this section,we review some of the needed properties of znz-pattern matrices and summarize some of the basic properties of potentially nilpotent matrices overF. Some of these results were known whenF=R; we consider the more general case. We continue to use the notation from the introduction.

When referring to elements of the fieldF,we shall use 1_Fto denote the multiplica- tive identity ofF,but abuse notation slightly and write 0 for the additive identity 0_F.

For any positive integern∈Z,we writen_F to denote (1_F+· · ·+ 1_F) (ntimes). Then

−n_F will denote the additive inverse of n_F in F,and n⁻¹_F denotes the multiplicative inverse (providedn_F= 0).

Given ann×nznz-patternA,we can construct a digraphD(A) = (V, E) on the vertex set V = [n] :={1, . . . , n},whose edge set consists of the arcs (i, j) whenever (A)_i,j = 0. We call the edge (i, i) a loop; loops correspond to the nonzero entries on the diagonal ofA. A simple cycle γ of length k,also called ak-cycle,is a sequence ofk distinct vertices{i₁, . . . , i_k} such that (i₁, i₂),(i₂, i₃), . . . ,(i_k−1, i_k),(i_k, i₁)∈E.

We sometimes denote ak-cycleγby (i₁, i₂, . . . , i_k),and denote its length by|γ|=k.

Furthermore,we say two cycles γ₁ and γ₂ are disjoint if they have no vertices in common.

Suppose that A ∈Q(A,F) is a realization of A. The characteristic polynomial of A can be described in terms of the cycles of D(A). Precisely,suppose that γ = (i₁, . . . , i_k) is a k-cycle. We let (γ) =a_i1,i2a_i2,i3· · ·a_ik,i1 where a_i,j= (A)_i,j. Then the characteristic polynomial ofAhas the form

p_A(x) =xⁿ+r₁xⁿ⁻¹+r₂xⁿ⁻²+· · ·+r_n−1x+r_n with

r_i= (−1)ⁱ (−1)^|γ1|−1 (γ₁)

· · ·

(−1)^|γp|−1 (γ_p)

.

where the sum is over all pairwise disjoint cyclesγ₁, . . . , γ_psuch that|γ₁|+· · ·+|γ_p|=i.

A znz-pattern Aof ordern≥2 is reducibleif there exists some integer 1≤r≤ n−1 and a permutation matrixP such that

PAP^T =

A1 A2

0_r,n−r A₃ .

Otherwise,a znz-pattern A is called irreducible. Equivalently,a znz-pattern A is irreducible if and only if the associated digraphD(A) is strongly connected,that is, there is a directed path between any pair of distinct vertices. The Frobenius normal form of A is a permutation similar block upper triangular matrix whose diagonal blocks are irreducible. The diagonal blocks are called the irreducible components of A.

The final lemma of this section summarizes some of the results we will need in the later sections.

Lemma 2.1. Fix a field Fand a znz-pattern A.

(a) Suppose thatA is reducible with irreducible componentsA1, . . . ,At. ThenA is potentially nilpotent overFif and only if each znz-patternAi is potentially nilpotent.

(b) If Ais potentially nilpotent over F, then so isAT, the transpose ofA.

(c) If A is a nilpotent realization of A, then the characteristic polynomial of A isp_A(x) =xⁿ.

3. Eliminating potentially nilpotent candidates via ideal saturation.

LetF be any field. Using some tools and techniques from commutative algebra and algebraic geometry,we will show that a znz-patternAis potentially nilpotent overF if and only if a certain geometric set is nonempty. As an application,we develop an algebraic method to eliminate certain znz-patternsA as being potentially nilpotent overF. We also explain how to use Gr¨obner bases to show that some patterns are not potentially nilpotent. While we will endeavor to keep this material as self-contained as possible,further background material can be found in the book of Cox,Little,and O’Shea [6].

We begin with some notation. Fix a znz-patternA,and letS_A={(i, j)|(A)i,j= 0}be the locations of the nonzero elements inA. We then define the polynomial ring

R_A:=F[zi,j |(i, j)∈S_A] =F[zi1,j1, . . . , z_it,jt]

int=|S_A| variables over the fieldF. Associate toAthe matrix M_Awhere (M_A)_i,j:=

z_i,j if (A)_i,j= 0 0 if (A)i,j= 0.

Note that M_A is not a realization of A since the entries of M_A are variables. The characteristic polynomial ofM_Athen has the form

p_MA(x) =xⁿ−F₁xⁿ⁻¹+F₂xⁿ⁻²+· · ·+ (−1)ⁿ⁻¹F_n−1x+ (−1)ⁿF_n

where each coefficientF_i =F_i(z_i1,j1, . . . , z_it,jt) is a polynomial in R_A. We then use thencoefficients of the characteristic polynomial to define an ideal ofR_A. Precisely, let

I_A:= (F₁, . . . , F_n)⊆R_A.

In fact, I_A is a homogeneous ideal since for each F_i = 0,the polynomial F_i is a homogeneous polynomial of degree i; recall that a polynomial G is homogeneous if each term of G has the same degree. To see this fact,note that each term of F_i corresponds to a composite cycle of length i in the directed graph D(A) (see the formula in Section 2),from which it follows that F_i is homogeneous. Hence,every znz-patternAinduces a homogeneous idealI_A.

Example 3.1. We illustrate the above notation with the following znz-pattern A=



∗ ∗ 0

∗ 0 ∗ 0 ∗ ∗



.

The associated matrix is

M_A=



z_1,1 z_1,2 0 z_2,1 0 z_2,3

0 z_3,2 z_3,3





where thez_i,j’s are indeterminates in the polynomial ring R_A=F[z_1,1, z_1,2, z_2,1, z_2,3, z_3,2, z_3,3].

The idealI_Ais then generated by three homogeneous polynomials:

I_A= (z_1,1+z_3,3, z_1,2z_2,1+z_2,3z_3,2+z_1,1z_3,3, z_1,1z_2,3z_3,2+z_1,2z_2,1z_3,3).

For eacha = (a_i1,j1, . . . , a_it,jt) ∈F^t,let M_A(a) denote the matrix obtained by replacing each z_ik,jk with a_ik,jk. The characteristic polynomial of M_A(a) will have the form:

p_MA(a)(x) =xⁿ−F₁(a)xⁿ⁻¹+F₂(a)xⁿ⁻²+· · ·+ (−1)ⁿ⁻¹F_n−1(a)x+ (−1)ⁿF_n(a).

If A is potentially nilpotent over F,then there exists an a ∈ F^t with all a_i,j = 0 such that M_A(a) is a nilpotent matrix. In particular,the characteristic polynomial of M_A(a) must be xⁿ by Lemma 2.1 (c),which,in turn,implies thatF_i(a) = 0 for i= 1, . . . , n. Thus,one can determine if a znz-patternAis potentially nilpotent over Fif one understands the affine variety described byI_A; theaffine variety¹ defined by I_A is the set

V(I_A) ={a∈F^t|G(a) = 0 for allG∈I_A}

={a∈F^t|F₁(a) =· · ·=F_n(a) = 0}.

The setV(I_A) contains all the elementsa∈F^tsuch that the matrixM_A(a) is nilpo- tent. Thus,if A is potentially nilpotent over F and M_A(a) is a realization of A that is nilpotent,then a ∈ V(I_A). However,the converse is not necessarily true.

Indeed,if b ∈ V(I_A),then while M_A(b) still has a characteristic polynomial of xⁿ, the matrix M_A(b) may not be a realization of A. As a simple example,note that 0 = (0, . . . ,0)∈V(I_A),(since eachF_i is homogeneous,and thus F_i(0) = 0 for all i), butM_A(0) is the zero-matrix,which is not a realization ofA.

For each indeterminatez_i,j∈R_A,letV(z_i,j) denote the associated affine variety, that is, V(z_i,j) = {a ∈ F^t | a_i,j = 0}. With this notation,we can determine if a znz-patternAis potentially nilpotent overF:

1What we call an affine varietyis sometimes called an algebraic set. We decided to follow [6].

Theorem 3.2. Fix a fieldFand a znz-patternA. ThenAis potentially nilpotent overF if and only if

V(I_A)\ ^t

k=1

V(z_ik,jk)=∅.

Proof. IfAis potentially nilpotent overF,then there exists ana∈F^t such that M_A(a) is nilpotent. But that implies thata∈V(I_A). Furthermore,sinceM_A(a) is a realization ofA,a_ik,jk = 0 fork= 1, . . . , t,or in other words,a∈V(z_ik,jk) for each k. This proves the first direction.

For the reverse direction,ifa∈V(I_A)\_t

k=1V(z_ik,jk),thenM_A(a) is a nilpotent matrix,and furthermore,sincea_ik,jk = 0 for allk,this matrix is also a realization of A.

As a consequence of Theorem 3.2,to determine ifAis potentially nilpotent over F,it suffices to show that the setV(I_A)\_t

k=1V(z_ik,jk) is non-empty. Unfortunately, this can be a highly non-trivial problem. However we can use this reformulation to describe an algebraic method to determine if the setV(I_A)\_t

k=1V(z_ik,jk) is empty, thus providing a means to determine ifAis not potentially nilpotent overF.

We begin with a simple lemma. AmonomialofR_Ais any polynomial of the form m=z_i^b1

1,j1z_i^b2

2,j2· · ·z^b_i^t

t,jt with eachb_i∈Z_≥0.

Lemma 3.3. Fix a field F and a znz-pattern A. Suppose that there exists a monomialm=z_i^b₁¹_,j1z^b_i2²_,j2· · ·z_i^b_t^t_,jt ∈I_A. ThenAis not potentially nilpotent over F.

Proof. For any a ∈ V(I_A),we must have m(a) = a^b_i¹

1,j1· · ·a^b_i^t

t,jt = 0 because m∈I_A. But this means thata_ik,jk = 0 for somek= 1, . . . , n,and thus,a∈V(z_ik,jk).

Now apply Theorem 3.2.

The colon operation and the saturation of ideals are two required algebraic in- gredients:

Definition 3.4. LetI andJ be ideals of a ringR. ThenI:J denotes the ideal I:J ={g∈R|gJ ⊆I}.

Thesaturation ofI with respect toJ,denotedI:J^∞,is the ideal I:J^∞={g∈R|gJⁱ⊆I for some integeri≥0}. Alternatively,I:J^∞= (· · ·(((I:J) :J) :J)· · ·).

We come to one of the main results of this section.

Theorem 3.5. Fix a field F and a znz-pattern A. If R_A =F[z_i1,j1, . . . , z_it,jt], then letm_A:=_t

k=1z_ik,jk and letJ = (m_A)be the ideal generated bym_A. Then (a) V(I_A)\_t

k=1V(z_ik,jk)⊆V(I_A:J^∞)⊆V(I_A:J);

(b) if 1 ∈ I_A : J^∞, then A is not potentially nilpotent over F, or any field extension of F;

(c) if1∈I_A:J, thenAis not potentially nilpotent overF, or any field extension of F.

Proof. Statement (a) is a well-known result via the algebraic geometry dictionary.

For completeness,we include a short proof in this context. Suppose thata∈V(I_A)\ _t

k=1V(z_ik,jk),and thus,a_ik,jk = 0 for k = 1, . . . , t. Suppose that G ∈ I_A : J^∞. Thus,there exists an integer i such that GJⁱ ⊆ I_A. But because Jⁱ = (mⁱ_A),this implies that Gmⁱ_A ∈ I_A. Since a ∈ V(I_A),we have (Gmⁱ_A)(a) =G(a)mⁱ_A(a) = 0.

But since eacha_ik,jk = 0, we havemⁱ_A(a) =aⁱ_i1,j1· · ·aⁱ_it,jt = 0,and henceG(a) = 0, or equivalently,a∈V(I_A:J^∞). The second inclusion containment follows from the fact thatI_A:J ⊆I_A:J^∞.

To prove (b),suppose that 1 ∈ I_A : J^∞. It then follows that there exists an i such thatJⁱ ⊆I_A,and hence mⁱ_A∈I_A. But then we get the desired conclusion by Lemma 3.3. In any extension ofF,we will continue to havemⁱ_A∈I_A. Statement (c) follows directly from (b) since we will have 1∈I_A:J ⊆I_A:J^∞.

Remark 3.6. Many computer algebra systems allow one to compute the sat- uration of an ideal,thus making Theorem 3.5 a practical tool. The computational commutative algebra programs CoCoA [4] and Macaulay 2 [12] are two free programs that can be used to compute the idealsI:J andI:J^∞. On the second author’s web page²is a short introduction on how to use these programs to compute the examples found below.

Some well-known necessary facts for nilpotent matrices are simple corollaries of Theorem 3.5.

Corollary 3.7. Let A be znz-pattern. If Ahas only one nonzero entry on the diagonal or only one transversal, thenAis not potentially nilpotent over any fieldF.

Proof. In both cases,we show that one of the generators ofI_Amust be a mono- mial. If A has only one nonzero entry on the diagonal,say at position (i, i),then the trace of M_A is z_i,i. But since F₁ = trM_A = z_i,i,it immediately follows that m_A ∈ I_A,and hence,1 ∈ I_A : (m_A). Similarly,if A has only one transversal,the determinant ofM_A,which equalsF_n,has formz_i^b1

1,j1z_i^b2

2,j2· · ·z_i^bt

t,jt whereb_k = 1 or 0.

It then follows thatm_A∈I_A,or equivalently,1∈I_A: (m_A).

2http://flash.lakeheadu.ca/∼avantuyl/research/research.html

We now provide some illustrative examples.

Example 3.8. LetA be the znz-pattern of Example 3.1. LetFbe any field of characteristic two. Because

I_A= (z_1,1+z_3,3, z_1,2z_2,1+z_2,3z_3,2+z_1,1z_3,3, z_1,1z_2,3z_3,2+z_1,2z_2,1z_3,3), the monomialz²_1,1z_3,3∈I_Abecause

z_1,2z_2,1(z_1,1+z_3,3) +z_1,1(z_1,2z_2,1+z_2,3z_3,2+z_1,1z_3,3) + (z_1,1z_2,3z_3,2+z_1,2z_2,1z_3,3)

= 2z_1,2z_2,1z_1,1+ 2z_1,1z_2,3z_3,2+z²_1,1z_3,3+ 2z_1,2z_2,1z_3,3=z_1,1² z_3,3

sincex+x= 0 for anyx∈F. ThusAis not potentially nilpotent over any field of extension ofF. Note that whenF=Z2 is the finite field with exactly two elements, then one could use a direct calculation because there is only one choice for eachz_i,j, namely 1_F. However,this method shows thatAis not potentially nilpotent over any extension of this field.

Example 3.9. It is possible that 1∈I_A:J^∞,but 1∈I_A :J. As an example, consider the znz-pattern

A=



∗ 0 0 0 ∗ ∗ 0 ∗ ∗



.

We can see immediately thatAis not potentially nilpotent over any fieldFsince any realizationA ofAwill have the nonzero eigenvalue ofa_1,1. However,this cannot be deduced fromI_A:J. For example,ifF=Z2,then we use CoCoA or Macaulay 2 to findI_A:J =

(z1,1+z2,2+z3,3,−z1,1z2,2+z2,3z3,2−z1,1z3,3−z2,2z3,3,−z1,1z2,3z3,2+z1,1z2,2z3,3) : (mA)

= (z1,1+z2,2+z3,3, z_2,2² +z²_3,3, z2,3z3,2+z2,2z3,3).

However,a computer algebra system will reveal that 1∈I_A:J^∞,thus showing that Ais not potentially nilpotent overF.

Example 3.10. Using the saturation of ideals also lends itself to sign patterns.

Consider the signed pattern

A=









− − − 0 0

+ + + 0 0

0 0 0 − −

0 − 0 0 −

− 0 0 0 0







 .

The patternAis the patternG₅studied in [14]. We then consider the matrix

M_A=









−z_1,1 −z_1,2 −z_1,3 0 0

z_2,1 z_2,2 z_2,3 0 0

0 0 0 −z_3,4 −z_3,5 0 −z_4,2 0 0 −z_4,5

−z_5,1 0 0 0 0







 .

We define I_A as above. LettingF=R,we find that 1∈I_A: (m_A)^∞ using CoCoA.

This sign patternA,therefore,is not potentially nilpotent overR,as first discovered in [14]; in factG₅is part of a much larger family of non-potentially nilpotent patterns.

As we will show below,the converse of Theorem 3.5 (b) does not hold. To show that Ais not potentially nilpotent,we apply the theory of Gr¨obner bases. Roughly speaking,a Gr¨obner basis ofI_Ais a “good” choice of generators ofI_Awhich can allow one to describe the affine varietyV(I_A).

We now recall the needed definitions. We fix a monomial ordering > on the monomials ofR_A,that is,(1)>is a total ordering on the set of monomials,(2)>is compatible with multiplication (ifm₁> m₂,then for any monomialm,mm₁> mm₂), and (3) > is also a well-ordering. Of particular importance is the lex monomial ordering,that is,

z^a_i¹

1,j1z^a_i²

2,j2· · ·z_i^at

t,jt > z_i^b1

1,j1z_i^b2

2,j2· · ·z_i^bt

t,jt

if and only if the first nonzero entry of thet-tuple (a₁−b₁, . . . , a_t−b_t) is positive.

For any polynomial F = c_αm_α ∈ R_A where m_α are monomials andc_α ∈F, the leading term ofF,denoted LT_>(F) is the largest monomial termc_αm_αinF with respect to>.

Definition 3.11. A subset {G₁, . . . , G_s} of an ideal I is a Gr¨obner basis of I with respect to a monomial ordering > if for all F ∈ I, LT_>(F) is divisible by LT_>(G_i) for some i.

We then make use of the following two properties of Gr¨obner bases.

Theorem 3.12. Let R=F[z_i1,j1, . . . , z_it,jt]. Let>be the lex monomial ordering with the property that z_i1,j1 >· · ·> z_it,jt. LetI be an ideal of R, and suppose that {G₁, . . . , G_s} is a Gr¨obner basis ofI with respect to>. Then

(a) I= (G₁, . . . , G_s), that is, the Gr¨obner basis generates I;

(b) Let I_l=I∩F[z_il+1,jl+1, . . . , z_it,jt]. ThenI_l is thelth elimination ideal, and a Gr¨obner basis forI_l is{G₁, . . . , G_s} ∩F[zil+1,jl+1, . . . , z_it,jt].

Proof. Statement (a) is [6,Chapter 2,§5,Corollary 2],while (b) is known as the Elimination Theorem [6,Chapter 3,§1,Theorem 2].

To make use of the above theorem to describe the affine varietyV(I),one first finds a Gr¨obner basis{G₁, . . . , G_s}forIwith respect to the lex monomial order. The- orem 3.12(b) implies that we can partition theG_i’s so that the first set are polynomi- als in the variables{z_i1,j1, . . . , z_it,jt},the second set are polynomials in the variables {z_i2,j2, . . . , z_it,jt},and so on,i.e.,the number of variables is eliminated as you move through the partitions. In some (but not all) cases,one or more of theG_i’s may only contain one variable. We can then find roots of these polynomials (either explicitly or numerically),and then using these solutions,find roots to the other polynomials.

We illustrate how to use Gr¨obner bases to eliminate some znz-patternsAas being potentially nilpotent over F. We will study the following pattern in more detail in the next section.

Example 3.13. We consider the znz-pattern

A=



∗ ∗ 0 0 ∗ ∗

∗ 0 ∗





and letF=R. In this case,the generators of the idealI_Aare

I_A= (z_1,1+z_2,2+z_3,3, z_1,1z_2,2+z_1,1z_3,3+z_2,2z_3,3, z_1,2z_2,3z_3,1+z_,1z_2,2z_3,3).

We can use a computer algebra program to check thatI_A: (z_1,1z_1,2z_2,2z_2,3z_3,1z_3,3)^∞= (1). Thus Theorem 3.5 does not tell us ifAis not potentially nilpotent overR.

We use either CoCoA or Macaulay 2 to find a Gr¨obner basis forI_A: {z_1,1+z_2,2+z_3,3, z_1,2z_2,3z_3,1+z_3,3³ , z_2,2² +z_2,2z_3,3+z_3,3² }.

Notice that the last polynomial contains the fewest number of variables. If A was potentially nilpotent,then there existsa = (a_1,1, a_1,2, a_2,2, a_2,3, a_3,1, a_3,3)∈ R⁶ such that M_A(a) is nilpotent,and specifically,a is a zero of all three polynomials in the Gr¨obner basis. Notea_3,3 must be a nonzero real number. But for any nonzero real numbera∈R,the last polynomial from the Gr¨obner basis implies thata_2,2will then have to satisfy

z_2,2² +az_2,2+a²= 0⇔z_2,2=a

−1±√

−3 2

.

But then for every nonzero choice ofa∈R,a_2,2∈R. Hence,Ais not potentially nilpo- tent overR. Observe that this example shows that the converse of Theorem 3.5(b) is false.

4. Digraphs without k-cycles with k small: a necessary condition. Let D(A) be the digraph associated to a znz-patternA. It is known that ifAis potentially

nilpotent over F =R,and if D(A) has at least two loops,then D(A) must have a 2-cycle. See,for example,[7,Lemma 3.2] which considers the signed case,but the proof also holds in the non-signed case. WhenF=R,then this necessary condition need not hold:

Example 4.1. Let A be the pattern of Example 3.13. The associated graph D(A) has three loops but no two cycles,so [7,Lemma 3.2] implies that A is not potentially nilpotent over R. However, A is potentially nilpotent over other fields:

Bodine [1] has observed that A is SAP (hence potentially nilpotent) over certain finite fields and Yielding [21] has observed thatAis SAP overC. For example,Ais potentially nilpotent overF=Z7 as demonstrated with the realization



4_F 1_F 0 0 2_F 1_F

−1_F 0 1_F



.

Our goal in this section is to explore the role of small cycles in nilpotence. More precisely,we provide a necessary condition onFfor a znz-patternAto be potentially nilpotent overFifD(A) has loops,but nok-cycles of small size. We begin by recalling the definition of the roots of unity and one result concerning these numbers.

Definition 4.2. Fix a fieldF. We say thatFcontains all the m^throots of unity if all of themroots of the polynomialx^m−1_F = (x−1_F)(x^m−1+x^m−2+· · ·+x+ 1_F) belong toF,that is,x^m−1_F factors intomlinear forms overF.

Lemma 4.3. Fix a field F and integer m ≥2. Suppose that there is a solution (a₁, . . . , a_m)∈F^m to the m−1 elementary symmetric polynomial equations

z₁+z₂+· · ·+z_m= 0 z₁z₂+· · ·+z_m−1z_m= 0

... z₁z₂· · ·z_m−1+· · ·+z₂z₃· · ·z_m= 0 with all a_j= 0. ThenFcontains all the m^throots of unity.

Proof. If (a₁, . . . , a_m) is such a solution,then (a₁a⁻¹_m, . . . , a_ma⁻¹_m) is also a solu- tion. Thus,we can assumea_m= 1_F. Hence,substituting (a₁, . . . , a_m−1,1_F) into the above equations and rearranging gives:

a₁+a₂+· · ·+a_m−1=−1F

a₁a₂+· · ·+a_m−2a_m−1= 1_F ...

a₁a₂· · ·a_m−1= (−1_F)^m−1.

We claim thata₁, . . . , a_m−1are the remainingm^throots of unity. Indeed, (x−a₁)(x−a₂)· · ·(x−a_m−1) =x^m−1−(a₁+a₂+· · ·a_m−1)x^m−2

+(a₁a₂+· · ·+a_m−2a_m−1)x^m−3

+· · ·+ (−1)^m−2(a₁· · ·a_m−2+· · ·+a₂· · ·a_m−1)x +(−1)^m−1a₁· · ·a_m−1

=x^m−1+x^m−2+· · ·+x+ 1_F.

That is, a₁, . . . , a_m−1 are the zeros of x^m−1+x^m−2+· · ·+x+ 1_F. The conclusion now follows.

Theorem 4.4. Let Abe a znz-pattern withm≥2 nonzero entries on the diago- nal, and suppose thatD(A)has no k-cycles with 2≤k≤m−1. IfA is potentially nilpotent over F, thenF contains all them^th roots of unity.

Proof. After relabeling,we may assume that the nonzero diagonal entries ofA are at (1,1), . . . ,(m, m). To simplify notation,let z_i denote the variable z_i,i in the polynomial ringR_A. BecauseD(A) has nok-cycles with 2≤k≤m−1,this implies that the firstm−1 generators ofI_Aare:

F₁=z₁+z₂+· · ·+z_m F₂=z₁z₂+· · ·+z_m−1z_m

...

F_m−1=z₁z₂· · ·z_m−1+· · ·+z₂z₃· · ·z_m.

Let A ∈ Q(A) be a realization that is nilpotent. If a_1,1, . . . , a_m,m are the nonzero diagonal entries,then a = (a_1,1, . . . , a_m,m) satisfies F_i(a) = 0 for i = 1, . . . , m−1.

Because a_j,j = 0 for 1≤j ≤m,Lemma 4.3 implies that the fieldF contains all the m^throots of unity.

Corollary 4.5. Let A be a znz-pattern with m ≥ 2 nonzero entries on the diagonal, and suppose that D(A) has no k-cycles with2 ≤k ≤ m. Then A is not potentially nilpotent over any F.

Proof. We use the notation of the proof of Theorem 4.4. BecauseAhas nok-cycle with 2≤k≤m,we haveF_m=z₁z₂· · ·z_m∈I_A. Now apply Lemma 3.3.

Using the above theorem,we can give a infinite family A_n below of potentially nilpotent znz-patterns. In [2],this family was demonstrated to fail to be potentially nilpotent forF=R.

Theorem 4.6. Fix a field F, and for each n ≥ 3, let A_n denote the n×n

znz-pattern

A_n=















∗ ∗ 0 · · · · 0

0 ∗ ∗ . .. ...

... . .. ... ... ... ...

... . .. ∗ 0

0 0 . .. ∗ ∗

∗ 0 0 · · · 0 ∗















Then A_n is potentially nilpotent over F if and only ifF contains all then^th roots of unity.

Proof. The graph ofD(A) is an n-cycle with a loop at each vertex. Thus,one direction follows immediately from Theorem 4.4 since D(A) has n loops and nok- cycles for 2≤k≤n−1. For the converse direction,suppose thatFcontains all then^th roots of unity: supposexⁿ−1_F= (x−ζ₁)· · ·(x−ζ_n−1)(x−1_F) withζ₁, . . . , ζ_n−1∈F. Then the matrix

A_n=















ζ₁ 1_F 0 · · · · · · 0

0 ζ₂ 1_F 0 0

... . .. ... ... . .. ...

... . .. . .. 0

0 0 . .. ζ_n−1 1_F

−1_F 0 0 · · · 0 1_F















is a desired realization.

Corollary 4.7. Fix a prime p. If p ≡ 1 (mod n), then An is potentially nilpotent over F=Zp.

Proof. Whenp≡1 (mod n),then by [16,Theorem 2.4],the fieldZ_pcontains all then^throots of unity. Now apply the Theorem 4.6.

Example 4.8. Theorem 4.6 gives a new way to explain why the patternA=A3

of Example 3.13 is not potentially nilpotent overR. BecauseD(A) has three loops, but no two cycles,if A were potentially nilpotent over F,then F must contain all the cube roots of unity. However,Rdoes not have this property. But whenF=Z7, x³−1 factors into linear forms; hence the realization in Example 4.1.

5. Potentially nilpotent matrices of small order over finite fields. In this section,we employ the tools of previous sections to classify all znz-patterns A

that are potentially nilpotent over F of order two or three when F = Z_p,with pa prime number. As a consequence of Lemma 2.1,it suffices to classify all znz-patterns of order two or three that are irreducible.

We begin with the 2×2 case by showing a much stronger result:

Theorem 5.1. Let F be any field. Then the znz-pattern

A= ∗ ∗

∗ ∗

is the only irreducible 2×2 potentially nilpotent pattern overF. Proof. The only irreducible 2×2 znz-patterns are

0 ∗

∗ 0 , ∗ ∗

∗ 0 , 0 ∗

∗ ∗ , and ∗ ∗

∗ ∗ .

The first three patterns cannot be potentially nilpotent overFby Corollary 3.7. The matrix

1_F 1_F

−1F −1F . is a desired realization ofA.

The following lemma is used to shorten some of the cases in the next theorem.

Lemma 5.2. LetAbe an irreduciblen×nznz-pattern. LetD(A)be the associated digraph.

(a) IfF =Z₂ andD(A) has an odd number of loops, thenA is not potentially nilpotent over F.

(b) If F=Z2 and D(A) has exactly two loops and two 2-cycles, then A is not potentially nilpotent over F=Z₂.

(c) The only solutions to the equation x+y+z= 0 with x, y, z∈Z3 andx,y, z nonzero are(1_F,1_F,1_F)and(2_F,2_F,2_F).

Proof. (a) Suppose thatD(A) has loops at (i₁, i₁), . . . ,(i_m, i_m) withm= 2k+ 1.

Then z_i1,i1 +· · ·+z_im,im ∈I_A. WhenF=Z2,we must havez_i,j = 1_F for all (i, j).

But this would imply that 1_F+· · ·+ 1_F=m_F= 0, which is false.

(b) Suppose that the diagonal entries ofA are at (i₁, i₁) and (i₂, i₂) and the two 2-cycles are (i₃, j₃) and (i₄, j₄). Then the polynomial

F₂=z_i1,i1z_i2,i2+z_i3,j3z_j3,i3+z_i4,j4z_j4,i4 ∈I_A.

IfF=Z2,then the only nonzero choice forz_i,j is 1_F. It then follows thatF₂ cannot equal zero inF=Z₂.