betaFeedback

Reading v1View latest version

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.

Introduction

Gcd-graphs were first introduced by Klotz and Sander in [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 [5, 7]). Let us first recall the theory of Cayley graphs over RR. Let SS be a symmetric subset of (R,+)(R,+). 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}SR^{\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 [6, 7]). 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.

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 [8].

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

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

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}\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 [9], 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 D}V_m, where D⊆{1,…,n}D\subseteq\{1,\ldots,n\}.

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. □\square

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,k,A_{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\le r\le 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\le m,k\le 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\mathcal{D}}g_{n,m,k},\qquad0\le k\le n.

For each kk, the rank- kk characters contribute $a(n,k,q) copies of λk\lambda_k. If different values of $k 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\mathcal{D}}\frac{qA_{m,k}-a(n,m,q)}{q-1}=\sum_{m\in\mathcal{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. □

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)=∣GL⁡r(Fq)∣\gamma(r,q)=|\operatorname{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}.

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]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
  6. [6]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
  7. [7]———, On gcd-graphs over finite commutative rings, Journal of Algebra and Its Applications. In press (2026).DOI
  8. [8]———, On U-unitary Cayley graphs over finite rings, arXiv:2603.21239, (2026).arxiv.org/abs/2603.21239
  9. [9]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

Paper details

vlnc:W_muvjjnz3
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