# Symmetric Integer Matrices Having Integer Eigenvalues

Authors: Lei Cao; Selcuk Koyuncu
Journal: International Journal of Mathematics and Mathematical Sciences
 (2016)

---

## Abstract

We provide characterization of symmetric integer matrices for rank at most 2 that have integer spectrum and give some constructions for such matrices of rank 3. We also make some connection between Hanlon’s conjecture and integer eigenvalue problem.


---

## Body

## 1. Introduction

The study of matrices with integer entries combines linear algebra, number theory, and group theory (the study of arithmetic groups). It was shown that the eigenvalues of symmetric matrices over the integersZ stem from as to what algebraic integers occur as eigenvalues for the incidence matrix of a graph (see [1]). Integer eigenvalues of a nonsymmetric matrix with entries as certain simple functions are presented in [2]. A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. A number of papers on Laplacian matrices investigate the class of Laplacian integral graphs (see [3–5]). Integer matrices that arise from Laplacians are connected to the three-dimensional Heisenberg Lie algebra and the eigenvalues and eigenvectors were explicitly given for the subclass of these matrices (see [6]). An interesting class of matrices called Bn was introduced in [7]; the most interesting property of the Bn-class is that the spectra of the matrices consist of the consecutive integers 0,1,…,n-1; that is, the eigenvalues do not depend on the values of the elements of B∈Bn. In this paper, we characterize all symmetric integer matrices for rank at most 2 that have integer spectrum and give some constructions for such matrices of rank 3. We also open a discussion on the fact that integer eigenvalue problem has strong connection with Hanlon’s conjecture (see [6]). We provide some examples and conjectures that relate these two problems.We start with some basic definitions from linear algebra. LetA be a square matrix of size n and let λ be a scalar quantity. Then PA(λ)=det⁡(A-λI) is called the characteristic polynomial of A. It is clear that the characteristic polynomial is an nth degree polynomial in λ and det⁡(A-λI)=0 will have n (not necessarily distinct) solutions for λ. The values of λ that satisfy det⁡(A-λI)=0 are the characteristic roots or eigenvalues of A. An n×n matrix A is called real symmetric if AT, the transpose of A, coincide with A. If A=[aij] is an m×n matrix and B=[bij] is an p×q matrix, then the tensor product of A and B, denoted by A⊗B, is the mp×nq matrix and is defined as (1)A⊗B=a11B⋯a1nB⋮⋱⋮am1B⋯amnB.If A is n×n and B is m×m, then the Kronecker sum (or tensor sum) of A and B, denoted by A⊕B, is the mn×mn matrix of the form (Im⊗A)+(B⊗In). Let Mn(Z) be the set of all n×n symmetric matrices with integer entries.LetA be an n×n matrix and A[k] be the sum of all kth order principal minors of A. Then all coefficients in the characteristic polynomial of A can be expressed by A[k] for k=1,2,…,n. In particular, A[1]=trace(A) and A[n]=det⁡(A).Lemma 1.
LetA∈Mn(R) with eigenvalues λ1,λ2,…,λn. The characteristic polynomial of A is given by (2)pAλ=det⁡λI-A=λn+cn-1λn-1+cn-2λn-2+⋯+c1λ+c0.Then(3)ci=An-i,i=0,…,n-1.Lemma 2.
LetA∈Mn(Z) with rank 1. Then A has integer eigenvalues.We now present the characterization of all symmetric integer matrices for rank at most 2 that have integer spectrum.


## 2. The Rank 2 Case

Theorem 3.
LetA∈Mn(Z) with rank 2. Then A has integer eigenvalues if and only if there exist two integers m and n such that trace(A)=m+n and A[2]=mn where A[2] is the sum of determinants of all 2nd order principal minors of A.Proof.
SinceA has rank 2, the characteristic polynomial of A has the form (4)λn-traceAλn-1+A2λn-2.It is clear that the two nonzero eigenvalues of A are (5)λ1=traceA+traceA2-4A22,λ2=traceA-traceA2-4A22.
“⇐” Suppose there exist integers m and n such that trace(A)=m+n and A[2]=mn. Then it follows that (6)λ1=m,λ2=n.
“⇒” If all eigenvalues of A are integers, then there exists an integer k such that(7)traceA2-4A2=k2.Letting (8)m=traceA+k2,m=traceA-k2and using (7), the difference of trace(A)2 and k2 is 4A[2] which is even, so either both trace(A) and k are even or both trace(A) and k are odd, and hence both m and n are integers.Lemma 4.
LetA=BCDE. If E is invertible and DE=ED, then det⁡(A)=det⁡(BE-CD).Theorem 5.
LetA=BCCB. Suppose both B and C are integer matrices of order n with integer eigenvalues. If B and C commute, then A has integer eigenvalues.Proof.
According to Lemma4, (9)det⁡λI2n-A=det⁡λI2n-B2-C2=det⁡λI2n-B-CλI2n-B+C.Since B and C commute, they can be diagonalized simultaneously and hence all eigenvalues of both B+C and B-C are integers.Lemma 6.
Let(10)A=BIO⋯OOBIO⋮⋮⋱⋱⋱OO⋯OBIO⋯⋯OB∈M2nZ.If B=abba∈M2(Z), then A has integer eigenvalues.Proof.
Define(11)J=010⋯00010⋮⋮⋱⋱⋱00⋯0010⋯⋯00∈MnZ.Then we can write A as(12)A=In⊗B+J⊗I2=B⊕J.Since B and J have integer eigenvalues, then A=B⊕J has also integer eigenvalues.We now give some constructions for all symmetric matrices of rank 3 that has integer spectrum.


