betaFeedback

WorksMathematics

Spectra of gcd-graphs over a matrix ring

Abstract

In this short note, we calculate the spectra of gcd-graphs defined over a matrix ring. Using character sums, we show that this calculation can be reduced to certain counting problems. In particular, when the underlying ring is a matrix ring with coefficients in a finite field, we calculate these spectra explicitly. We will also show that two gcd-graphs over the same matrix ring are isospectral if and only if they have the same generating set.

Introduction

Gcd-graphs were first introduced by Klotz and Sander [4]. These graphs lie at the intersection of algebra, number theory, and discrete analysis, and therefore they naturally exhibit many elegant properties. Ever since this article, subsequent works have generalized the notion of a gcd-graph to an arbitrary finite ring RR (see [7, 9]). Let us first recall the theory of Cayley graphs over RR. Let SS be a symmetric subset of (R,+)(R,+) such that 0∉S0 \notin S. The Cayley graph Γ(R,S)\Gamma(R,S) is defined as follows

  1. The vertex set of Γ(R,S)\Gamma(R,S) is RR.

  2. Two vertices u,vu,v are adjacent if u−v∈Su-v \in S.

We say that Γ(R,S)\Gamma(R,S) is a gcd-graph if SS is stable under left and right actions of the unit group R×R^{\times}; i.e., R×SR×=SR^{\times} S R^{\times}=S. In this setting, the interplay between the additive and multiplicative structures of RR has played a fundamental role in understanding the geometry of their associated gcd-graphs. Furthermore, when the underlying ring RR is a finite commutative Frobenius ring, we showed in previous work that the spectra of gcd-graphs over RR can be described by various arithmetical sums such as Gauss sums, Ramanujan sums, and Heilbronn sums (see [8, 9]). The goal of this article is to extend these calculations to the general case where RR is a finite symmetric Fq\mathbb{F}_q-algebra which could be non-commutative. When RR is a matrix ring with coefficients in a finite field, our approach gives complete and explicit formulas for the spectra of gcd-graphs defined over RR. To achieve this goal, we use the counting formula of Balasubramanian, Kaipa, and Khurana [1], who also identify the relevant quantities with character sums over matrices of prescribed rank. Our approach to calculating the spectra is similar in spirit to the work of Eichler and Lamprecht; see the introduction of [1] for a historical overview. Finally, we also show that the rank counts form a super collection and we use this fact to deduce that the degree of a gcd-graph over a fixed matrix ring determines its generating set. This proves a natural analogue of So’s conjecture for gcd-graphs defined over a matrix ring.

2020 Mathematics Subject Classification. Primary 05C50; Secondary 05C25, 15B33.

Key words and phrases. Gcd graphs, Finite rings, Partial Traces, Character Sums.

Spectra of a Cayley graph over a finite symmetric algebra

In this section, we recall the theory of finite symmetric Frobenius algebras and the associated spectra of Cayley graphs defined over them. This theory is discussed in [10].

Let RR be a finite-dimensional Fq\mathbb{F}_q-algebra. We say that RR is a finite symmetric Frobenius Fq\mathbb{F}_q-algebra if there exists a non-degenerate linear functional Ψ:R→Fq\Psi:R\to\mathbb{F}_q such that Ψ(ab)=Ψ(ba)\Psi(ab)=\Psi(ba). Here, non-degenerate means that the kernel of Ψ\Psi does not contain any non-zero left ideal in RR. Equivalently, the map R→Hom⁡Fq(R,Fq)R\to\operatorname{Hom}_{\mathbb{F}_q}(R,\mathbb{F}_q) defined by a↦Φaa\mapsto\Phi_a where Φa(u)=Ψ(au)\Phi_a(u)=\Psi(au) is an isomorphism of Fq\mathbb{F}_q-vector spaces. Let

Ψ~=Tr⁡Fq/Fp∘Ψ:R⟶Fp.\widetilde{\Psi}=\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}\circ\Psi:R\longrightarrow\mathbb{F}_p.

Here Tr⁡Fq/Fp\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p} is the trace map from Fq\mathbb{F}_q to Fp\mathbb{F}_p. The pairing (a,b)↦Ψ~(ab)(a,b)\mapsto\widetilde{\Psi}(ab) is also nondegenerate, showing that RR is also a finite symmetric Fp\mathbb{F}_p-algebra.

