On gcd-graphs over matrix rings
Dung Nguyen, Tung T. Nguyen · 2026
Read On gcd-graphs over matrix rings by Dung Nguyen, Tung T. Nguyen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00836.txt.
Introduction
Nguyen and Nguyen study graphs built from matrix rings in this 2026 maths paper. A gcd-graph links numbers or ring elements when their greatest common divisor meets a set rule. Such graphs over finite rings are a rich meeting point. Number theory, algebra, combinatorics, and graph theory all feed into them.
Here the ground set is a matrix ring whose entries come from a finite field. The pair show that these graphs carry several notable graph-theoretic traits. The proofs also force new facts about the structure of matrix rings themselves. The authors note those side results may serve algebraists on their own. The paper suits readers who like their graph theory with strong algebraic bones. It adds matrix rings to a map long drawn for simpler rings. Each new ground ring tends to reveal fresh links between counting, symmetry, and shape.
Catalog record
| CREATOR | Dung Nguyen, Tung T. Nguyen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00836
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On gcd-graphs over matrix rings Dung Nguyen, Tung T. Nguyen Abstract . Graphs defined over finite rings are well studied in the literature. The study of these graphs benefits from rich connections between several areas of mathematics, including number theory, algebra, combinatorics, and graph theory, and these connections often lead to interesting interactions between algebraic and combinatorial structures. In this article, we investigate gcd-graphs defined over matrix rings with coefficients in finite fields. We show that these graphs exhibit several interesting graph-theoretic properties. Along the way, we also prove some results on the structure of matrix rings, which may be of independent interest. 2020 Mathematics Subject Classification Primary 05C50, 15B33, 16S50 1. Introduction Graphs defined over finite rings are well studied in the literature, tracing their origins to the foundational work of Klotz and Sander on gcd-graphs (see, for example, [ 1 , 2 , 6 , 12 ] ). Unlike graphs defined over abstract abelian groups, graphs defined over rings benefit from both the additive and multiplicative structures of the underlying ring. Moreover, the interplay between these two structures often gives rise to rich and interesting properties of the associated graphs. To set the stage for our subsequent analysis, we recall the definition of these graphs. Definition 1.1 . Let R be a finite ring and S\subset R\setminus\{0\} be a symmetric subset (meaning that S=-S ). The Cayley graph \Gamma(R,S) is defined as follows: (1) The vertex set is the set of elements in R . (2) Two vertices x,y\in R are adjacent if x-y\in S . We refer to S as the generating set for \Gamma(R,S) . In practice, S often has arithmetic origins. One of the earliest and most extensively studied types of Cayley graphs over rings is the class of gcd-graphs, first introduced in [ 6 ] . We begin by recalling this fundamental concept. Let n be a positive integer and D a subset of proper divisors of n . The gcd-graph G_{n}(D) is defined as follows: (1) the vertices of G_{n}(D) are elements of the finite ring \mathbb{Z}/n\mathbb{Z} , and (2) two vertices a,b are adjacent if \gcd(a-b,n)\in D . In this setting, the generating set is precisely the collection of elements of the form du , where d\in D and u\in(\mathbb{Z}/n\mathbb{Z})^{\times} . The concept of gcd-graphs can be naturally generalized to any finite ring in which we employ an equivalent characterization: a graph \Gamma(R,S) is a gcd-graph if and only if S is stable under the left and right actions of R^{\times} . That is, S satisfies the condition R^{\times}SR^{\times}=S , where R^{\times} denotes the group of units in R (see [ 8 , 10 , 12 , 13 , 14 ] ). In this paper, we focus on the case where the underlying ring R is a matrix ring defined over a finite field. In this setting, we can utilize tools from linear algebra to address fundamental questions concerning the structure of the associated gcd-graphs. We summarize here some of our main results; for precise statements and detailed proofs, we refer the reader to the main body of the text. Let R=M_{n}(\mathbb{F}_{q}) where \mathbb{F}_{q} is a finite field with q elements. Let S be a symmetric subset of M_{n}(\mathbb{F}_{q}) . Throughout the rest of the pape, we will assume that n>1 because in the case n=1 , a gcd-graph is either a complete graph or an empty graph (additionally, certain rank subadditivity properties and non-commutative matrix decompositions we seek to investigate simply do not exist in a 1-dimensional space). For each 1\leq k\leq n , let V_{k} be the subset of R consisting of all matrices of rank k. (1) \Gamma(R,S) is a gcd-graph if and only if there exists a subset I\subset\{1,2,\ldots,n\} such that S=\bigsqcup_{k\in I}V_{k}. We will write \Gamma(M_{n}(\mathbb{F}_{q}),[k_{1},k_{2},\ldots,k_{r}]) for \Gamma(M_{n}(\mathbb{F}_{q}),S) where k_{1}<k_{2}<\cdots<k_{r} are elements of I. To avoid the trivial cases of empty graphs or complete graphs, we will assume that 1\leq r\leq n-1 . (2) The gcd-graph \Gamma(M_{n}(\mathbb{F}_{q}),[k_{1},k_{2},\ldots,k_{r}]) is connected with diameter equal to \max\left\{2,\left\lceil\frac{n}{k_{r}}\right\rceil\right\}. (3) The gcd-graph \Gamma(M_{n}(\mathbb{F}_{q}),[k_{1},k_{2},\ldots,k_{r}]) is not bipartite. (4) The gcd-graph \Gamma(M_{n}(\mathbb{F}_{q}),S) is Hamiltonian. (5) The clique number of \Gamma(M_{n}(\mathbb{F}_{q}),[1]) is q^{n} . (6) The sum of all matrices in M_{n}(\mathbb{F}_{q}) with fixed rank k is the zero matrix. Figure 1. An example of gcd-graph \Gamma(M_{2}(\mathbb{F}_{2}),[2]) Outline In section 2 , we provide some background on graph theory that we will need later in the text. In section 3.1 , we give necessary and sufficient conditions for a Cayley graph over M_{n}(\mathbb{F}_{q}) to be a gcd-graph. These conditions are explicit and can be easily verified. In section 3.3 , we describe the connectivity of gcd-graphs. In particular, we compute the distance between any two vertices. In the course of proving our results, we obtain some statements on representing a matrix as a sum of two matrices with fixed ranks—a topic that may be of independent interest. Other fundamental properties, such as bipartiteness, Hamiltonicity, and clique numbers, are discussed in section 3.4 and section 3.5 . Finally, in section 3.6 , we show that the sum of all matrices with fixed rank is 0 , which leads to an interesting corollary on the walk structure of a gcd-graph. Future work The study of gcd-graphs over matrix rings presents several additional questions that appear to be considerably more subtle. For example, while we determine the clique number of the graph \Gamma(M_{n}(\mathbb{F}_{q}),[1]) , the corresponding problem for gcd-graphs of the form \Gamma(M_{n}(\mathbb{F}_{q}),[k_{1},k_{2},\ldots,k_{r}]) remains open. Other natural directions include the study of chromatic numbers and explicit spectral descriptions (for gcd-graphs over finite commutative rings, these are rather well-studied, see [ 1 , 3 , 6 , 12 ] ). We hope that the results in this paper provide a useful framework for investigating these questions. Code The code that we wrote to test our calculations and conduct numerical experiments on gcd-graphs can be found at [ 11 ] . 2. Background on graph theory In this section, we recall some background in graph theory that we will need for the later part of this article. 2.1. Connectedness of Cayley graphs A Cayley graph \Gamma(R,S) is connected if and only if every element of R can be written as a sum of elements of S . We may think of the generating set S as providing the “bridges” that connect vertices in R . To illustrate this, suppose we want to find a walk between vertices a and b in R . We can construct such a walk by moving through intermediate vertices: a\to x_{1}\to x_{2}\to\cdots\to x_{n-1}\to b. By the definition of a Cayley graph, each edge corresponds to an element of S , so we have \displaystyle x_{1}-a \displaystyle=s_{1}\in S, \displaystyle x_{2}-x_{1} \displaystyle=s_{2}\in S, \displaystyle b-x_{n-1} \displaystyle=s_{n}\in S. Summing these equations telescopically, we obtain b-a=s_{1}+s_{2}+\cdots+s_{n}, where each s_{i}\in S . This argument also shows that the distance between a and b in the Cayley graph is the smallest integer n for which b-a can be expressed in this form. 2.2. Diameter and clique number of a graph The diameter of a graph is the maximum length of the shortest-path between any two vertices, namely \text{diam}(G)=\max_{u,v\in V(G)}d(u,v). The clique number of a graph, denoted \omega(G) , is the number