# The Spectrum and Eigenvectors of the Laplacian Matrices of the Brualdi-Li Tournament Digraphs

Authors: Xiaogen Chen
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Letm≥1 be an integer, let ℬ2m denote the Brualdi-Li matrix of order 2m, and let ℒℬ2m denote the Laplacian matrices of Brualdi-Li tournament digraphs. We obtain the eigenvalues and eigenvectors of ℒℬ2m.


---

## Body

## 1. Introduction

The Laplacian spectral theory is currently not only a hot research direction of spectral graph theory but also one of the research directions of combined matrix theory. The Laplacian spectrum of a graph is of importance in graph theory, matrix theory, and the definite solution of partial differential equations. It also has applications in quantum chemistry, biology, and complex network. Therefore, it has important theoretical and practical values to study the Laplacian eigenvalues and eigenvectors of graphs. The Laplacian spectrum of graph has attracted the attention of researchers; see [1–5] and so on. We follow [1, 6] for terminology and notations.LetG be a digraph of order n with vertex set V(G) and arc set E(G), where V(G)={v1,v2,…,vn}. The adjacency matrix of G is the (0,1) matrix A(G)=(aij) of order n, where aij=1 if there is an arc from vi to vj and aij=0 otherwise. The digraph G is called the associated digraph of matrix A(G). Let D(G)=diag⁡(d1,d2,…,dn), the diagonal matrix with vertex outdegrees d1,d2,…,dn of v1,v2,…,vn. L(G)=D(G)-A(G) is called the Laplacian matrix of the digraph G. The characteristic polynomial of the adjacency matrix A(G), that is, P(G,λ)=P(A(G),λ)=det⁡(λI-A(G)), is called the characteristic polynomial of the digraph G. The equation det⁡(λI-A(G))=0 has n complex roots and these roots are called the eigenvalues of A(G). Suppose the distinct eigenvalues of L(G) are denoted by λ1,λ2,…,λr∈ℂ with corresponding algebraic multiplicities μλ1,μλ2,…,μλr, where μλi is a nonnegative integer i=1,2,…,r. LS=(λ1λ2⋯λrμλ1μλ2⋯μλr) is called the Laplacian spectrum of digraph G. The Laplacian spectral radius of G is the largest modulus of an eigenvalue of L(G), denoted by ρ(L(G)). The symbol ℂ will denote the complex field. Let λ∈ℂ be an eigenvalue of matrix A. There is vector x≠0 satisfying Ax=λx, and then x is called the eigenvectors of matrix A corresponding to λ.A tournament matrix of ordern is a (0,1) matrix Tn satisfying the equation Tn+Tnt=Jn-In, where Jn is the all ones matrix, In is the identity matrix, and Tnt is the transpose of Tn. Let
(1)ℬ2m=(UmUmtIm+UmtUm),
where Um is strictly upper triangular tournament matrix (all of whose entries above the main diagonal are equal to one); that is,(2)Um=(011⋯1001⋯1⋮⋱⋱⋱⋮00⋯0100⋯00)m×m
is the tournament matrix of order 2m.The matrixℬ2m has been dubbed by the Brualdi-Li matrix. The associated digraph of matrix ℬ2m is called the Brualdi-Li tournament digraph. In 1983 Brualdi and Li conjectured that the maximal spectral radius for tournaments of order 2m is attained by the Brualdi-Li matrix [7]. This conjecture has been confirmed in [8]. The properties of the Brualdi-Li matrix have been investigated in [9–14].In this paper, we obtain the spectrum and eigenvectors of the Laplacian matrices of the Brualdi-Li tournament digraphs.Theorem 1.
Letm≥1 be an integer, and let 𝒮ℒℬ2m be the Laplacian spectrum of the Brualdi-Li tournament digraph. Then
(3)𝒮ℒℬ2m=(0mλkλk¯1⌊m-12⌋+⌊m+12⌋11),
where ⌊a⌋ is the floor of number a, λk=m-icot((π+2kπ)/2m), and λk¯ is the conjugate complex number of λk, k=0,1,2,…,⌊m/2⌋-1.Theorem 2.
Letm≥1 be an integer, and let ξ=(vw)≠0 be the eigenvector of ℒℬ2m corresponding to λ, where v=(v1,v2,…,vm)t, w=(w1,w2,…,wm)t; then(1)
ifλ=m, thenξm=(01) is the eigenvector of ℒℬ2 corresponding to λ=m=1,ξm=(1,-1,1,-1)t is the eigenvector of ℒℬ4 corresponding to λ=m=2,ξm=∑k=2m‍lkξmk is the eigenvector of ℒℬ2m corresponding to λ=m>2,wherelk is an arbitrary constant, k=2,3,…,m,
(4)(ξm2,ξm3,…,ξmm)=(1m-2t1-Im-200-11m-2t1-Im-200-1)2m×(m-1);(2)
ifλ≠m, then
(5)vk=12(m-λ)(1-λ(m-1-λm+1-λ)k-1),wk=12(m-λ)(1+λ(m-1-λm+1-λ)k),hhhhhhhhhhhhhhhhhhhk=1,2,⋯,m.Corollary 3.
Letm≥1 be an integer, and let ρ(ℒℬ2m) be the Laplacian spectral radius of the Brualdi-Li tournament digraph. Then
(6)ρ(ℒℬ2m)=m2+cot2π2m.Proof.
By Theorem1,
(7)ρ(ℒℬ2m)=max⁡0≤k≤⌊m/2⌋-1{0,m,|m±icotπ+2kπ2m|}=m2+cot2π2m.Corollary 4.
Letm≥1 be an integer, then(1)
ifm>1 is odd, then ℒℬ2m is not diagonalizable,(2)
ifm is even or m=1, then ℒℬ2m is diagonalizable.