Let Γ(R,S)\Gamma(R,S) be a Cayley graph over RR, where 0∉S0\notin S and SS is stable under Fq×\mathbb{F}_q^\times. Let ζp=e2πi/p\zeta_p=e^{2\pi i/p}. The additive characters of RR are

χr(x)=ζpΨ~(rx),r∈R.\chi_r(x)=\zeta_p^{\widetilde{\Psi}(rx)},\qquad r\in R.

By the theory of RR-circulant matrices (see [3]), we know that the spectrum of Γ(R,S)\Gamma(R,S) consists of the eigenvalues

λr=∑s∈SζpΨ~(rs)=∑s∈SζpTr⁡Fq/Fp(Ψ(rs)),r∈R,\lambda_r=\sum_{s\in S}\zeta_p^{\widetilde{\Psi}(rs)}=\sum_{s\in S}\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(\Psi(rs))},\qquad r\in R,

with one eigenvalue for each r∈Rr\in R, counting multiplicities. We will show below that, in some cases, the calculation of λr\lambda_r can be reduced to certain counting problems. To do so, we start with a simple lemma in character theory.

Lemma 2.1. Let u∈Fqu\in\mathbb{F}_q. Then

∑a∈Fq×ζpTr⁡Fq/Fp(au)={q−1,u=0,−1,u≠0.\sum_{a\in\mathbb{F}_q^\times}\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(au)} = \begin{cases} q-1, & u=0,\\ -1, & u\ne0. \end{cases}

Proof. The map

Fq⟶C×,a⟼ζpTr⁡Fq/Fp(au)\mathbb{F}_q\longrightarrow\mathbb{C}^\times,\qquad a\longmapsto\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(au)}

is an additive character of Fq\mathbb{F}_q. If u=0u=0, it is the trivial character. If u≠0u\ne0, it is nontrivial, so its sum over Fq\mathbb{F}_q is zero. Removing the term a=0a=0 gives the result. □

Let us introduce the counting numbers.

Ar=#{s∈S:Ψ(rs)=0},Br=#{s∈S:Ψ(rs)≠0}.A_r=\#\{s\in S:\Psi(rs)=0\},\qquad B_r=\#\{s\in S:\Psi(rs)\ne0\}.

Then Ar+Br=∣S∣A_r+B_r=|S|. We are now ready to express λr\lambda_r in terms of these counting numbers.

Proposition 2.2. For each r∈Rr\in R, we have

λr=qAr−∣S∣q−1.\lambda_r=\frac{qA_r-|S|}{q-1}.

Proof. Let us write S/Fq×={[s1],…,[sd]}S/\mathbb{F}_q^\times=\{[s_1],\ldots,[s_d]\} for the scalar orbits. Since 0∉S0\notin S, every orbit has q−1q-1 elements. Therefore

λr=∑i=1d∑s∈[si]ζpTr⁡Fq/Fp(Ψ(rs))=∑i=1d∑a∈Fq×ζpTr⁡Fq/Fp(Ψ(rasi))=∑i=1d∑a∈Fq×ζpTr⁡Fq/Fp(aΨ(rsi)).\lambda_r=\sum_{i=1}^{d}\sum_{s\in[s_i]}\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(\Psi(rs))} =\sum_{i=1}^{d}\sum_{a\in\mathbb{F}_q^\times}\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(\Psi(ras_i))} =\sum_{i=1}^{d}\sum_{a\in\mathbb{F}_q^\times}\zeta_p^{\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p}(a\Psi(rs_i))}.

The condition Ψ(rs)=0\Psi(rs)=0 is constant on each scalar orbit. By Lemma 2.1,

λr=Arq−1(q−1)+Brq−1(−1)=Ar−Brq−1=Ar−∣S∣−Arq−1=qAr−∣S∣q−1.\lambda_r=\frac{A_r}{q-1}(q-1)+\frac{B_r}{q-1}(-1)=A_r-\frac{B_r}{q-1}=A_r-\frac{|S|-A_r}{q-1}=\frac{qA_r-|S|}{q-1}.

Applications to gcd-graphs over a matrix ring

In this section, we focus on the case R=Mn(Fq)R=M_n(\mathbb{F}_q). In this case, Mn(Fq)M_n(\mathbb{F}_q) is a symmetric Frobenius ring with respect to the matrix trace map. Let

Vm={B∈Mn(Fq):rank⁡(B)=m}.V_m=\{B\in M_n(\mathbb{F}_q):\operatorname{rank}(B)=m\}.

