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 (see [7, 9]). Let us first recall the theory of Cayley graphs over . Let be a symmetric subset of such that . 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 [8, 9]). 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. 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 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 [11], using the theory of row and column operations, we show that is a gcd-graph if and only if , where . In this case, we will write for .
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, .
Theorem 3.2 ([1 Theorem 1.1]). For , we have
where
Here is the Gaussian binomial coefficient.
The case follows directly from .
Theorem 3.3. The eigenvalues of the gcd-graph are
For each , the rank- characters contribute copies of . If different values of 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 .
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 , So conjectured in [12] that two gcd-graphs and are isospectral if and only if . 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 . Let be two subsets of such that and are isospectral. Then .
In fact, we will show that having the same degree already guarantees that . 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 is called super if
A finite collection of positive real numbers is called super if its decreasing ordering is super. We say that a finite graph with spectrum is super if the sequence forms a super collection.
For , let be the set of matrices in that have rank . Recall that and
We will show that these numbers form a super collection.
Proposition 4.4. Suppose that . Then the collection is super. More precisely:
If , then
is a super sequence.
If , then
is a super sequence.
Proof. Write . By the rank-counting formula, we have
Consequently, for ,
It follows that
Let us focus on the first case, where . Using the inequality
we obtain
Since , this gives . Together with (2), this proves the first assertion.
Let us prove the second assertion, where . For each integer , define
By the rank-counting formula,
Therefore,
Thus the sequence is strictly increasing. Applying this to our fixed matrix size , we obtain
Since , it follows that
It remains to compare with the lower-rank counts. The ratio formula gives
On the other hand, the inequalities imply
Together with (4.1), these inequalities prove that is super. □
Remark 4.5. When , we have and . Thus the rank counts are also super when . The only exception is , where both counts equal 1.
Corollary 4.6. Every gcd-graph over is super, provided .
Proof. For each , the characters indexed by rank- matrices contribute 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 be super, and partition into nonempty blocks , ordered so that
Set . If , then
Therefore 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 and are isospectral. Since each graph is regular, its largest adjacency eigenvalue is its degree. Therefore,
Suppose first that . We have shown that the rank counts form a super collection. We claim that this implies . Indeed, suppose to the contrary that . Let us choose such that is largest among the rank counts indexed by . Interchanging and if necessary, we may assume that . Cancelling the common terms in the degree equality gives
However, by the super property and the choice of ,
a contradiction. Hence .
Finally, when , the only possible rank lists are and , 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]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]Karen Meagher, Hermie Monterde, and Tung T. Nguyen, Sedentariness in Cayley graphs, arXiv:2611.00567 (2026).arxiv.org/abs/2611.00567
- [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]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]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]———, On gcd-graphs over finite commutative rings, Journal of Algebra and Its Applications. In press (2026).DOI
- [10]———, On U-unitary Cayley graphs over finite rings, arXiv:2603.21239 (2026).arxiv.org/abs/2603.21239
- [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]Wasin So, Integral circulant graphs, Discrete Mathematics 306 (2006), no. 1, 153–158.DOI