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 (see [5, 7]). Let us first recall the theory of Cayley graphs over . Let be a symmetric subset of . The Cayley graph is defined as follows
The vertex set of is .
Two vertices are adjacent if .
We say that is a gcd-graph if is stable under left and right actions of the unit group ; i.e., . In this setting, the interplay between the additive and multiplicative structures of has played a fundamental role in understanding the geometry of their associated gcd-graphs. Furthermore, when the underlying ring is a finite commutative Frobenius ring, we showed in previous work that the spectra of gcd-graphs over 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 is a finite symmetric -algebra which could be non-commutative. When 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 . 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 be a finite-dimensional -algebra. We say that is a finite symmetric Frobenius -algebra if there exists a non-degenerate linear functional such that . Here, non-degenerate means that the kernel of does not contain any non-zero left ideal in . Equivalently, the map defined by where is an isomorphism of -vector spaces. Let
Here is the trace map from to . The pairing is also nondegenerate, showing that is also a finite symmetric -algebra.
Let be a Cayley graph over , where and is stable under . Let . The additive characters of are
By the theory of -circulant matrices (see [3]), we know that the spectrum of consists of the eigenvalues
with one eigenvalue for each , counting multiplicities. We will show below that, in some cases, the calculation of can be reduced to certain counting problems. To do so, we start with a simple lemma in character theory.
Lemma 2.1. Let . Then
Proof. The map
is an additive character of . If , it is the trivial character. If , it is nontrivial, so its sum over is zero. Removing the term gives the result. □
Let us introduce the counting numbers.
Then . We are now ready to express in terms of these counting numbers.
Proposition 2.2. For each , we have
Proof. Let us write for the scalar orbits. Since , every orbit has elements. Therefore
The condition is constant on each scalar orbit. By Lemma 2.1,
Applications to gcd-graphs over a matrix ring
In this section, we focus on the case . In this case, is a symmetric Frobenius ring with respect to the matrix trace map. Let
In [9], using the theory of row and column operations, we show that is a gcd-graph if and only if , where .
For , write
Lemma 3.1. If , then .
Proof. We can write for some . Thus
Here , and is a rank-preserving bijection of .
For , let
By Lemma 3.1, we only need to calculate
If
then
Consequently,
where
Here and are fixed. In particular, .
It turns out that there is a neat formula for recently discovered in [1]. Let us briefly recall this formula. First, let us write
with . This is the number of rank- matrices in . In particular, .
The case follows directly from .
Theorem 3.3. The eigenvalues of the gcd-graph are
For each , the rank- characters contribute $a(n,k,q) copies of . If different values of $k give the same eigenvalue, their multiplicities are added.
Proof. By Proposition 2.2 and Theorem 3.2,
There is one character for each matrix , and there are matrices of rank . □
We have an immediate corollary.
Corollary 3.4. A gcd-graph over is integral.
Remark 3.5. When , we recover the spectrum of the unitary Cayley graph over . Indeed, setting in the formula for , the only term in the sum is . Thus
where and . 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 .
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]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]Bocong Chen and Jing Huang, On unitary Cayley graphs of matrix rings, Discrete Mathematics 345 (2022), no. 1, 112671.DOI
- [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]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]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]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]———, On gcd-graphs over finite commutative rings, Journal of Algebra and Its Applications. In press (2026).DOI
- [8]———, On U-unitary Cayley graphs over finite rings, arXiv:2603.21239, (2026).arxiv.org/abs/2603.21239
- [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