## 2. Some Lemmas

Fundamental Theorem of Algebra. Every nonzero, single-variable, degree n polynomial with complex coefficients has, counted with multiplicity, exactly n roots.Complex Conjugate Root Theorem. If P is a polynomial in one variable with real coefficients and a+bi is a root of P with a and b real numbers, then its complex conjugate a-bi is also a root of P, where i2=-1.The symbolℒℬ2m denotes the Laplacian matrix of the Brualdi-Li tournament digraph. Clearly, ℒℬ2m=((m-1)Im-Um-Umt-Im-UmtmIm-Um).Lemma 5.
Letm>1 be an integer, and X=(1,x,x2,…,xm-1)t, where x≠1 is real variable. Then
(8)(1)XtUm=-11-xXt+11-x1mt,(2)XtUmt=x1-xXt-xm1-x1mt.Proof.
Consider(9)(1)XtUm=(1,x,x2,…,xm-1)Um=(0,∑k=00‍xk,∑k=01‍xk,∑k=02‍xk,∑k=03‍xk,…,∑k=0m-3‍xk,∑k=0m-2‍xk)=(1-11-x,1-x1-x,1-x21-x,1-x31-x,…,1-xm-21-x,1-xm-11-x)=-11-xXt+11-x1mt.(2)XtUmt=(1,x,x2,…,xm-1)Umt=(∑k=1m-1‍xk,∑k=2m-1‍xk,…,∑k=m-2m-1‍xk,∑k=m-1m-1‍xk,0)=(x-xm1-x,x2-xm1-x,…,xm-2-xm1-x,xm-1-xm1-x,xm-xm1-x)=x1-xXt-xm1-x1mt.Lemma 6.
Letm>1 be an integer, λ≠m, let λ∈ℂ be an arbitrary eigenvalue of ℒℬ2m, and let ξ=(vw)≠0 be the eigenvector of ℒℬ2m corresponding to λ, where v=(v1,v2,…,vm)t, w=(w1,w2,…,wm)t. Let X=(1,x,x2,…,xm-1)t, f(x)=∑k=1m‍vkxk-1, and g(x)=∑k=1m‍wkxk-1, where x is real variable. Then
(10)(1)f(x)=((m+1-λ)a+(a+b)(x+x2+⋯+xm-1)+(a-b(m-λ))xmxm-1)×((m-λ)((m+1-λ)-(m-1-λ)x))-1,(2)g(x)=(a+b(m-λ)+(a+b)(x+x2+⋯+xm-1)-a(m-1-λ)xmxm-1)×((m-λ)((m+1-λ)-(m-1-λ)x))-1,
where a=1mtv, b=1mtw.Proof.
Ifλ(≠m) is an eigenvalue, with eigenvector ξ=(vw), of ℒℬ2m, then ℒℬ2mξ=λξ expands to
(11)((m-1)Im-Um-Umt-Im-UmtmIm-Um)(vw)=λ(vw).
Therefore,
(12)((m-1)Im-Um)v-Umtw=λv,(-Im-Umt)v+(mIm-Um)w=λw.
We have
(13)Xt((m-1)Im-Um)v-XtUmtw=λXtv,Xt(-Im-Umt)v+Xt(mIm-Um)w=λXtw.
According to Lemma 5, we have
(14)((m-1-λ)(1-x)+1)f(x)-xg(x)=a-bxm-f(x)+((m-λ)(1-x)+1)g(x)=b-axm.
Notice that this equation holds for x=1 too. Consider
(15)D=det⁡((m-1-λ)(1-x)+1-x-1(m-λ)(1-x)+1)=((m-1-λ)(1-x)+1)((m-λ)(1-x)+1)-x=(m-λ)(1-x)((m+1-λ)-(m-1-λ)x),Df=det⁡(a-bxm-xb-axm(m-λ)(1-x)+1)=(a-bxm)((m-λ)(1-x)+1)+x(b-axm)=a(m+1-λ)+(b-a(m-λ))x-b(m+1-λ)xm+(b(m-λ)-a)xm+1=(1-x)(a(m+1-λ)+(a+b)(x+⋯+xm-1)+(a-b(m-λ))xm(x+⋯+xm-1)),Dg=det⁡((m-1-λ)(1-x)+1a-bxm-1b-axm)=(b-axm)((m-1-λ)(1-x)+1)+(a-bxm)=a+b(m-λ)-b(m-1-λ)x-(b+a(m-λ))xm+a(m-1-λ)xm+1=(1-x)(a+b(m-λ)+(a+b)(x+⋯+xm-1)-a(m-1-λ)xm(x+⋯+xm-1)).
By Cramer’s rule,
(16)(1)f(x)=((m+1-λ)a+(a+b)(x+x2+⋯+xm-1)+(a-b(m-λ))xm(x+x2+⋯+xm-1))×((m-λ)((m+1-λ)-(m-1-λ)x))-1,(2)g(x)=(a+b(m-λ)+(a+b)(x+x2+⋯+xm-1)-a(m-1-λ)xm(x+x2+⋯+xm-1))×((m-λ)((m+1-λ)-(m-1-λ)x))-1.
We are done.Lemma 7.
Under the assumptions and in the notation of Lemma6,
(17)a+b=1mtv+1mtw≠0,a=1mtv≠0,b=1mtw≠0.Proof.
In Lemma6(1), by setting x=1, we have
(18)a=f(1)=(m+1-λ)a+(a+b)(m-1)+(a-b(m-λ))(m-λ)((m+1-λ)-(m-1-λ)).
Since λ≠m, it follows that
(19)(a+b)(1-λ)=2a.
As we all know that the eigenvalues of a real skew-symmetric matrix are all pure imaginary or nonzero, hence det⁡((1-m)Im+U-Ut)≠0, where m>1. Since
(20)det⁡(1Im-ℒℬ2m)=det⁡((2-m)Im+UmUmtIm+Umt(1-m)Im+Um)=det⁡((2-m)Im+Um(2-m)Im+Um+UmtIm+Umt(2-m)Im+Um+Umt)=det((1-m)Im+U-Ut0Im+Umt(1-m)Im+Jm)=det⁡((1-m)Im+U-Ut)det⁡((1-m)Im+Jm)=(1-m)m-1det⁡((1-m)Im+U-Ut)≠0,
hence λ≠1. Notice that (a+b)(1-λ)=2a and if a+b=0, then a=0 and b=(a+b)-a=0. By Lemma 6,
(21)f(x)=∑k=1m‍vkxk-1≡0,g(x)=∑k=1m‍wkxk-1≡0,
for arbitrary real variable x. It is not possible. Hence a+b≠0. It is easy to see that a≠0 and b≠0.Lemma 8 (see [15]).
IfA is a square matrix, then,(1)
for every eigenvalue ofA, the geometric multiplicity is less than or equal to the algebraic multiplicity,(2)
A is diagonalizable if and only if the geometric multiplicity of every eigenvalue is equal to the algebraic multiplicity.