In [11], using the theory of row and column operations, we show that Γ(Mn(Fq),S)\Gamma(M_n(\mathbb{F}_q),S) is a gcd-graph if and only if S=⋃m∈DVmS=\bigcup_{m\in\mathcal{D}}V_m, where D⊆{1,…,n}\mathcal{D}\subseteq\{1,\ldots,n\}. In this case, we will write Γ(Mn(Fq),D)\Gamma(M_n(\mathbb{F}_q),\mathcal{D}) for Γ(Mn(Fq),S)\Gamma(M_n(\mathbb{F}_q),S).

For X∈Mn(Fq)X\in M_n(\mathbb{F}_q), write

AX=#{B∈S:tr⁡(XB)=0}.A_X=\#\{B\in S:\operatorname{tr}(XB)=0\}.

Lemma 3.1. If rank⁡(X)=rank⁡(Y)\operatorname{rank}(X)=\operatorname{rank}(Y), then AX=AYA_X=A_Y.

Proof. We can write X=PYQX=PYQ for some P,Q∈GL⁡n(Fq)P,Q\in\operatorname{GL}_n(\mathbb{F}_q). Thus

AX=#{B∈S:tr⁡(PYQB)=0}=#{B∈S:tr⁡(YQBP)=0}=#{C∈S:tr⁡(YC)=0}=AY.\begin{aligned} A_X&=\#\{B\in S:\operatorname{tr}(PYQB)=0\}\\ &=\#\{B\in S:\operatorname{tr}(YQBP)=0\}\\ &=\#\{C\in S:\operatorname{tr}(YC)=0\}\\ &=A_Y. \end{aligned}

Here C=QBPC=QBP, and B↦QBPB\mapsto QBP is a rank-preserving bijection of SS.

For 0≤k≤n0\leq k\leq n, let

In(k)=(Ik000).I_n(k)=\begin{pmatrix}I_k&0\\0&0\end{pmatrix}.

By Lemma 3.1, we only need to calculate

AS,k:=AIn(k)=#{B∈S:tr⁡(In(k)B)=0}.A_{S,k}:=A_{I_n(k)}=\#\{B\in S:\operatorname{tr}(I_n(k)B)=0\}.

If

B=(B11B12B21B22),B11∈Mk(Fq),B=\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix},\qquad B_{11}\in M_k(\mathbb{F}_q),

then

In(k)B=(B11B1200),tr⁡(In(k)B)=tr⁡(B11)=∑i=1kbii.I_n(k)B=\begin{pmatrix}B_{11}&B_{12}\\0&0\end{pmatrix},\qquad\operatorname{tr}(I_n(k)B)=\operatorname{tr}(B_{11})=\sum_{i=1}^{k}b_{ii}.

Consequently,

AS,k=∑m∈DAm,kA_{S,k}=\sum_{m\in D}A_{m,k}

where

Am,k=#{B=(bij)∈Mn(Fq):rank⁡(B)=m, ∑i=1kbii=0}(1)A_{m,k}=\#\left\{B=(b_{ij})\in M_n(\mathbb{F}_q):\operatorname{rank}(B)=m,\ \sum_{i=1}^{k}b_{ii}=0\right\} \tag*{(1)}

Here nn and qq are fixed. In particular, Am,0=∣Vm∣A_{m,0}=|V_m|.

It turns out that there is a neat formula for Am,kA_{m,k} recently discovered in [1]. Let us briefly recall this formula. First, let us write

a(N,r,q)=∏j=0r−1(qN−qj)2qr−qj,0≤r≤N,a(N,r,q)=\prod_{j=0}^{r-1}\frac{(q^N-q^j)^2}{q^r-q^j},\qquad0\leq r\leq N,

with a(N,0,q)=1a(N,0,q)=1. This is the number of rank-rr matrices in MN(Fq)M_N(\mathbb{F}_q). In particular, ∣Vm∣=a(n,m,q)|V_m|=a(n,m,q).

Theorem 3.2 ([1 Theorem 1.1]). For 0≤m,k≤n0\leq m,k\leq n, we have

Am,k=a(n,m,q)+(q−1)gn,m,kq,A_{m,k}=\frac{a(n,m,q)+(q-1)g_{n,m,k}}{q},

where