## 3. The Rank 3 Case

Theorem 7.
LetA∈Mn(Z) be symmetric integer matrix with rank 3. If one of the following cases holds, then A has integer eigenvalues.(i)
One of the eigenvalues ofA is 1 or -1 and there exists a positive integer k such that (13)A3-A22+4A3=k2.(ii)
All nonzero eigenvalues ofA are the same and(14)A2=traceA23,A3=traceA327.(iii)
One of the nonzero eigenvalues ofA has multiplicity two and there exists a positive integer such that (15)traceA2-3A2=k2.(iv)
The trace ofA is equal to zero and there exists a positive integer k and integers m, n such that (16)k=A324+A2327,m3=A32+k,n3=A32-k.In fact, one of eigenvalues ism+n.Proof.
Since the rank ofA is 3, the characteristics polynomial of A can be written as(17)PAλ=λn-traceAλn-1+A2λn-2-A3λn-3=λn-3λ3-traceAλ2+A2λ-A3.(i)
Suppose that one of the eigenvalues ofA is λ=1. By substituting this eigenvalue in (17), one obtains(18)A3-A2=1-traceA.In addition, (17) can be factored as(19)PAλ=λn-3λ-1λ2+1-traceAλ+A3.By Theorem3, the quadratic factor has integer roots if and only if there exists a positive integer k, such that(20)1-traceA2+4A3=k2.Now combining (18) and (20) yields(21)A3-A22+4A3=k2.And in fact, the other eigenvalues are(22)λ2=1-traceA+k2,λ3=-1+traceA-k2which are integers because either both1-traceA and k are even or both of them are odd by (20).(ii)
Letλ~ be the only nonzero eigenvalue of A. Then (23)PAλ=λn-3λ-λ~3,(24)λ-λ~3=λ3-traceAλ2+A2λ-A3.By comparing the coefficients on both sides of (24), one obtains(25)traceA=3λ~,A2=3λ~2,A3=λ~3.Thus(26)A2=traceA23,A3=traceA327.(iii)
Suppose thatA has two nonzero eigenvalues λ1 and λ2 with multiplicity one and two, respectively. Then the characteristic polynomial of A can be written as (27)PAλ=λn-3λ-λ12λ-λ2,and hence(28)λ-λ12λ-λ2=λ3-traceAλ2+A2λ-A3.By comparing the coefficients on both sides of (28), one obtains(29)traceA=2λ1+λ2,A2=λ12+2λ1λ2,A3=λ12λ2.In addition, sinceλ1 has multiplicity two, both PA(λ1) and its derivative PA′(λ1) are equal to zero and hence(30)3λ12-2traceAλ1+A2=0.Now taking the derivative of both sides of (28), we get(31)3λ2-2traceAλ+A2=λ-λ12+2λ-λ1λ-λ2.Since (31) is quadratic and has one integer root λ1, then the other root must be rational. Thus there exists a positive integer k such that(32)4traceA2-12A2=2k2which yields that(33)traceA2-3A2=k2.(iv)
Denote the nonzero eigenvalues ofA by λ1, λ2, and λ3. We have λ3=-(λ1+λ2) due to zero trace. Also, we have the following equations(34)λ12+λ1λ2+λ22=-A2,(35)λ12λ2+λ1λ22=-A3.Multiplying (34) by λ1 yields that(36)λ13+λ12λ2+λ1λ22=-A2λ1.Subtracting (35) from (36), one obtains(37)λ13+A2λ1-A3=0.Note that the following(38)A32+A324+A33273+A32-A324+A23273=A32+k3+A32-k3=m+nis always a solution of (36). To see this, first note that(39)m·n=A32+k3·A32-k3=A324-A324-A23273=-A33,m+n3=m3+3m2n+3mn2+n3=A32+k+3mnm+n+A32-k=A32+k-A23·m+n+A32-k=-A23·m+n+A3.Lemma 8.
Let(40)F=11⋯111⋯1⋮⋮⋱⋮11⋯1∈Mmand let A=(F⊗B)+(C⊗Im). Then A has integer eigenvalues if BC=CB and both B and C have integer eigenvalues.Proof.
SinceB and C commute, they can be diagonalized simultaneously. Without loss of generality, suppose (41)B=b1b2⋱bn,C=c1c2⋱cn.Note that A has eigenvalues bi+(n-1)ci with multiplicity 1 for i=1,2,…,n and A has eigenvalue bi-ci with multiplicities m-1 for i=1,2,…,n since (bi-ci)I-A has rank (n-1)m.Lemma 9.
LetA∈Mn(Z). If A=A1⊗A2⊗⋯⊗Ak where each Ai has integer eigenvalues and Ai∈Mi(Z), i=1,…,k, then A has integer eigenvalues.Proposition 10.
LetAT=A∈M3(Z) and B=abba∈M2(Z). Suppose both A and B have integer eigenvalues. Then A⊕B has integer eigenvalues.In this section, we open a discussion on possible connection between integer eigenvalue problem and Hanlon’s conjecture. We support our approach with some examples and adopt the notation used in [6].