## 3. Proof of Theorem1

Letλ∈ℂ be an arbitrary eigenvalue of ℒℬ2m, and let ξ=(vw)≠0 be the eigenvector of ℒℬ2m corresponding to λ, where v=(v1,v2,…,vm)t, w=(w1,w2,…,wm)t.Form=1, then ℬ2=(0010), ℒℬ2=(00-11). Obviously, λ1=0, λ2=1 are eigenvalues of ℒℬ2 and μ0=μ1=1. Theorem 1 holds.Form>1, using the previous assumptions and notation, obviously, P(ℒℬ2m,0)=det⁡(0I2m-ℒℬ2m)=0, by definition, λ=0 is an eigenvalue of ℒℬ2m, μ0≥1.Note thatP(ℒℬ2m,m)=det⁡(mI2m-ℒℬ2m)=0, and by definition, λ=m is an eigenvalue of ℒℬ2m. By simple calculation, the rank of matrix mI2m-ℒℬ2m is equal to m+1. By Lemma 8(1)  μm≥2m-(m+1)=m-1.Forλ≠m, by Lemma 7, we set a=1mtv,a+b=1mtv+1mtw=1; hence b=1-1mtv=1-a. In Lemma 6(1), by setting x=1, we have
(22)a=1mtv=f(1)=(m+1-λ)a+m-1+a+(a-1)(m-λ)(m-λ)((m+1-λ)-(m-1-λ))=(m-λ)(2a-1)+m+2a-12(m-λ).Hence(23)a=1-λ2.
Denoting f0=(m+1-λ)a,f1=f2=⋯=fm-1=1,fm=a+(a-1)(m-λ), c=(m-λ)(m+1-λ), and d=(m-1-λ)/(m+1-λ), we have
(24)f(x)=∑k=1m‍vkxk-1=((m+1-λ)a+x+x2+⋯+xm-1+(a+(a-1)(m-λ))xmxm-1)×((m-λ)((m+1-λ)-(m-1-λ)x))-1=1c1(1-dx)∑k=0m‍fkxk=1c∑k=0∞‍dkxk∑k=0m‍fkxk=1c∑k=0∞‍(∑j=0k‍fjdk-j)xk.It must be that(25)vk=1c∑j=0k-1‍fjdk-1-j,k=1,2,…,m.Therefore(26)a=∑k=1m‍vk=1c∑k=1m‍∑j=0k-1‍fjdk-1-j=1c∑k=1m‍(f0dk-1+∑j=1k-1‍dk-1-j)=1c∑k=1m‍(f0dk-1+1-dk-11-d)=1c(1-d)2×(f0(1-dm)(1-d)+m(1-d)-1+dm)=1c(1-d)2×((1-f0(1-d))dm+(f0+m)(1-d)-1).
That is, ac(1-d)2=(1-f0(1-d))dm+(f0+m)(1-d)-1.Sincea=(1-λ)/2, f0=(m+1-λ)a, c=(m-λ)(m+1-λ), and d=(m-1-λ)/(m+1-λ), then
(27)(1-f0(1-d))dm=ac(1-d)2-(f0+m)(1-d)+1,(1-2a(m+1-λ)m+1-λ)dm=4a(m-λ)m+1-λ-2((m+1-λ)a+m)m+1-λ+1,λdm=-λ.
Denote θk=(π+2kπ)/2m, k=0,1,2,m-1. As λ≠0,λ-m≠0, we have d=e2iθk; that is, (m-1-λ)/(m+1-λ)=e2iθk, where i2=-1.Therefore,(28)λ=λk=m-1+e2iθk1-e2iθk=m-isin2θk1-cos⁡2θk=m-icotθk,
where 1-e2iθk≠0, k=0,1,2,…,m-1.Note that ifm is odd, by dm=((m-1-λ)/(m+1-λ))m=-1, then (m-1-λ)/(m+1-λ)=-1; hence λ=m. It is an eigenvalue of ℒℬ2m.Furthermore,μλk≥1. Note that λk¯=λm-1-k, k=0,1,2,…,⌊m/2⌋-1.To sum up, by fundamental theorem of algebra and complex conjugate root theorem, form≥1, we obtain the following conclusions.Ifm is odd, then μ0=μλk=μλk¯=1 and μm=m=⌊(m-1)/2⌋+⌊(m+1)/2⌋.Ifm is even, then μ0=μλk=μλk¯=1 and μm=m-1=⌊(m-1)/2⌋+⌊(m+1)/2⌋.Considerk=0,1,2,…,⌊m/2⌋-1. We complete the proof of Theorem 1.