gn,m,k=∑i=max⁡{0,m−(n−k)}min⁡{m,k}(−1)iq(i2)+k(m−i)(ki)qa(n−k,m−i,q).g_{n,m,k}=\sum_{i=\max\{0,m-(n-k)\}}^{\min\{m,k\}}(-1)^i q^{\binom{i}{2}+k(m-i)}\binom{k}{i}_q a(n-k,m-i,q).

Here (ki)q\binom{k}{i}_q is the Gaussian binomial coefficient.

The case k=0k=0 follows directly from gn,m,0=a(n,m,q)g_{n,m,0}=a(n,m,q).

Theorem 3.3. The eigenvalues of the gcd-graph Γ(Mn(Fq),S)\Gamma(M_n(\mathbb{F}_q),S) are

λk=∑m∈Dgn,m,k,0≤k≤n.\lambda_k=\sum_{m\in D}g_{n,m,k},\qquad0\leq k\leq n.

For each kk, the rank-kk characters contribute a(n,k,q)a(n,k,q) copies of λk\lambda_k. If different values of kk give the same eigenvalue, their multiplicities are added.

Proof. By Proposition 2.2 and Theorem 3.2,

λk=qAS,k−∣S∣q−1=∑m∈DqAm,k−a(n,m,q)q−1=∑m∈Dgn,m,k.\lambda_k=\frac{qA_{S,k}-|S|}{q-1}=\sum_{m\in D}\frac{qA_{m,k}-a(n,m,q)}{q-1}=\sum_{m\in D}g_{n,m,k}.

There is one character for each matrix X∈Mn(Fq)X\in M_n(\mathbb{F}_q), and there are a(n,k,q)a(n,k,q) matrices of rank kk. □\square

We have an immediate corollary.

Corollary 3.4. A gcd-graph over Mn(Fq)M_n(\mathbb{F}_q) is integral.

Remark 3.5. When D={n}\mathcal{D}=\{n\}, we recover the spectrum of the unitary Cayley graph over Mn(Fq)M_n(\mathbb{F}_q). Indeed, setting m=nm=n in the formula for gn,m,kg_{n,m,k}, the only term in the sum is i=ki=k. Thus

gn,n,k=(−1)kq(k2)+k(n−k)a(n−k,n−k,q)g_{n,n,k}=(-1)^kq^{\binom{k}{2}+k(n-k)}a(n-k,n-k,q)
=(−1)kqk(2n−k−1)/2γ(n−k,q),=(-1)^kq^{k(2n-k-1)/2}\gamma(n-k,q),

where γ(r,q)=∣GLr(Fq)∣\gamma(r,q)=|\mathrm{GL}_r(\mathbb{F}_q)| and γ(0,q)=1\gamma(0,q)=1. These are precisely the eigenvalues obtained in [2 Theorem 1.1]. We remark that the proof presented in [2] uses an entrywise parametrization of the additive characters, which agrees with ours after transposing the indexing matrix. Their calculation therefore gives the same character sum gn,n,kg_{n,n,k}.

An analogue of So’s conjecture

Two graphs are called isospectral if their spectra are the same. Isomorphic graphs are isospectral but the converse is not true in general. For a gcd-graph over Z/N\mathbb{Z}/N, So conjectured in [12] that two gcd-graphs Γ(Z/N,D1)\Gamma(\mathbb{Z}/N,D_1) and Γ(Z/N,D2)\Gamma(\mathbb{Z}/N,D_2) are isospectral if and only if D1=D2D_1=D_2. In this section, we will prove an analogue of So’s conjecture for gcd-graphs over a matrix ring. More precisely, we will show the following.

Theorem 4.1. Suppose that n≥1n\ge1. Let D1,D2D_1,D_2 be two subsets of {1,2,…,n}\{1,2,\ldots,n\} such that Γ(Mn(Fq),D1)\Gamma(M_n(\mathbb{F}_q),D_1) and Γ(Mn(Fq),D2)\Gamma(M_n(\mathbb{F}_q),D_2) are isospectral. Then D1=D2D_1=D_2.

In fact, we will show that having the same degree already guarantees that D1=D2D_1=D_2. In order to prove this theorem, we first introduce the following definition which is motivated by our study of sedentariness on Cayley graphs [5 Theorem 2.2]; namely, if a walk-regular graph is super then it is sedentary at every vertex.

Remark 4.2. After the completion of this paper, we learned that this concept has been studied in [6 Definition 1.5]. We note, however, that our convention reverses the order of the super sequences defined in their paper.