## 4. Connection to Hanlon’s Conjecture

Definition 11.
Leta, b, and k be nonnegative integers with a≤k+1 and b≤k+1. Let Ωk(a,b) be the set of pairs (U,V) such that U is an A-subset of k0 and V is a B-subset of k0, where k0={0,1,…,k} and k is a nonnegative integer. Define the weight of a pair (U,V) to be (42)WU,V=∑u∈Uu+∑v∈Vv.Let Ωk(a,b,w) be the set of pairs (U,V) such that W(U,V)=w.Example 12.
Leta=2, b=1, and w=4. If k=2, then the ordered basis is Ω2(2,1,4)={(12,1),(02,2)}. If k=3, the ordered basis is Ω2(2,1,4)={(13,0),(03,1),(12,1),(02,2),(01,3)}. In this case, if k=0 then Ω2(2,1,4)=∅.We define a matrixTk(a,b,w) with respect to corresponding basis Ωk(a,b,w). We need the following definition in order to define the matrix Tk(a,b,w).Definition 13.
Let(U,V) and (X,Y) be elements of Ωk(a,b,w), and let (u,v,z) be a triple with u∈U, v∈V and z is any integer. we say that (U,V) and (X,Y) are (u,v,z)-neighbors if(1)
X=(U∖{u})∪{u+z},(2)
Y=(Y∖{v})∪{v-z},(3)
u+v≤k.In [6] (Conjecture 1.12), it was conjectured that the eigenvalues Tk(a,b,w) are nonnegative integers. Let us present some examples.Example 14.
T 2 ( 2,1 , 4 ) with respect to the ordered basis {(12,1),(02,2)} is (43)2112.Theorem 3 guarantees that both eigenvalues of T2(2,1,4) are integers.Example 15.
T 3 ( 2,1 , 4 ) with respect to the ordered basis (44)13,0,03,1,12,1,02,2,01,3is(45)2110-1120111021-101121-11-112.If the last row and column are deleted, the resulting matrix is in the form of block matrix given in Theorem 5. The eigenvalues of (1,1)-block are 1, 3 and the eigenvalues of (2,2)-block are both 1 with multiplicity 2. The eigenvalues of T2(2,1,4) are 0,0,2,4,4. Notice that these eigenvalues can also be obtained from the sum and difference of (1,1) and (1,2) blocks with given multiplicities.Example 16.
T 4 ( 2,1 , 4 ) with respect to the ordered basis (46)04,0,13,0,03,1,12,1,02,2,01,3is(47)20101102110-111201101021-11011211-11-112.The eigenvalues of T4(2,1,4) are 0, 0, 1, 2, 4, and 5. We do not observe an obvious connection in this example.Example 17.
T 3 ( 3,2 , 5 ) with respect to the ordered basis (48)012,02is (49)4.Example 18.
T 3 ( 2,2 , 4 ) with respect to the ordered basis (50)13,01,12,02,02,12,01,13is(51)3101131001311013.Notice that the matrix T3(2,2,4) is in block form given in Theorem 5 and its eigenvalues are the eigenvalues of the sum and difference of (1,1) and (2,2)-blocks with given multiplicities. In this case the eigenvalues are 1, 3, 3, and 5.Example 19.
T 3 ( 2,2 , 6 ) with respect to the ordered basis(52)23,01,13,02,03,12,03,03,12,12,12,03,02,13,01,23is(53)31-111-1101311110-1-1120001-11103001111003011-1100021-11011113101-111-113.Note that some examples given above follow directly from the theory we have provided and some do not. We aim to search more general connections in a followup paper. In [6], the author search for algebraic expression for the eigenvalues. We use the same notation and state the conjecture. For each a, b, w, k, and each nonnegative integer r, let μk(a,b,w;r) denote the multiplicity of r as an eigenvalue of Tk(a,b,w). Let(54)μka,b;r=∑wμka,b,w;r.LetMk(x,y,λ) be the following generating function for the numbers μk(a,b;r):(55)Mkx,y,λ=∑a,b,rμka,b;rxaybλr.It was conjectured in [6] (Conjecture 1.14) that Mk(x,y,λ)=∏i=0k‍(1+x+y+λi+1xy). This conjecture is still open in general. We hope to find more obvious connections and use them to solve given conjectures in this paper.



---

*Source: 3471438-2016-11-07.xml*