## 4. Proofs of Theorem2 and Corollary 4

It is easy to see that the distinct eigenvalues ofℒℬ2m are 0,λk=m-icot((π+2kπ)/2m),λk¯,m, with corresponding algebraic multiplicities 1,1,1,⌊(m-1)/2⌋+⌊(m+1)/2⌋, k=1,2,…,⌊m/2⌋-1.Forλ=m=1, ℒℬ2=(00-11) and, obviously, ξm=(01) is the eigenvector of ℒℬ2 corresponding to λ=m=1.Forλ=m=2,
(29)ℒℬ4=(1-10001-10-102-1-1-102).By simple calculation,ξm=(1,-1,1,-1)t is the eigenvector of ℒℬ4 corresponding to λ=m=2.Forλ=m>2, let ξm=(vw)≠0 be the eigenvector of ℒℬ2m corresponding to m, and then ℒℬ2mξm=mξm expands to
(30)(Im+UmUmtIm+UmtUm)(vw)=0.
Equation (30) is equivalent to the following equation:
(31)(Im(I+Um)-1Umt0mUm-(Im-Umt)(I+Um)-1Umt)(vw)=0.By simple calculation,(32)(I+Um)-1Umt=(-Im-101m-1t0),Um-(Im-Umt)(I+Um)-1Umt=(Jm-11m-100).
We obtain the solution of (30) as follows:
(33)ξm=∑k=2m‍lkξmk,
where lk is an arbitrary constant, k=2,3,…,m, and
(34)(ξm2,ξm3,…,ξmm)=(1m-2t1-Im-200-11m-2t1-Im-200-1)2m×(m-1).Forλ≠m, let ξ=(vw)≠0 be the eigenvector of ℒℬ2m corresponding to λ(≠m), where v=(v1,v2,…,vm)t, w=(w1,w2,…,wm)t; then ℒℬ2mξ=λξ expands to
(35)((m-1)Im-Um-Umt-Im-UmtmIm-Um)(vw)=λ(vw).
By Lemma 7, 1mtv+1mtw≠1; we put 1mtv+1mtw=1. By Theorem 1, a=1mtv=(1-λ)/2, b=1mtw=1-a.Denoteg0=a+(1-a)(m-λ), g1=g2=⋯=gm-1=1, and gm=-a(m-1-λ). By Lemma 6(2) we have
(36)g(x)=∑k=1m‍wkxk-1=(a+(1-a)(m-λ)+x+x2+⋯+xm-1-a(m-1-λ)xmxm-1)×((m-λ)((m+1-λ)-(m-1-λ)x))-1=1c1(1-dx)∑k=0m‍gkxk=1c∑k=0∞‍dkxk∑k=0m‍gkxk=1c∑k=0∞‍(∑j=0k‍gjdk-j)xk.
It must be that
(37)wk=1c∑j=0k-1‍gjdk-1-j,k=1,2,…,m.
Hence
(38)wk=1c∑j=0k-1‍gjdk-1-j=1c(1-λ+(1+λ)(m-λ)2dk-1+∑j=0k-2‍dj)=1c(1-λ+(1+λ)(m-λ)2dk-1+1-dk-11-d)=12(m-λ)(1+λ(m-1-λm+1-λ)k),k=1,2,…,m.
In the proof of Theorem 1, we have
(39)vk=1c∑j=0k-1‍fjdk-1-j=1c((m+1-λ)(1-λ)2dk-1+∑j=0k-2‍dj)=1c((m+1-λ)(1-λ)2dk-1+1-dk-11-d)=12(m-λ)(1-λ(m-1-λm+1-λ)k-1),k=1,2,…,m.
We complete the proof of Theorem 2.Letλ be an eigenvalue of ℒℬ2m, and μλ and νλ are the algebraic multiplicity and the geometric multiplicity corresponding to λ, respectively.Ifm=1, by Theorem 1 and Theorem 2, and  μ0=ν0=μ1=ν1=1, then ℒℬ2 is diagonalizable.Ifm>1, by Theorem 1, μ0=1, μm=⌊(m-1)/2⌋+⌊(m+1)/2⌋, and  μλk=μλk¯=1, where λk=m-icot((π+2kπ)/2m), k=0,1,2,⋯,⌊m/2⌋-1.By Theorem2, ν0=1, νm=m-1, and νλk=νλk¯=1. We have the following:ifm>1 is odd, then m=μm≠νm=m-1;ifm is even, then μλ=νλ, where λ=0,m,λk,λk¯, k=0,1,2,…,⌊m/2⌋-1.By Lemma8(2), Corollary 4 holds.



---

*Source: 940834-2014-05-14.xml*