Definition 4.3. A sequence of positive real numbers a1,…,ara_1,\ldots,a_r is called super if

ai>∑j=i+1rajfor each 1≤i≤r.a_i>\sum_{j=i+1}^{r}a_j \qquad\text{for each }1\le i\le r.

A finite collection of positive real numbers is called super if its decreasing ordering is super. We say that a finite graph GG with spectrum {λ1(m1),λ2(m2),…,λr(mr)}\{\lambda_1^{(m_1)},\lambda_2^{(m_2)},\ldots,\lambda_r^{(m_r)}\} is super if the sequence {m1,m2,…,mr}\{m_1,m_2,\ldots,m_r\} forms a super collection.

For 0≤k≤n0\le k\le n, let VkV_k be the set of matrices in Mn(Fq)M_n(\mathbb{F}_q) that have rank kk. Recall that ∣V0∣=1|V_0|=1 and

∣Vk∣=∏j=0k−1(qn−qj)2qk−qj.|V_k|=\prod_{j=0}^{k-1}\frac{(q^n-q^j)^2}{q^k-q^j}.

We will show that these numbers form a super collection.

Proposition 4.4. Suppose that n≥2n\ge2. Then the collection {∣V0∣,…,∣Vn∣}\{|V_0|,\ldots,|V_n|\} is super. More precisely:

  1. If q≥3q \ge3, then

∣Vn∣,∣Vn−1∣,…,∣V0∣|V_n|, |V_{n-1}|,\ldots, |V_0|

is a super sequence.

  1. If q=2q = 2, then

∣Vn−1∣,∣Vn∣,∣Vn−2∣,…,∣V0∣|V_{n-1}|, |V_n|, |V_{n-2}|,\ldots, |V_0|

is a super sequence.

Proof. Write Nk=∣Vk∣N_k = |V_k|. By the rank-counting formula, we have

NkNk−1=qk−1(qn−k+1−1)2qk−1.\frac{N_k}{N_{k-1}} = \frac{q^{k-1}(q^{n-k+1}-1)^2}{q^k-1}.

Consequently, for 1≤k≤n−11 \le k \le n-1,

NkNk−1>(qn−k+1−1)2q≥(q2−1)2q≥92>2.\frac{N_k}{N_{k-1}} > \frac{(q^{n-k+1}-1)^2}{q} \ge\frac{(q^2-1)^2}{q} \ge\frac{9}{2} > 2.

It follows that

∑j=0k−1Nj<Nk∑ℓ=1k2−ℓ<Nk(1≤k≤n−1).(2)\sum_{j=0}^{k-1}N_j < N_k\sum_{\ell=1}^{k}2^{-\ell}<N_k \qquad(1\le k\le n-1). \tag*{(2)}

Let us focus on the first case, where q≥3q \ge3. Using the inequality

∏i=1n(1−xi)≥1−∑i=1nxi(0≤xi≤1),\prod_{i=1}^{n}(1-x_i)\ge1-\sum_{i=1}^{n}x_i \qquad(0\le x_i\le1),

we obtain

Nn∣Mn(Fq)∣=∏i=1n(1−q−i)≥1−∑i=1nq−i≥1−1−q−nq−1>1−1q−1≥12.\begin{aligned} \frac{N_n}{|M_n(\mathbb{F}_q)|}=\prod_{i=1}^{n}(1-q^{-i})\ge1-\sum_{i=1}^{n}q^{-i}\ge1-\frac{1-q^{-n}}{q-1} \\ &>1-\frac{1}{q-1}\ge\frac{1}{2}. \end{aligned}

Since ∑k=0nNk=∣Mn(Fq)∣\sum_{k=0}^{n}N_k=|M_n(\mathbb{F}_q)|, this gives Nn>∑k=0n−1NkN_n>\sum_{k=0}^{n-1}N_k. Together with (2), this proves the first assertion.

Let us prove the second assertion, where q=2q=2. For each integer r≥2r\ge2, define

br=#{A∈Mr(F2):rank⁡(A)=r−1}2r2.b_r=\frac{\#\{A\in M_r(\mathbb{F}_2):\operatorname{rank}(A)=r-1\}}{2^{r^2}}.

By the rank-counting formula,

br=(1−2−r)2∏i=2r−1(1−2−i).b_r=(1-2^{-r})^2\prod_{i=2}^{r-1}(1-2^{-i}).

Therefore,

br+1br=(1−2−(r+1))21−2−r=1+2−2r−21−2−r>1.\frac{b_{r+1}}{b_r}=\frac{(1-2^{-(r+1)})^2}{1-2^{-r}}=1+\frac{2^{-2r-2}}{1-2^{-r}}>1.

Thus the sequence (br)r≥2(b_r)_{r\ge2} is strictly increasing. Applying this to our fixed matrix size nn, we obtain

Nn−12n2=bn≥b2=(1−14)2=916>12.\frac{N_{n-1}}{2^{n^2}}=b_n\ge b_2=\left(1-\frac{1}{4}\right)^2=\frac{9}{16}>\frac{1}{2}.

Since ∑j=0nNj=2n2\sum_{j=0}^{n}N_j=2^{n^2}, it follows that

Nn−1>Nn+∑j=0n−2Nj.N_{n-1} > N_n + \sum_{j=0}^{n-2} N_j.

It remains to compare NnN_n with the lower-rank counts. The ratio formula gives

NnNn−2=9⋅22n−3(2n−1)(2n−1−1)>94>2.\frac{N_n}{N_{n-2}} = \frac{9 \cdot2^{2n-3}}{(2^n-1)(2^{n-1}-1)} > \frac{9}{4} > 2.

On the other hand, the inequalities Nk>2Nk−1N_k > 2N_{k-1} imply

∑j=0n−2Nj≤Nn−2∑ℓ=0n−22−ℓ<2Nn−2<Nn.\sum_{j=0}^{n-2} N_j \le N_{n-2}\sum_{\ell=0}^{n-2}2^{-\ell} < 2N_{n-2} < N_n.

Together with (4.1), these inequalities prove that Nn−1,Nn,Nn−2,…,N0N_{n-1},N_n,N_{n-2},\ldots,N_0 is super. □

Remark 4.5. When n=1n=1, we have ∣V0∣=1|V_0|=1 and ∣V1∣=q−1|V_1|=q-1. Thus the rank counts are also super when q>2q>2. The only exception is (n,q)=(1,2)(n,q)=(1,2), where both counts equal 1.

Corollary 4.6. Every gcd-graph over Mn(Fq)M_n(\mathbb{F}_q) is super, provided (n,q)≠(1,2)(n,q)\ne(1,2).

Proof. For each kk, the characters indexed by rank-kk matrices contribute ∣Vk∣|V_k| copies of the corresponding eigenvalue. If several ranks give the same eigenvalue, their contributions are added. Thus the multiplicities of the distinct eigenvalues are obtained by merging terms of the super rank-count sequence.

We claim that merging terms preserves the super property. Indeed, let a1,…,ara_1,\ldots,a_r be super, and partition {1,…,r}\{1,\ldots,r\} into nonempty blocks B1,…,BtB_1,\ldots,B_t, ordered so that

min⁡B1<⋯<min⁡Bt.\min B_1 < \cdots< \min B_t.

Set bj=∑i∈Bjaib_j=\sum_{i\in B_j}a_i. If s=min⁡Bjs=\min B_j, then

bj≥as>∑i>sai≥∑ℓ>jbℓ.b_j \ge a_s > \sum_{i>s}a_i \ge\sum_{\ell>j}b_\ell.

Therefore b1,…,btb_1,\ldots,b_t is super. Applying this observation to the rank counts proves the result. □

We are now ready to prove Theorem 4.1.

Proof of Theorem 4.1. Suppose that Γ(Mn(Fq),D1)\Gamma(M_n(\mathbb{F}_q),\mathcal{D}_1) and Γ(Mn(Fq),D2)\Gamma(M_n(\mathbb{F}_q),\mathcal{D}_2) are isospectral. Since each graph is regular, its largest adjacency eigenvalue is its degree. Therefore,

∑m∈D1∣Vm∣=∑m∈D2∣Vm∣.\sum_{m\in\mathcal{D}_1}|V_m|=\sum_{m\in\mathcal{D}_2}|V_m|.

Suppose first that (n,q)≠(1,2)(n,q)\ne(1,2). We have shown that the rank counts ∣V0∣,…,∣Vn∣|V_0|,\ldots,|V_n| form a super collection. We claim that this implies D1=D2\mathcal{D}_1=\mathcal{D}_2. Indeed, suppose to the contrary that D1≠D2\mathcal{D}_1\ne\mathcal{D}_2. Let us choose k∈D1△D2k\in\mathcal{D}_1\mathbin{\triangle}\mathcal{D}_2 such that ∣Vk∣|V_k| is largest among the rank counts indexed by D1△D2\mathcal{D}_1\mathbin{\triangle}\mathcal{D}_2. Interchanging D1\mathcal{D}_1 and D2\mathcal{D}_2 if necessary, we may assume that k∈D1∖D2k\in\mathcal{D}_1\setminus\mathcal{D}_2. Cancelling the common terms in the degree equality gives

∑m∈D1∖D2∣Vm∣=∑m∈D2∖D1∣Vm∣.\sum_{m\in\mathcal{D}_1\setminus\mathcal{D}_2}|V_m|=\sum_{m\in\mathcal{D}_2\setminus\mathcal{D}_1}|V_m|.

However, by the super property and the choice of kk,

∑m∈D1∖D2∣Vm∣≥∣Vk∣>∑m∈D2∖D1∣Vm∣,\sum_{m\in\mathcal{D}_1\setminus\mathcal{D}_2} |V_m| \ge|V_k| > \sum_{m\in\mathcal{D}_2\setminus\mathcal{D}_1} |V_m|,

a contradiction. Hence D1=D2D_1 = D_2.

Finally, when (n,q)=(1,2)(n,q) = (1,2), the only possible rank lists are ∅\varnothing and {1}\{1\}, which give graphs of degrees 0 and 1, respectively. Thus the conclusion holds in this case as well. □

Acknowledgements

The author used ChatGPT to assist with locating references, reviewing the exposition, and running computational checks. He thanks Dr. Nguyen Duy Tân for enlightening discussions around this topic. This project is supported by a Small Research Grant at Elmhurst University.

References

DEPARTMENT OF MATHEMATICS, ELMHURST UNIVERSITY, ILLINOIS, USA

Email address: [email protected]

References

  1. [1]Kumar Balasubramanian, Krishna Kaipa, and Himanshi Khurana, On the cardinality of matrices with prescribed rank and partial trace over a finite field, Linear Algebra and its Applications 704 (2025), 35–57.arxiv.org/abs/2407.14273
  2. [2]Bocong Chen and Jing Huang, On unitary Cayley graphs of matrix rings, Discrete Mathematics 345 (2022), no. 1, 112671.DOI
  3. [3]Shigeru Kanemitsu and Michel Waldschmidt, Matrices of finite abelian groups, finite Fourier transform and codes, Proc. 6th China-Japan Sem. Number Theory, World Sci. London-Singapore-New Jersey (2013), 90–106.
  4. [4]Walter Klotz and Torsten Sander, Some properties of unitary Cayley graphs, The Electronic Journal of Combinatorics 14 (2007), no. 1, R45, 12 pages.DOI
  5. [5]Karen Meagher, Hermie Monterde, and Tung T. Nguyen, Sedentariness in Cayley graphs, arXiv:2611.00567 (2026).arxiv.org/abs/2611.00567
  6. [6]Katja Mön ius and Wasin So, How many non-isospectral integral circulant graphs are there?, Australasian Journal of Combinatorics 86 (2023), no. 2, 320–335.
  7. [7]Ján Mináč, Tung T. Nguyen, and Nguyen Duy Tân, On the gcd-graphs over polynomial rings, Canadian Journal of Mathematics. In press (2026), 1–28.arxiv.org/abs/2409.01929
  8. [8]Tung T. Nguyen and Nguyen Duy Tân, Supercharacters of finite abelian groups and applications to spectra of U-unitary Cayley graphs, arXiv preprint arXiv:2508.10348 (2025).arxiv.org/abs/2508.10348
  9. [9]———, On gcd-graphs over finite commutative rings, Journal of Algebra and Its Applications. In press (2026).DOI
  10. [10]———, On U-unitary Cayley graphs over finite rings, arXiv:2603.21239 (2026).arxiv.org/abs/2603.21239
  11. [11]D. Nguyen and Tung T. Nguyen, On gcd-graphs over matrix rings arXiv:2606.00836 (2026), to appear in Involve.arxiv.org/abs/2606.00836
  12. [12]Wasin So, Integral circulant graphs, Discrete Mathematics 306 (2006), no. 1, 153–158.DOI

Paper details

vlnc:W_muvjjnz3
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…
Contents