Graphs from matrices - a survey

Abstract

Let R be a commutative ring with identity. For a positive integer $n\ge 2,$ let $M_n(R)$ be the set of all n × n matrices over R and $M_n{(R)}^{*}$ be the set of all non-zero matrices of $M_n(R).$ The zero-divisor graph of $M_n(R)$ is a simple directed graph with vertex set the non-zero zero-divisors in $M_n(R)$ and two distinct matrices A and B are adjacent if their product is zero. Given a matrix $A\in M_n(R),$ Tr(A) is the trace of the matrix A. The trace graph of the matrix ring $M_n(R),$ denoted by ${\Gamma }_t(M_n(R)),$ is the simple undirected graph with vertex set $\{A\in M_n{(R)}^{*}:\text{there exists }B\in M_n{(R)}^{*}$ $\text{such that Tr}(\mathit{\text{AB}})=0\}$ and two distinct vertices A and B are adjacent if and only if Tr $(\mathit{\text{AB}})=0.$ For an ideal I of R, the notion of the ideal based trace graph, denoted by ${\Gamma }_{I^t}(M_n(R)),$ is a simple undirected graph with vertex set $M_n(R)\setminus M_n(I)$ and two distinct vertices A and B are adjacent if and only if Tr $(\mathit{\text{AB}})\in I.$ In this survey, we present several results concerning the zero-divisor graph, trace graph and the ideal based trace graph of matrices over R.

Keywords:

• Commutative rings
• graphs from matrices
• matrix rings
• zero-divisor graph
• trace graph

2020 Mathematics Subject Classification:

• 16S50
• 05C25
• 05C45
• 05C69

1 Introduction

The study of algebraic structures using the properties of graphs has become an exciting research topic in the last twenty years. These areas have applications in other areas of mathematics and are increasingly being used in computer networks. Algebraic tools can be used to give surprising proofs of graph theoretic facts, and there are many interesting algebraic objects associated with graphs. The first is the study of algebraic objects associated with graphs. The second is the use of tools from algebra to derive properties of graphs. In fact, the study aims at exposing the relationship between algebra and graph theory and advancing applications of one with the other.

Research on graphs associated with rings was started in 1988 by Bech [10] after introducing the topic of coloring of rings. In 1999, Anderson and Livingston [8] modified and studied the same as the zero-divisor graph of a commutative ring whose vertices are the non-zero zero divisors of the commutative ring and two distinct vertices are adjacent provided their multiplication in the underlying commutative ring is zero. Redmond [21] has extended this concept to any arbitrary ring. In a manner analogous to the commutative case, research on graphs from non-commutative rings are also taken under consideration. The connection between matrices and graph theory is growing very enormously and is recently studied by many researchers.

In this survey article, we shall focus on graph construction from the ring of matrices over commutative rings. This graph is one of the classical graph construction from the non-commutative ring of matrices over commutative rings and graph theory. The study of graphs from the ring of matrices is especially important. The Artin-Wedderburn theorem is a classification theorem for semisimple rings and semisimple algebras and the same states that an Artinian semisimple ring is isomorphic to a product of finitely many matrix rings over division rings, both of which are uniquely determined up to permutation of indices. In particular, any simple left or right Artinian ring is isomorphic to a matrix ring over a division ring. Hence it is vital to study about graphs from matrices. In this regard, several authors [3, 5, 11, 16, 17, 26] have extensively studied on graphs from matrices. A recent book [7] gives the entire literature and developments on the research from graphs from rings.

2 Preliminaries

Let us recall certain basic definitions related to graphs from rings. Throughout this paper, R denotes a ring with identity 1. An element $x\in R$ is called a unit if there exists a $y\in R$ with $\mathit{\text{xy}}=\mathit{\text{yx}}=1.$ The collection of all units in R is denoted by U(R). It is easy to check that U(R) is a group under multiplication and is called the multiplicative group of units of R. An element a in a commutative ring R is called a zero-divisor if there is a $0\ne b\in R$ such that ab = 0. The set of all zero-divisors of R is denoted by Z(R), i.e., $Z(R)=\{a\in R|\mathit{\text{ab}}=0 \text{for some} \mathrm{b}\ne 0\}$ and $Z{(R)}^{*}=Z(R)\setminus \left\{0\right\}.$A commutative ring with identity is said to be an integral domain if it has no nonzero zero-divisors.

For a commutative ring R, the zero-divisor graph $\Gamma (R)$ [8] of R is the undirected simple graph with vertex set $Z^{*}(R)$ and two distinct vertices x and y are adjacent if xy = 0. The zero-divisor graph of a non-commutative ring [21] has been introduced and studied by Redmond in 2002. An element x in a non-commutative ring R is a zero divisor if either xy = 0 or yx = 0 for some non-zero $y\in R.$ The concept of zero-divisor graph for a non-commutative ring was generalized in two different ways [21]. For any non-commutative ring R, one can associate a directed graph whose vertices are the non-zero zero-divisors of R, and there is a directed edge from x to y if and only if $\mathit{\text{xy}}=0.$ The second definition of the zero-divisor graph of a non-commutative ring introduced in [21] produces an undirected graph. For an arbitrary ring R, the zero-divisor graph $\Gamma (R)$ [21] of R is an undirected graph whose vertices are the non-zero zero-divisors of R and two distinct vertices x and y are adjacent if either xy = 0 or $\mathit{\text{yx}}=0.$

Consequently, research on graphs from non-commutative rings has moved in several directions. Akbari and Mohammadian [2] studied the problem of determining when the zero-divisor graphs of rings are isomorphic, given that the zero-divisor graphs of their matrix rings are isomorphic. In [3], authors investigated some properties of zero-divisor graphs of matrix rings. Bozic and Petrovic [11] investigated the relationship between graphs of commutative and noncommutative rings and proved several results on zero-divisor graphs of matrix rings. In particular, they investigated the possible diameters of zero-divisor graphs of matrix ring over a commutative ring R in terms of the diameter of $\Gamma (R).$ Li and Ralph P. Tucci [17] studied the zero-divisor graphs of upper triangular matrix rings over commutative rings with identity. In [5], Ashrafi and Tadayyonfar completely determined the structure of the zero-divisor graph of 2 × 2 matrices over a field. Motivated by these studies on graphs from ring of matrices, Almahdi, Louartiti and Tamekkante [6] introduced the concept of the trace graph of matrices over a finite commutative ring. For a commutative ring R, the set of all n × n matrices with entries from R is a ring and it is denoted by $M_n(R).$ The trace graph of the matrix ring $M_n(R),$ denoted by ${\Gamma }_t(M_n(R)),$ is the simple undirected graph with vertex set $\{A\in M_n{(R)}^{*}:\text{there exists} B\in M_n{(R)}^{*}$ $\text{such that Tr}(\mathit{\text{AB}})=0\}$ and two distinct vertices A and B are adjacent if and only if Tr $(\mathit{\text{AB}})=0.$

Further, Redmond [21] generalized the notion of the zero-divisor graph of a commutative ring R to that of an ideal based graph. Let R be a commutative ring and I be a proper ideal of R. The ideal based zero-divisor graph of R, denoted by ${\Gamma }_I(R)$ [22], is an undirected graph whose vertex set is $R\setminus I$ and two distinct vertices x and y are adjacent if $\mathit{\text{xy}}\in I.$ Redmond [22] explored the relationship between ${\Gamma }_I(R)$ and $\Gamma (R/I).$ This work includes the complete determination of the planar ideal based zero-divisor graphs. Maimani et al. [18] showed that for finite ideals I and J of R and S, respectively, for which $I=\sqrt{I}$ and $J=\sqrt{J},$ if ${\Gamma }_I(R)\cong {\Gamma }_J(R)$, then $\Gamma (R/I)\cong \Gamma (S/J).$ Tamizh Chelvam and Nithya [25] classified all finite quotient rings and ideals of for which the crosscap of ${\Gamma }_I(R)$ is at most one.

This survey paper contains six sections. In the Section 3, we elaborate results concerning zero-divisor graph of matrices. In the Section 4, we present basic properties like degree, connectivity, Eulerian, Hamiltonian and irregularity index of trace graph of matrices. In Section 5, we present results concerning the trace graph of matrices over field. In Section 6, we present results concerning the ideal based trace graph of matrices.

3 Zero-divisor graph of matrices

Let R be a noncommutative ring and $Z(R),Z_L(R),Z_R(R),Z_T(R)$ denote the set of zero-divisors, left zero-divisors, right zero-divisors, and two-sided zero-divisors of R, respectively, i.e., $Z(R)=\{x\in R|\mathit{\text{xy}}=0 \text{or} \mathit{\text{yx}}=0 \text{for} \text{some} y\in R^{*}\},Z_L(R)=\{x\in R|\mathit{\text{xa}}=0 \text{for} \text{some} a\in R^{*}\}$, $Z_R(R)=\{x\in R|\mathit{\text{bx}}=0 \text{for} \text{some} b\in R^{*}\}$, and $Z_T(R)=\{x\in R|\mathit{\text{xa}}=\mathit{\text{bx}}=0 \text{for} \text{some} a,b\in R^{*}\}$. Note that when R is commutative, all of these sets are equal. The concept of directed zero-divisor graphs of noncommutative rings was introduced and studied by Redmond [21]. Subsequently, several authors studied the properties of directed zero-divisor graphs of noncommutative rings [11, 26, 27]. Hereafter, in this section, by a ring R, we mean a noncommutative ring. For a ring R, the zero-divisor graph of R is the directed graph $\overrightarrow{\Gamma }(R)$ with vertices $Z{(R)}^{*}$, where $x\to y$ is an edge between two distinct vertices x and y if and only if xy = 0. It is trivial that if R is a commutative ring, then $y\to x$ is an edge whenever $x\to y$ is an edge. Therefore, if we consider the underlying undirected graph of $\overrightarrow{\Gamma }(R)$, this definition agrees with the usual definition of the zero-divisor of a commutative ring. Let us see some examples of directed zero-divisor graphs of noncommutative rings.

Example 3.1.

[21] Consider the ring $R=\{(\begin{array}{cc}a& b\\ 0& 0\end{array})|a\in {\mathbb{Z}}_4,$ $b\in 2{\mathbb{Z}}_4\}$. Then $Z{(R)}^{*}=\{x_1,x_2,\dots ,x_7\}$, where x₁=$(\begin{array}{cc}0& 2\\ 0& 0\end{array})$, x₂=$(\begin{array}{cc}1& 0\\ 0& 0\end{array})$, x₃=$(\begin{array}{cc}1& 2\\ 0& 0\end{array})$, x₄=$(\begin{array}{cc}2& 0\\ 0& 0\end{array})$, x₅=$(\begin{array}{cc}2& 2\\ 0& 0\end{array})$, x₆=$(\begin{array}{cc}3& 0\\ 0& 0\end{array})$, x₇=$(\begin{array}{cc}3& 2\\ 0& 0\end{array})$.

Fig. 1 Directed zero-divisor graph.

The corresponding directed zero-divisor graph $\overrightarrow{\Gamma }(R)$ is given below:

Example 3.2.

[21, Example 2.2] Let K be a field, $V={\oplus }_{i=1}^{\infty }K$, and $R={\mathit{\text{Hom}}}_K(V,V)$. Under point-wise addition and multiplication taken to be composition of functions, R is an infinite noncommutative ring with identity. Let ${\pi }_1:V\to V$ be defined by $(a_1,a_2,\dots )\mapsto (a_1,0,0,\dots )$ and $f:V\to V$ be defined by $(a_1,a_2,\dots )\mapsto (0,a_1,a_2,\dots ).$ Then ${\pi }_1,f\in R$ and ${\pi }_{1}f=0,$ while $f{\pi }_1\ne 0.$ Clearly f is not a left zero-divisor in R (if $g\in R$ with $\mathit{\text{fg}}(a_1,a_2,\dots )=(0,0,\dots )$ for every $(a_1,a_2,\dots ,)\in V,$ then $g(a_1,a_2,\dots )=(0,0,\dots )$ for every $(a_1,a_2,\dots )\in V)$. Hence, $\overrightarrow{\Gamma }(R)$ is nonempty and $\overrightarrow{\Gamma }(R)$ is not connected since there is no path leading from the vertex f to any other vertex of $\overrightarrow{\Gamma }(R).$

Note that the structure of $\overrightarrow{\Gamma }(R)$ in Example 3.2 is still rather rich. By defining π_j to be $(a_1,a_2,\dots )\mapsto (0,\dots ,0,a_j,0,\dots ),$ the vertices ${\left\{{\pi }_j\right\}}_{j=1}^{\infty }$ induce a complete subgraph of $\overrightarrow{\Gamma }(R).$

The following theorem gives a necessary and sufficient condition for $\overrightarrow{\Gamma }(R)$ to be connected.

Theorem 3.3

([21, Theorem 2.3]). Let R be a ring. Then $\overrightarrow{\Gamma }(R)$ is connected if and only if $Z_L(R)=Z_R(R)$. Further, if $\overrightarrow{\Gamma }(R)$ is connected, then $\mathit{\text{diam}}(\overrightarrow{\Gamma }(R))\le 3$.

Corollary 3.4

([21, Corollary 2.4]). Let R be a left and right Artinian ring with a two-sided identity. Then $Z_L(R)=Z_R(R)$; so $\overrightarrow{\Gamma }(R)$ is connected.

Note that when R is a commutative ring, then $\overrightarrow{\Gamma }(R)=\Gamma (R)$. Hence we recover the following result on zero-divisor graphs as a corollary.

Corollary 3.5.

Let R be a commutative ring with $Z{(R)}^{*}\ne \varnothing$. Then $\Gamma (R)$ is connected, $\mathit{\text{diam}}(\Gamma (R))\le 3$, and gr $(\Gamma (R))\le 4$.

Note that as in the case of commutative rings, R is finite if and only if $\overrightarrow{\Gamma }(R)$ is finite [14, Theorem 1]. Further, when R is finite, $\overrightarrow{\Gamma }(R)$ is connected and diam($\overrightarrow{\Gamma }(R)$) $\le 3$. We may have $Z_R(R)=Z_L(R)$ for an infinite noncommutative ring R as well. Let $\mathbb{H}$ be the ring of quaternions over the field of real numbers. Then $\mathbb{H}$ is an infinite noncommutative division ring. Let $R=\mathbb{H}\times \mathbb{H}.$ The only nonzero zero-divisors of R are of the form $(0,t)$ or $(t,0)$ for $0\ne t\in \mathbb{H}.$ Note that all zero-divisors of R are two-sided (i.e., $Z_L(R)=Z_R(R)).$

Theorem 3.6

([21, Theorem 2.7]). Let R be a finite ring with no nonzero nilpotent elements and $\overrightarrow{\Gamma }(R)\ne \varnothing$. Then $\overrightarrow{\Gamma }(R)$ is not a tournament.

Note that for a ring R, $M_n(R)$ denotes the ring of all n × n matrices over R. Unlike the zero-divisor graphs of commutative rings, directed zero-divisor graphs of noncommutative rings need not be connected. We proceed to see whether directed zero-divisor graphs of matrices over commutative rings are connected.

Theorem 3.7

([11, Theorem 3.1]). Let R be a commutative ring. Then $\overrightarrow{\Gamma }(M_n(R))$ is connected and $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))\le 3$.

Our next aim is to mention a relationship between the diameters of $\Gamma (R)$ and $\overrightarrow{\Gamma }(M_n(R))$.

Proposition 3.8

([11, Proposition 3.1]). Let R be a commutative ring with $Z{(R)}^{*}\ne \varnothing$. Then $\mathit{\text{diam}}(\Gamma (R))\le \mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))$.

Let T(R) be the total quotient ring of a commutative ring R. Anderson et al. [9] proved that $\Gamma (R)$ and $\Gamma (T(R))$ were isomorphic as graphs, and as a consequence, it followed that these two graphs had the same diameter and girth. It is now observed that the same claim holds for $\overrightarrow{\Gamma }(M_n(R))$ and $\overrightarrow{\Gamma }(M_n(T(R)))$ as well.

Theorem 3.9

([11, Theorem 3.2]). Let R be a commutative ring with total quotient ring T(R). Then $\overrightarrow{\Gamma }(M_n(R))\cong \overrightarrow{\Gamma }(M_n(T(R))),$ implying diam $(\overrightarrow{\Gamma }(M_n(R)))=$ diam $(\overrightarrow{\Gamma }(M_n(T(R))))$.

For a noncommutative ring R, the undirected zero-divisor graph $\Gamma (R)$ is the undirected graph with vertices $Z{(R)}^{*}$, and for distinct vertices a and b, there is an edge connecting them if and only if ab = 0 or ba = 0. The following results concern the girth of the undirected zero-divisor graph $\Gamma (R)$ of a noncommutative ring R.

Proposition 3.10

([11, Proposition 3.2]). Let R be a commutative ring. Then gr $(\Gamma (M_n(R)))=3$.

Theorem 3.11

([21, Theorems 3.2 and 3.3]). Let R be a noncommutative ring with $Z{(R)}^{*}\ne \varnothing$. Then $\mathit{\text{diam}}(\Gamma (R))\le 3$, and gr $(\Gamma (R))\le 4,$ if $\Gamma (R)$ contains a cycle.

Next, we present a characterization of $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))$ in terms of diam $(\Gamma (R))$.

Lemma 3.12

([11, Lemma 4.1]). Let R be a commutative ring and $A\in Z{(M_n(R))}^{*}$. If all elements of R are either invertible or zero-divisors, then there exists an invertible $P\in M_n(R)$ such that the first row of PA (alternatively, the last column of AP) consists entirely of zero-divisors.

Lemma 3.13

([11, Lemma 4.2]). Let R be a commutative ring. If every finite set of zero-divisors of R has a nonzero annihilator, then diam $(\overrightarrow{\Gamma }(M_n(R)))=2.$

Proposition 3.14

([11, Proposition 4.1]). Let R be an integral domain. Then $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))=2$.

Now we state a characterization for the diameter of $\overrightarrow{\Gamma }(M_n(R))$ for rings with complete directed zero-divisor graphs.

Theorem 3.15

([11, Theorem 4.1]). Let R be a commutative ring such that $R\ncong {\mathbb{Z}}_2\times {\mathbb{Z}}_2$, and let $\mathit{\text{diam}}(\Gamma (R))=1$. Then $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))=2$.

Theorem 3.16

([11, Theorem 4.2]). Let R be a commutative ring such that $T(R)=K_1\times K_2$, where both K_i are fields. Then $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))=3$.

In the theorem below, when Z(R) is an ideal in R, we determine the diameter of $\overrightarrow{\Gamma }(M_n(R))$ for a commutative Noetherian ring R.

Theorem 3.17

([11, Theorem 4.3]). Let R be a commutative Noetherian ring with $\mathit{\text{diam}}(\Gamma (R))=2$. If Z(R) is a (prime) ideal of R, then $\mathit{\text{diam}}(\overrightarrow{\Gamma }(M_n(R)))=2$.

Fig. 2 The trace graph ${\Gamma }_t(M_2({\mathbb{Z}}_2))$.

4 Trace graph of matrices

First, we present some results on the trace graph of matrices over commutative rings proved by Almahdi et al. [6]. Having introduced the trace graph of matrices, Almahdi et al. [6] studied about the trace graph of matrices over a commutative ring. More specifically, they have studied about the degree of vertices and irregularity index of the trace graph. The following example illustrates the definition.

Example 4.1.

The trace graph ${\Gamma }_t(M_2({\mathbb{Z}}_2))$ is given in Figure 2. Note that ${\Gamma }_t(M_2({\mathbb{Z}}_2))$ is bi-regular. The matrices in ${\Gamma }_t(M_2({\mathbb{Z}}_2))$ are $$\begin{array}{c}{A}_1=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),A_2=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right),A_3=\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right),A_4=\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right),\\ A_5=\left(\begin{array}{cc}1& 1\\ 0& 0\end{array}\right),A_6=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right),A_7=\left(\begin{array}{cc}0& 0\\ 1& 1\end{array}\right),A_8=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right),\\ A_9=\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right),A_{10}=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right),A_{11}=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),A_{12}=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\\ A_{13}=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right),A_{14}=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right),A_{15}=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right).\end{array}$$

Remark 4.2

([6, Remark 2.1] ).

1. When $n=1,$ the trace graph ${\Gamma }_t(M_n(R))$ is same as the zero-divisor graph ${\Gamma }_t(M_1(R))=\Gamma (R).$

2. Except in the case of $n=1,$ for every matrix $A\in M_n{(R)}^{*}$ there exists a matrix $B\in M_n{(R)}^{*},B\ne A$ such that Tr $(\mathit{\text{AB}})=0.$ Hence, whenever the case $n\ge 2$ is assumed, the vertex set is $M_n{(R)}^{*}.$ Hence throughout this paper on trace graph of matrices, we consider $n\ge 2.$

3. As observed above, if $n\ge 2,$ the graph ${\Gamma }_t(M_n(R))$ contains no isolated vertices. In this regard, it is to be noted that ${\Gamma }_t(M_1(R))=\Gamma (R)$ may have an isolated vertex. For example, the zero-divisor graph of ${\mathbb{Z}}_4$ contains an isolated vertex.

4. For $A,B\in M_n(R),$ we have Tr $(\mathit{\text{AB}})=$ Tr(BA) and hence the graph ${\Gamma }_t(M_n(R))$ is undirected.

Now, let us present some few fundamental properties about the trace graph as obtained by Almahdi et al. [6].

Theorem 4.3

([6, Theorem 2.2]). Let R be a commutative ring with identity $1\ne 0$ and $n\ge 2$ be an integer. Then ${\Gamma }_t(M_n(R))$ is connected with diam $({\Gamma }_t(M_n(R)))=2$ and gr $({\Gamma }_t(M_n(R)))=3.$

For $A=(a_{\mathit{\text{ij}}})\in M_n(R),$ $I(A)=\sum _{1\le i,j\le n}R{a}_{\mathit{\text{ij}}},$ the ideal of R generated by all entries of A.

Proposition 4.4

([6, Proposition 2.3]). Let R be a finite commutative ring with identity $1\ne 0$ and $n\ge 2$ be an integer.

1. For any vertex A of ${\Gamma }_t(M_n(R)),$ we have:

   1. deg $(A)=\frac{|R{|}^{n^2}}{|I(A)|}-1$ if Tr $(A^2)\ne 0;$

   2. deg $(A)=\frac{|R{|}^{n^2}}{|I(A)|}-2$ if Tr $(A^2)=0.$

2. $\delta ({\Gamma }_t(M_n(R)))=|R{|}^{n^2-1}-2.$

3. If R is a field, then $\Delta ({\Gamma }_t(M_n(R)))=|R{|}^{n^2-1}-1.$

4.1 Irregularity index of the trace graph

Further Almahdi et al. [6] studied about the irregularity index of trace graph ${\Gamma }_t(M_n(R)).$ Recall that the degree sequence of a graph Γ is the list of vertex degrees (usually written in nonincreasing order, as $d_1\ge d_2\ge \cdots \ge d_k$). The irregularity index of $\Gamma ,$ noted $t(\Gamma )$ is the number of distinct terms in the degree sequence.

Let p and q be two prime numbers. It can be shown that, $t(\Gamma (\mathbb{Z}/p\mathbb{Z}\times \mathbb{Z}/q\mathbb{Z})$ is 1 if $p=q=2$ and 2 otherwise. In this section, we present results concerning the irregularity index of the trace graph of matrices. From Proposition 4.4, it is clear that $\delta ({\Gamma }_t(M_n(R)))\ne \Delta ({\Gamma }_t(M_n(R)))$ and hence, $t({\Gamma }_t(M_n(R)))\ge 2.$ It was proved in Example 3.1 [6] that $t({\Gamma }_t({\mathbb{Z}}_2\times {\mathbb{Z}}_2))=4.$ The results on the irregularity index are presented here.

The following lemmas are proved in [6].

Lemma 4.5

([6, Lemma 3.2]). Two isomorphic finite graphs have the same irregularity index.

Lemma 4.6

([6, Lemma 3.3]). Let R and $R\prime$ be two finite isomorphic rings and n > 1 be an integer. Then ${\Gamma }_t(M_n(R)))$ and (${\Gamma }_t(M_n(R\prime )))$ are isomorphic.

The next two results are concerned with the cases where $t({\Gamma }_t(M_n(R)))=2$ or 3.

Theorem 4.7

([6, Theorem 3.4]). Let R be a finite ring and $n\ge 2$ be an integer. Then $t({\Gamma }_t(M_n(R)))=2$ if and only if R is a field.

Theorem 4.8

([6, Theorem 3.5]). Let R be a finite ring and $n\ge 2$ be an integer. The following are equivalent:

1. $t({\Gamma }_t(M_n(R)))=3;$

2. R is a (local) ring with exactly one nontrivial ideal;

3. R is isomorphic to one of the of following two classes of rings: ${\mathbb{Z}}_p[X,Y]/(g(X),Y^2)$ and ${\mathbb{Z}}_{p^2}[X]/(g(X)+p\Omega \omega (X)),$ where p is a prime integer, g(X) is monic and irreducible in ${\mathbb{Z}}_p[X]$ and deg($\omega (X)$) < deg(g(X)).

Let I be an ideal of R. Let $\mu (I)$ denote the minimal number of generators of I, and $d(R)=\mathrm{\text{max}}\{\mu (I)|I\text{ is an ideal of} R\}.$ Questions on the number d(R) for various classes of commutative (local) rings have been studied. One type of question that has been considered is the determination of the rings R in a certain class with $d(R)\le n$ for certain small values of n. The next result describes the degree sequence of ${\Gamma }_t(M_n(R))$ with $n\ge 2$ such that $d(R)\le \frac{n(n-1)}{2}$.

Theorem 4.9

([6, Proposition 3.6]). Let R be a finite ring and $n\ge 2$ be an integer such that $d(R)\le \frac{n(n-1)}{2}.$ Then the list of vertex degrees of ${\Gamma }_t(M_n(R))$ is $\frac{|R{|}^{n^2}}{\left|I\right|}-2,\frac{|R{|}^{n^2}}{\left|J\right|}-1$ where I ranges over all nonzero ideals of R and J ranges over all nonzero ideals of R such that $J^2\ne 0.$

Corollary 4.10

([6, Corollary 3.7]). Let R be a finite reduced ring and $n\ge 2$ be an integer such that $d(R)\le \frac{n(n-1)}{2}.$ Then the list of vertex degrees of ${\Gamma }_t(M_n(R))$ is $\frac{|R{|}^{n^2}}{\left|I\right|}-2,\frac{|R{|}^{n^2}}{\left|I\right|}-1$ where I ranges over all nonzero ideals of R. Consequently $t({\Gamma }_t(M_n(R)))=2\left|\left\{\right|I|:I \text{is an nonzero ideal of} R\}\right|.$

Theorem 4.11

([6, Proposition 3.8]). Let (R, M) be a local ring with $M^2=0$ and $n\ge 2$ be an integer such that $d(R)\le n^2.$ Then the list of vertex degrees of ${\Gamma }_t(M_n(R))$ is $\frac{|R{|}^{n^2}}{\left|I\right|}-2,\frac{|R{|}^{n^2}}{\left|I\right|}-1$ where I ranges over all nonzero ideals of R. Consequently $t({\Gamma }_t(M_n(R)))=\left|\left\{\right|I|:I \text{is an nonzero ideal of} R\}\right|+1.$

4.2 Connectivity of the trace graph

Now, we present some results helpful in describing the basic structure of ${\Gamma }_t(M_n(R))$ like Eulerian, sub-Eulerian and super-Eulerian properties of the trace graph. Further, we present results concerning planarity, the thickness, Hamiltonian and domination of the trace graph. In view of Theorem 4.3, ${\Gamma }_t(M_n(R))$ can never be a bipartite graph.

Theorem 4.12

([23, Theorem 3.3]). Let R be a commutative ring with identity $1\ne 0$ and $n\ge 2$ be an integer. Then the eccentricity of every vertex of ${\Gamma }_t(M_n(R))$ is 2.

Remark 4.13

([23, Remark 3.2]). From Theorem 4.12, for a commutative ring R with identity $1\ne 0$ and an integer $n\ge 2,$ we have the following.

1. $\mathit{\text{rad}}({\Gamma }_t(M_n(R)))=2.$

2. ${\Gamma }_t(M_n(R))$ is self-centered.

We have the following known result involving vertex connectivity and diameter of a graph.

Theorem 4.14

([20, Plesník]). Let Γ be a simple graph of diameter two. Then $\kappa \prime (\Gamma )=\delta (\Gamma ).$

By making use of Theorems 4.3, 4.14, and Proposition 4.4(2), we have the following corollary.

Corollary 4.15

([23, Corollary 3.2]). Let R be a finite commutative ring with identity $1\ne 0$ and $n\ge 2$ be an integer. Then $\kappa \prime ({\Gamma }_t(M_n(R)))=|R{|}^{n^2-1}-2.$

Note that 2-connectivity of a graph is also called as biconnectivity and also it is a part of necessary condition for several graph theoretical properties of graphs. In the following theorem, it is proved that ${\Gamma }_t(M_n(R))$ is 2-connected.

Theorem 4.16

([23, Theorem 3.4]). Let R be a commutative ring with identity $1\ne 0$ and $n\ge 2$ be a positive integer. Then ${\Gamma }_t(M_n(R))$ is 2-connected. In particular, ${\Gamma }_t(M_n(R))$ has no cut vertices.

Theorem 4.17

([23, Theorem 3.5]). Let R be a commutative ring and let n₁, n₂ be two positive integers such that $n_1\le n_2.$ Then ${\Gamma }_t(M_{n_1}(R))$ is isomorphic to a subgraph of ${\Gamma }_t(M_{n_2}(R)).$

4.3 Eulerian properties of the trace graph

The study of Eulerian graphs was initiated by Euler $\prime$s solution of the K $\stackrel{..}{\mathrm{o}}$ nigsberg Bridge Problem in 1736. Even in cases where a graph is not Eulerian, there are interesting concepts concerning studies related to the Eulerian property of the graph viz. sub-Eulerian, super-Eulerian, subsemi-Eulerian etc. This section concentrates on such concepts for the trace graph of matrices over a commutative ring. In fact, it was proved that the trace graph contains at least one vertex of odd degree.

Theorem 4.18

([23, Theorem 4.1]). Let R be a finite commutative ring with identity and $n\ge 2$ be a positive integer. Then ${\Gamma }_t(M_n(R))$ contains at least one vertex of odd degree.

From the above theorem, it is obvious that for $n\ge 2,$ and for a finite commutative ring R, ${\Gamma }_t(M_n(R))$ is not Eulerian. In the following lemma, it was proved that the complement $\overline{{\Gamma }_t}(M_n(R))$ is connected which is used as a tool to provide a characterization for ${\Gamma }_t(M_n(R))$ to be sub-Eulerian. Recall that a graph is said to be sub-Eulerian if it is a spanning subgraph of some Eulerian graph and a non-Eulerian graph is said to be super-Eulerian if it has a spanning Eulerian subgraph.

Lemma 4.19

([23, Lemma 4.2]). Let R be a commutative ring with identity and $n\ge 2$ be a positive integer. The complement $\overline{{\Gamma }_t}(M_n(R))$ of the trace graph is connected.

The following theorem proves that ${\Gamma }_t(M_n(R))$ is sub-Eulerian.

Theorem 4.20

([23, Theorem 4.3]). Let R be a commutative ring with identity and $n\ge 2$ be a positive integer. Then ${\Gamma }_t(M_n(R))$ is sub-Eulerian.

Theorem 4.21

([23, Theorem 4.4]). Let R be a commutative ring with identity and $n\ge 3$ be a positive integer. Then every edge of ${\Gamma }_t(M_n(R))$ lies on a triangle.

Theorem 4.22

([23, Theorem 4.5]). Let R be a commutative ring with identity. Then every edge of ${\Gamma }_t(M_2(R))$ lies on a triangle.

Using Theorems 4.21 and 4.22, one can have the following which proves that ${\Gamma }_t(M_n(R))$ is super-Eulerian.

Theorem 4.23

([23, Theorem 4.6]). Let $n\ge 2$ be an integer and R be a finite commutative ring with identity. Then ${\Gamma }_t(M_n(R))$ is super-Eulerian.

From Theorems 4.21, 4.22 and the fact that ${\Gamma }_t(M_n(R))$ is connected, we have the following corollary.

Corollary 4.24

([23, Corollary 4.7]). Let R be a commutative ring with identity and $n\ge 2$ be a positive integer. Then ${\Gamma }_t(M_n(R))$ is triangulated.

Theorem 4.25

([23, Theorem 4.8]). Let R be a commutative ring with identity and $n\ge 2$ be a positive integer. Then every vertex of ${\Gamma }_t(M_n(R))$ lies on a cycle of length 4.

4.4 Planarity and thickness of trace graph

Here we look at the bounds for the genus of ${\Gamma }_t(M_n(R))$ and characterization for the trace graph of matrices over a finite commutative ring with identity having thickness 2. Let S_k denote the sphere with k handles, where k is a nonnegative integer, that is, S_k is an oriented surface with k handles. The genus of a graph G, denoted $g(G),$ is the minimal integer n such that the graph can be embedded in $S_n.$ Intuitively, G is embedded in a surface if it can be drawn in the surface so that its edges intersect only at their common vertices. If H is a subgraph of G, then $g(H)\le g(G).$ The graph-theoretical thickness (thickness, for short) of a graph G, denoted by $\Theta (G),$ is the minimum number of planar subgraphs into which the graph can be decomposed. The thickness of a planar graph is one.

We start with an observation of the existence of a maximal clique.

Theorem 4.26

([23, Theorem 6.1]). Let R be a commutative ring R with identity and $n\ge 2$ be an integer. Let $X=\{A=(a_{\mathit{\text{ij}}})\in M_n{(R)}^{*}:A$ is upper triangular with a_ii = 0 for every $i=1,\dots ,n\}$ and for $1\le i\le n,$ E_ii be the n × n matrix with 1 as the ${(i,i)}^{\mathit{\text{th}}}$ entry and 0 as the other entries. Then the set $X\cup {\left\{E_{\mathit{\text{ii}}}\right\}}_{i=1}^n$ is a maximal clique for ${\Gamma }_t(M_n(R))$ of order $|R{|}^{\frac{n(n-1)}{2}}+n-1.$

The statement in Theorem 4.26 also holds for lower triangular matrices instead of upper triangular matrices.

Theorem 4.27

([23, Theorem 6.3]). Let R be a commutative ring with identity. Then the following are true:

1. If $n\ge 2$ and $\left|R\right|\ge 3,$ then $g({\Gamma }_t(M_n(R)))\ge 9;$

2. If $n\ge 3$ and $\left|R\right|=2,$ then $g({\Gamma }_t(M_n(R)))\ge 4.$

3. If n = 2 and $\left|R\right|=2,$ then $g({\Gamma }_t(M_n(R)))\ge 2.$

From Theorem 4.27, we have the following corollary.

Corollary 4.28

([23, Theorem 6.2]). Let R be a commutative ring with identity and $n\ge 2$ be a positive integer. Then ${\Gamma }_t(M_n(R))$ is non-planar.

Theorem 4.29

([23, Theorem 6.4]). Let R be a finite commutative ring with identity and $n\ge 2$ be a positive integer. Then $\Theta ({\Gamma }_t(M_n(R)))=2$ if and only if n = 2 and $\left|R\right|=2.$

4.5 Hamiltonian nature of the trace graph

Here we observe that ${\Gamma }_t(M_n(R))$ can never be split or perfect graph. In the this regard, we see that the trace graph is Hamiltonian. Recall that a graph G is split if and only if no induced subgraph of G is a cycle on four($C_4)$ or five vertices($C_5)$, or a pair of disjoint edges($2K_2$). Also, it is well known that a graph G is perfect if and only if neither the graph G nor its graph complement $\overline{G}$ has an induced cycle of odd order $\ge 5.$A graph is said to be a theta graph if it is a 2-connected graph with two nonadjacent vertices of degree 3 and all other vertices of degree 2.

In the following theorem, we see that ${\Gamma }_t(M_n(R))$ contains a cycle of length 5 and hence it can never be a split graph or perfect graph.

Theorem 4.30

([24, Theorem 2.5]). Let $n\ge 2$ be an integer and R be a commutative ring with identity. Then ${\Gamma }_t(M_n(R))$ contains an induced cycle of length 5. Consequently ${\Gamma }_t(M_n(R))$ can never be a split graph and is an imperfect graph.

The following lemma is known.

Lemma 4.31

([12, Lemma 1]). Let G be a 2-connected graph on $p\ge 4$ vertices. Let C_k be a largest cycle of G in which $k<p.$ Then G has a theta subgraph containing $C_k.$

Lemma 4.32

([24, Theorem 3.1]). Let R be a commutative ring with identity and $n\ge 2$ be an integer. Then any largest cycle of ${\Gamma }_t(M_n(R))$ cannot be contained in a theta subgraph of ${\Gamma }_t(M_n(R)).$

Using Lemmas 4.31 and 4.32, it is proved that ${\Gamma }_t(M_n(R))$ is Hamiltonian and the same is stated below.

Theorem 4.33

([24, Theorem 3.2]). Let R be a commutative ring with identity and $n\ge 2$ be an integer. Then ${\Gamma }_t(M_n(R))$ is Hamiltonian.

4.6 Domination in trace graph of matrices

In this subsection, we present a result involving the domination number of ${\Gamma }_t(M_n(R))$ for a commutative semisimple ring. Further, first we present an upper bound for the domination number of ${\Gamma }_t(M_n(R))$ for $n\ge 2.$ Let R, S be commutative rings and $n\ge 2$ be a positive integer. One can realize that $M_n(R\times S)\cong M_n(R)\times M_n(S)$ through a ring isomorphism $\varphi :M_n(R\times S)\to M_n(R)\times M_n(S)$ defined by $$\begin{array}{c}\varphi \left(\left(\begin{array}{ccc}(a_{11},b_{11})& \dots & (a_{1n},b_{1n})\\ (a_{21},b_{21})& \dots & (a_{2n},b_{2n})\\ ⋮& \dots & ⋮\\ (a_{n1},b_{n1})& \dots & (a_{\mathit{\text{nn}}},b_{\mathit{\text{nn}}})\end{array}\right)\right)\hspace{1em}\\ =\left(\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ a_{21}& \dots & a_{2n}\\ ⋮& \dots & ⋮\\ a_{n1}& \dots & a_{\mathit{\text{nn}}}\end{array}\right),\left(\begin{array}{ccc}{b}_{11}& \dots & b_{1n}\\ b_{21}& \dots & b_{2n}\\ ⋮& \dots & ⋮\\ b_{n1}& \dots & b_{\mathit{\text{nn}}}\end{array}\right)\right).\end{array}$$

This gives that Tr $(A,B)=($ Tr $(A),$ Tr $(B))$ for $(A,B)\in M_n(R)\times M_n(S).$ Thus we have ${\Gamma }_t(M_n(R)\times M_n(S))\cong {\Gamma }_t(M_n(R\times S)).$

Theorem 4.34

([23, Theorem 5.1]). Let R, S be commutative rings and $n\ge 2$ be a positive integer. Then $$\gamma ({\Gamma }_t(M_n(R\times S)))=\mathrm{\text{min}}\left\{\gamma ({\Gamma }_t(M_n(R))),\gamma ({\Gamma }_t(M_n(S)))\right\}.$$

From the above, we get the domination number of the trace graph of a commutative semisimple ring. Also, we state an upper bound for the domination number of the trace graph of a commutative ring.

Theorem 4.35

([23, Theorem 5.2]). Let R be a commutative semisimple ring and $R\cong F_1\times F_2\times \cdots \times F_m,$ where $F_k^{\prime }s$ are fields. Then $$\gamma ({\Gamma }_t(M_n(R)))=\mathrm{\text{min}}\left\{\gamma ({\Gamma }_t(M_n(F_1))),\dots ,\gamma ({\Gamma }_t(M_n(F_m)))\right\}.$$

Theorem 4.36

([23, Theorem 5.3]). Let R be a commutative ring and $n\ge 2$ be a positive integer. Then $\gamma ({\Gamma }_t(M_n(R)))\le {(|R|-1)}^2+2.$

Remark 4.37

([23, Remark 5.4]). The bound obtained in Theorem 4.36 is sharp. For, one can check that $$X=\left\{\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right),\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\right\}$$ is a γ-set of the trace graph of ${\mathbb{Z}}_2.$ Thus $\gamma ({\Gamma }_t(M_2({\mathbb{Z}}_2)))=3={(|{\mathbb{Z}}_2|-1)}^2+2.$

5 Trace graph of matrices over a field

The study on graphs from matrix rings where the underlying ring is taken as a field provide some particularly exotic results. Consequently, the study of graphs from matrix rings over fields has received a great deal of attention from several authors, for which one can refer [1, 4, 15, 19]. In this section, we present results on the trace graph of matrices over a field. The following lemma reveals the cardinality of the vertex set of the trace graph $\Gamma (M_2(\mathbb{F}))$ which is used in the discussion of the relationship between the zero-divisor graph of matrices over finite fields and the trace graph of matrices over finite fields when $n=2.$

Lemma 5.1

([5, Lemma 2.1]). Suppose $\mathbb{F}$ is a field of order q. Then $|V(\Gamma (M_2(\mathbb{F})))|={(q+1)}^2(q-1).$

The following lemma deals with the isomorphism between the trace graph of matrices over isomorphic rings.

Lemma 5.2

([6, Lemma 3.3]). Let R and $R\prime$ be two finite isomorphic rings and n > 1 be an integer. Then ${\Gamma }_t(M_n(R))$ and ${\Gamma }_t(M_n(R\prime ))$ are isomorphic.

Let R₁ and R₂ be two commutative rings. By Lemma 5.2, if R₁ and R₂ are two isomorphic rings, then ${\Gamma }_t(M_n(R_1))\cong {\Gamma }_t(M_n(R_2)).$ Here we present, the relationship between R₁ and R₂ when ${\Gamma }_t(M_n(R_1))\cong {\Gamma }_t(M_n(R_2)).$ Further, the relationship between the trace graph of matrices over finite fields and the zero-divisor graph of matrices over finite fields is also provided.

Theorem 5.3

([29, Proposition 2]). Let R₁, R₂ be finite commutative rings with identity and $n_1,n_2\ge 2$ be positive integers. If ${\Gamma }_t(M_{n_1}(R_1))\cong {\Gamma }_t(M_{n_2}(R_2)),$ then $\left|R_1\right|=\left|R_2\right|$ and $n_1=n_2.$

In view of the above theorem, we have the following corollary.

Corollary 5.4

([29, Corollary 2]). Let $n_1,n_2\ge 2$ be positive integers. Then

${\Gamma }_t(M_{n_1}({\mathbb{Z}}_{m_1}))\cong {\Gamma }_t(M_{n_2}({\mathbb{Z}}_{m_2}))$ if and only if m₁ = m₂ and $n_1=n_2.$

Theorem 5.5

([29, Proposition 3]). Let R be a finite commutative ring with identity and $\mathbb{F}$ be a finite field and $n_1,n_2\ge 2$ be positive integers. Then ${\Gamma }_t(M_{n_1}(R))\cong {\Gamma }_t(M_{n_2}(\mathbb{F}))$ if and only if $R\cong \mathbb{F}$ and $n_1=n_2.$

Corollary 5.6

([29, Corollary 3]). Let ${\mathbb{F}}_1$ and ${\mathbb{F}}_2$ be finite fields and $n\ge 2$ be an integer. Then

${\Gamma }_t(M_n({\mathbb{F}}_1)\cong {\Gamma }_t(M_n({\mathbb{F}}_2))$ if and only if ${\mathbb{F}}_1\cong {\mathbb{F}}_2.$

Theorem 5.7

([29, Proposition 4]). Let $\mathbb{F}$ be a finite field and $n\ge 2$ be an integer.

1. For two adjacent matrices $A,B\in V({\Gamma }_t(M_n(\mathbb{F}))),$

2. $|N(A)\cap N(B)|=|\mathbb{F}{|}^{n^2-2}-ϵ$ or $|\mathbb{F}{|}^{n^2-1}-ϵ,$

3. where $ϵ=\{\begin{array}{cc}1\hfill & \text{if Tr }(A^2),\text{Tr}(B^2)\ne 0;\hfill \\ 2\hfill & \text{if Tr }(A^2)=0\text{ or Tr}(B^2)=0\text{ but not both;}\hfill \\ 3\hfill & \text{if Tr }(A^2),\text{Tr}(B^2)=0.\hfill \end{array}$

4. For two non-adjacent matrices $A,B\in V({\Gamma }_t(M_n(\mathbb{F}))),$

5. $|N(A)\cap N(B)|=|\mathbb{F}{|}^{n^2-2}-1$ or $|\mathbb{F}{|}^{n^2-1}-1.$

Fig. 3 Subgraph induced by $〈Z{(M_2({\mathbb{Z}}_2))}^{*}〉$ of ${\Gamma }_t(M_2({\mathbb{Z}}_2))$.

It is clear that $\Gamma (M_n(R))$ is a subgraph of ${\Gamma }_t(M_n(R)).$ The following is an example of a ring R in which the subgraph of ${\Gamma }_t(M_n(R))$ induced by the set of zero-divisor of $M_n(R)$ is exactly $\Gamma (M_n(R)).$

Example 5.8.

Consider the ring $M_2({\mathbb{Z}}_2).$ Then $Z(M_2{({\mathbb{Z}}_2)}^{*})=\{A_1,\dots ,A_9\}$ where $A_1=(\begin{array}{cc}1& 0\\ 0& 1\end{array}),A_2=(\begin{array}{cc}1& 1\\ 0& 0\end{array}),A_3=(\begin{array}{cc}0& 0\\ 0& 1\end{array}),A_4=(\begin{array}{cc}0& 0\\ 1& 1\end{array}),A_5=(\begin{array}{cc}0& 1\\ 0& 1\end{array}),A_6=(\begin{array}{cc}1& 0\\ 0& 0\end{array}),A_7=(\begin{array}{cc}0& 1\\ 0& 0\end{array}),A_8=(\begin{array}{cc}0& 0\\ 1& 0\end{array}),A_9=(\begin{array}{cc}1& 1\\ 1& 1\end{array}).$

One can easily check that Tr $(A_i{A}_j)=0$ if and only if $A_i{A}_j=O$ or $A_j{A}_i=O.$ The following figure illustrates this fact graphically.

However, this is not always the case. The following is an example to show that $\Gamma (M_n(R))$ is not always equal to the induced subgraph $〈Z{(M_n(R))}^{*}〉$ of ${\Gamma }_t(M_n(R)).$

Theorem 5.9

([29, Theorem 5]). Let $\mathbb{F}$ be a finite field and $n\ge 2$ be an integer. Then $\Gamma (M_n(\mathbb{F}))$ is an induced subgraph of ${\Gamma }_t(M_n(\mathbb{F}))$ if and only if $n=2.$

5.1 Domination parameters of trace graph over fields

In this section, we present results concerning the domination number of ${\Gamma }_t(M_n(\mathbb{F}))$ and the values of other domination parameters like paired, total and inverse domination numbers of the trace graph of a matrix ring over a finite field $\mathbb{F}.$

Theorem 5.10

([29, Lemma 3]). Let $n\ge 2$ be an integer and $\mathbb{F}$ be a finite field. Then $\gamma ({\Gamma }_t(M_n(\mathbb{F})))\ge \left|\mathbb{F}\right|+1.$

The domination number for the trace graph of matrices over ${\mathbb{Z}}_2$ was obtained by Sivagami and Tamizh Chelvam [23]. The following theorem generalizes this result for any field $\mathbb{F}.$

Theorem 5.11

([29, Theorem 6]). Let $n,\mathcal{l},k$ be positive integers such that $n\ge 2,\mathcal{l},k\le n,$ $\mathbb{F}$ be a finite field, $A=(a_{\mathit{\text{ij}}})\in M_n{(\mathbb{F})}^{*}$ be a matrix. Let $S=\{A_x=A+x{E}_{\mathcal{l}k}:x\in \mathbb{F}\}.$ Then $S\cup \left\{E_{\mathcal{l}k}\right\}$ is a γ-set of ${\Gamma }_t(M_n(\mathbb{F}))$ of order $\left|\mathbb{F}\right|+1.$ Moreover, $\gamma ({\Gamma }_t(M_n(\mathbb{F})))=\left|\mathbb{F}\right|+1.$

In Theorem 5.11, one can replace E_nn by arbitrary $E_{\mathcal{l}k}$ to obtain a γ-set for ${\Gamma }_t(M_n(\mathbb{F})).$ From Theorem 5.11, one can observe the following corollary.

Corollary 5.12

([29, Corollary 4]). For an integer $n\ge 2$ and a finite field $\mathbb{F},$ ${\Gamma }_t(M_n(\mathbb{F}))$ is an excellent graph.

Theorem 5.13

([29, Proposition 5]). Let $n\ge 2$ be an integer and $\mathbb{F}$ be a finite field. Then $$\gamma \prime ({\Gamma }_t(M_n(\mathbb{F})))=\left|\mathbb{F}\right|+1.$$

Theorem 5.14

([29, Theorem 7]). Let $n\ge 2$ be an integer and $\mathbb{F}$ be a finite field. Then $${\gamma }_{\mathit{\text{pr}}}({\Gamma }_t(M_n(\mathbb{F})))=\{\begin{array}{cc}\left|\mathbb{F}\right|+1\hfill & \text{if char }\mathbb{F}\ne 2;\hfill \\ \left|\mathbb{F}\right|+2\hfill & \text{if char }\mathbb{F}=2.\hfill \end{array}$$

Theorem 5.15

([29, Proposition 6]). Let $n\ge 2$ be an integer and $\mathbb{F}$ be a finite field. Then $${\gamma }_t({\Gamma }_t(M_n(\mathbb{F})))=\left|\mathbb{F}\right|+1.$$

The following corollary is immediate from Theorems 4.34 and 5.10.

Corollary 5.16

( [29, Corollary 5]). Let $m\ge 2$ and ${\mathbb{F}}_1,{\mathbb{F}}_2,\dots ,{\mathbb{F}}_m$ be finite fields. For any positive integer $n\ge 2,$ $$\gamma ({\Gamma }_t(M_n(F_1\times F_2\times \cdots \times F_m)))=\mathrm{\text{min}}\left\{\right|F_1|,|F_2|,\dots ,|F_m\left|\right\}+1.$$

By Theorems 4.35 and 5.10, we have the following corollary.

Corollary 5.17.

Let R be a commutative semisimple ring which is a direct product fields $F_1,F_2,\dots ,F_m$ with $m\ge 2.$ Then $$\gamma ({\Gamma }_t(M_n(R)))=\mathrm{\text{min}}\left\{\left|F_1\right|,\left|F_2\right|,\dots ,\left|F_m\right|\right\}+1.$$

6 Ideal based trace graph of matrices

In ring theory, the ideals are so important, in fact there are entire classes of rings defined by how their ideals behave. The two most important classes are Noetherian ring and principal ideal domain. A commutative ring is called Noetherian if all of its ideals are finitely generated. An integral domain is called a principal ideal domain if all of its ideals are principal. Thus ideals are literally the cornerstone of everything interesting in the subject. In 2001, S. P. Redmond [22] introduced the concept of ideal based zero-divisor graph of a commutative ring R with respect to an ideal I of R. This turns out to be a very natural generalization of the zero-divisor graph. Redmond notes a strong connection between ${\Gamma }_I(R)$ and $\Gamma (R/I).$ Redmond describes a three step construction method for ${\Gamma }_I(R)$ based on $\Gamma (R/I).$ Properties of the ideal based zero-divisor graph have been studied by various authors [13, 18]. In analogous to the generalization of zero-divisor graph to ideal based zero-divisor graph, Tamizh Chelvam and Sivagami [28] generalized the notion of the trace graph ${\Gamma }_t(M_n(R))$ of a matrix ring $M_n(R)$ to the trace graph ${\Gamma }_{I^t}(M_n(R))$ with respect to an ideal I of R. A strong connection between ${\Gamma }_t(M_n(R))$ and ${\Gamma }_{I^t}(M_n(R))$ has been recognized.

Let I be an ideal of R. The trace graph of the matrix ring $M_n(R)$ with respect to an ideal I of R, denoted by ${\Gamma }_{I^t}(M_n(R)),$ is the simple undirected graph with vertex set $M_n(R)\setminus M_n(I)$ and two distinct vertices A and B are adjacent if and only if Tr $(\mathit{\text{AB}})\in I.$ In this section, we exhibit some properties and structure of ${\Gamma }_{I^t}(M_n(R)).$ In due course, it was proved that ${\Gamma }_{I^t}(M_n(R)$ is Hamiltonian. Further, some results on domination number of ideal based trace graphs with respect to some ideals I in R is also highlighted.

Recall that if $A=[a_{\mathit{\text{ij}}}]\in M_n(R)\setminus M_n(I)$ the corresponding matrix in $M_n(R/I)$ is $[a_{\mathit{\text{ij}}}+I].$ If $A=[a_{\mathit{\text{ij}}}]\in M_n(I),$ then the corresponding matrix in $M_n(R/I)$ is the zero matrix in $M_n(R/I).$ For convenience, we denote the matrix $[a_{\mathit{\text{ij}}}+I]\in M_n(R/I)$ as $\overline{A}$ corresponding to the matrix $A=(a_{\mathit{\text{ij}}}).$

6.1 Girth and diameter

In this section, we list some properties of the trace graph of matrix ring with respect to an ideal I of R that can be proved by similar arguments as in the case of the trace graph of matrix rings over commutative rings. For $A=[a_{\mathit{\text{ij}}}]\in M_n(R),$ we set $J_I(A)=\sum _{1\le i,j\le n}(R/I)(a_{\mathit{\text{ij}}}+I)\in (R/I);$ the sum of the ideals of R/I generated by all entries of $A=[a_{\mathit{\text{ij}}}+I]$ over $R/I.$ Note that $J_I(A)$ is an ideal of $R/I.$

Proposition 6.1

([28, Proposition 2.1]). For a non-zero ideal I of a commutative ring R and an integer $n\ge 2,$ ${\Gamma }_{I^t}(M_n(R)))$ contains no isolated vertex.

In the following, we observe that no vertex in ${\Gamma }_{I^t}(M_n(R))$ is adjacent to all other vertices.

Proposition 6.2

([28, Proposition 2.2]). For a non-zero ideal I of a commutative ring R and an integer $n\ge 2,$ no vertex of ${\Gamma }_{I^t}(M_n(R))$ is adjacent to every other vertex of ${\Gamma }_{I^t}(M_n(R)).$

Now we see, the degree of vertices in ${\Gamma }_{I^t}(M_n(R)).$

Proposition 6.3

([28, Proposition 2.3]). Let R be a finite commutative ring and $n\ge 2$ be an integer.

1. For any vertex A of ${\Gamma }_{I^t}(M_n(R)),$ we have:

   1. deg $(A)=\frac{|R{|}^{n^2}}{|J_I(A)|}-1$ if Tr $(A^2)\notin I,$ and

   2. deg $(A)=\frac{|R{|}^{n^2}}{|J_I(A)|}-2$ if Tr $(A^2)\in I.$

2. $\delta ({\Gamma }_t(M_n(R)))=\left|R{|}^{n^2-1}\right|I|-2.$

From Proposition 6.3, for a finite commutative ring R, ${\Gamma }_{I^t}(M_n(R))$ can never be an Eulerian graph. For, consider the matrices E₁₁ and $E_{1n}$ where $n\ne 1.$ Tr $(E_{11}^2)=1\notin I$ and Tr $(E_{1n}^2)=0\in I.$ Hence, by the Proposition 6.3, either of E₁₁ and $E_{1n}$ must have odd degree.

Proposition 6.4

([28, Proposition 2.4]). Let R be a commutative ring, $n\ge 2$ be an integer and I be a nontrivial ideal of R. Then ${\Gamma }_{I^t}(M_n(R))$ is connected with $\mathit{\text{diam}}({\Gamma }_{I^t}(M_n(R)))=2$ and $\mathit{\text{gr}}({\Gamma }_{I^t}(M_n(R)))=3.$

Remark 6.5

([28, Remark 2.5] ).

1. By Theorem 4.21 and Proposition 6.4, the eccentricity of every vertex in ${\Gamma }_{I^t}(M_n(R))$ is 2 and hence the radius of ${\Gamma }_{I^t}(M_n(R))$ is 2, that is, the graph ${\Gamma }_{I^t}(M_n(R))$ is self-centered.

2. By Proposition 6.4 ${\Gamma }_{I^t}(M_n(R))$ contains an odd cycle, and so ${\Gamma }_{I^t}(M_n(R))$ can never be a bipartite graph.

6.2 Interlink between trace and ideal based trace graphs

In this section, we list properties of the graph ${\Gamma }_{I^t}(M_n(R))$ through ${\Gamma }_t(M_n(R/I)).$ We explore the relationship between the structure of ${\Gamma }_t(M_n(R/I))$ and ${\Gamma }_{I^t}(M_n(R))$ throughout this section. In the sequel, we see the relationship between ${\Gamma }_t(M_n(R))$ and ${\Gamma }_{I^t}(M_n(R)).$

Theorem 6.6

([28, Theorem 3.3]). Let I be an ideal of a commutative ring R, $n\ge 2$ be a positive integer and $A=[a_{\mathit{\text{ij}}}],B=[b_{\mathit{\text{ij}}}]\in M_n(R)\setminus M_n(I)$ Then the following are true:

1. If $\overline{A}$ is adjacent to $\overline{B}$ in ${\Gamma }_t(M_n(R/I)),$ then A and B are adjacent in ${\Gamma }_{I^t}(M_n(R)).$

2. If A is adjacent to B in ${\Gamma }_{I^t}(M_n(R))$ and $\overline{A}\ne \overline{B},$ then $\overline{A}$ is adjacent to $\overline{B}$ in ${\Gamma }_t(M_n(R/I)).$

3. If A is adjacent to B in ${\Gamma }_{I^t}(M_n(R))$ and $\overline{A}=\overline{B},$ then Tr $(A^2),$ Tr $(B^2)\in I.$

4. If Tr $(A^2)\in I$ and $\overline{A}=\overline{B},$ then A is adjacent to B in ${\Gamma }_{I^t}(M_n(R))$ and Tr $(B^2)\in I.$

5. If A and B are (distinct) adjacent vertices in ${\Gamma }_{I^t}(M_n(R))$, then all (distinct) elements of $\overline{A}$ are adjacent to all elements of $\overline{B}$ in ${\Gamma }_{I^t}(M_n(R)).$ In particular, if $\mathit{\text{Tr}}(A^2)\in I,$ then all the distinct elements of $\overline{A}$ are adjacent in ${\Gamma }_{I^t}(M_n(R)).$

Corollary 6.7

([28, Corollary 3.4]). Let I be an ideal of a commutative ring R and $n\ge 2$ be a positive integer. Then ${\Gamma }_{I^t}(M_n(R))$ contains $|M_n(I)|$ disjoint subgraphs each isomorphic to ${\Gamma }_t(M_n(R/I)).$

Remark 6.8

([28, Remark 3.5]). The following are true:

1. ${\Gamma }_t(M_n(R)/M_n(I))$ is a graph with $\left|M_n(R/I)\right|-1$ vertices.

2. ${\Gamma }_{I^t}(M_n(R))$ is a graph with $\left|M_n(R)\right|-\left|M_n(I)\right|$ vertices.

3. Let R be a finite commutative ring. Note that Corollary 6.7 exhibits a partition of ${\Gamma }_{I^t}(M_n(R))$ into vertex disjoint subgraphs. Thus

   $\left|M_n(I)\right|\left|V({\Gamma }_t(M_n(R/I)))\right|=\left|V({\Gamma }_{I^t}(M_n(R)))\right|.$

The following theorem puts forth a partition of ${\Gamma }_{I^t}(M_n(R))$ into edge disjoint subgraphs. In view of Theorem 6.6 (iv), if Tr $(A^2)\in I$ and $\overline{A}=\overline{B},$ then A is adjacent to B in ${\Gamma }_{I^t}(M_n(R))$ and Tr $(B^2)\in I.$ This means that if Tr $(A^2)\in I$ for a matrix A, then the same is true for all matrices in the coset of A.

Theorem 6.9

([28, Theorem 3.6]). Let R be a commutative ring with identity, I be a non-trivial ideal of R, $n\ge 2$ be an integer and $$\lambda =\left|\right\{\overline{A}\in V({\Gamma }_t(M_n(R/I))):\text{Tr}(A^2)\in I\hspace{1em}\text{and}$$ $$\hspace{1em}A \text{is a coset representative of} \overline{A}\left\}\right|.$$

Then ${\Gamma }_{I^t}(M_n(R))\cong |M_n(I){|}^2{\Gamma }_t(M_n(R/I))\oplus \lambda K_{|M_n(I)|}.$

6.3 Graph parameters of ideal based trace graph

In this section, we see certain bounds for the clique, chromatic and independence numbers of ${\Gamma }_{I^t}(M_n(R))$ and state a condition for the chromatic and clique numbers of ${\Gamma }_{I^t}(M_n(R))$ to be equal.

Theorem 6.10

([28, Theorem 4.1]). Let $n\ge 2$ be an integer, R be a commutative ring and I be a non-trivial ideal of R. Then the following hold:

1. $\omega ({\Gamma }_t(M_n(R/I)))\le \omega ({\Gamma }_{I^t}(M_n(R)))\le |M_n(I)|\omega ({\Gamma }_t$ $(M_n(R/I))).$

   Moreover, the equality $\omega ({\Gamma }_{I^t}(M_n(R)))=|M_n(I)|\omega ({\Gamma }_t(M_n(R/I)))$ holds if there exists a clique of maximum order in ${\Gamma }_t(M_n(R/I))$ such that Tr $(A^2)\in I$ for every vertex $\overline{A}$ in the clique.

2. $\chi ({\Gamma }_t(M_n(R/I)))\le \chi ({\Gamma }_{I^t}(M_n(R)))\le |M_n(I)|$ $\chi ({\Gamma }_t(M_n(R/I))).$

The following theorem is a generalization of the moreover case of Theorem 6.10 (i).

Theorem 6.11

([28, Theorem 4.2]). Let $n\ge 2$ be an integer, R be a commutative ring and I be a non-trivial ideal in R. Let S be a clique of maximum order in ${\Gamma }_t(M_n(R/I))$ and S have the largest number of elements $\overline{A}$ with Tr $(A^2)\in I.$ Let $X=\{\overline{A}\in S:\text{Tr}(A^2)\notin I\}.$ Then $\omega ({\Gamma }_{I^t}(M_n(R)))=\left|X\right|+|M_n(I)|(\omega ({\Gamma }_t(M_n(R/I)))-|X|).$

Theorem 6.12

([28, Theorem 4.3]). Let $n\ge 2$ be an integer, R be a commutative ring and I be a non-trivial ideal of R. Let ${\Gamma }_t(M_n(R/I))$ contain a clique of maximum order such that Tr $(A^2)\in I$ for every $\overline{A}$ in the clique. If $\chi ({\Gamma }_t(M_n(R/I)))=\omega ({\Gamma }_t(M_n(R/I))),$ then $\chi ({\Gamma }_{I^t}(M_n(R)))=\omega ({\Gamma }_{I^t}(M_n(R))).$

Theorem 6.13

([28, Theorem 4.4]). Let $n\ge 2$ be an integer, R be a commutative ring and I be a non-trivial ideal of R. Then

1. $\alpha ({\Gamma }_t(M_n(R/I)))\le \alpha ({\Gamma }_{I^t}(M_n(R)))\le |M_n(I)|\alpha ({\Gamma }_t$ $(M_n(R/I)));$

2. In particular, if there exists an independent set of maximum order in ${\Gamma }_t(M_n(R/I))$ such that Tr $(A^2)\notin I$ for every vertex A in the independent set, then $$\alpha ({\Gamma }_{I^t}(M_n(R)))=|M_n(I)|\alpha ({\Gamma }_t(M_n(R/I))).$$

6.4 Domination in ${\Gamma }_{I^t}(M_n(R))$

In this section, we see the relationship between $\gamma ({\Gamma }_t(M_n(R/I)))$ and $\gamma ({\Gamma }_{I^t}(M_n(R)))$ and present the value of $\gamma ({\Gamma }_{I^t}(M_n(R)))$ for certain ideals I of R.

Theorem 6.14

([29, Proposition 7]). Let I be an ideal of a commutative ring R, $n\ge 2$ be an integer and S be a nonempty subset of $M_n(R)\setminus M_n(I).$ If $S=\{[a_{\mathit{\text{ij}}}]:1\le i,j\le n\}$ is a dominating set of ${\Gamma }_{I^t}(M_n(R)),$ then $S+M_n(I)=\{[a_{\mathit{\text{ij}}}]+M_n(I):[a_{\mathit{\text{ij}}}]\in S\}=\{[a_{\mathit{\text{ij}}}+I]:[a_{\mathit{\text{ij}}}]\in S\}$ is a dominating set of ${\Gamma }_t(M_n(R/I)).$ Moreover, $\gamma ({\Gamma }_t(M_n(R/I)))\le \gamma ({\Gamma }_{I^t}(M_n(R))).$

Theorem 6.15

([29, Proposition 8]). Let $n\ge 2$ be an integer, R be a commutative local ring and I be the maximal ideal of R. Then $\gamma ({\Gamma }_{I^t}(M_n(R)))=\left|\frac{R}{I}\right|+1.$

Let R and S be commutative rings with identity. From [23, p. 245], we have $M_n(R\times S)\cong M_n(R)\times M_n(S)$ and for $(A,B)\in M_n(R)\times M_n(S)$, Tr $((A,B))=($ Tr $(A),$ Tr $(B)).$

Theorem 6.16

([29, Proposition 9]). Let $n,m\ge 2$ be two integers, $R=R_1\times \cdots \times R_m$ be a commutative ring and $I=I_1\times \cdots \times I_m$ be an ideal in R. Then $\gamma ({\Gamma }_{I^t}(M_n(R)))=\mathrm{\text{min}}\{\gamma ({\Gamma }_{I_i^t}(M_n(R_i))):I_i\ne R_i\}.$

Corollary 6.17

([29, Corollary 6]). Let $R=R_1\times \cdots \times R_m$ be a finite commutative Artinian ring where $m\ge 2$ and (R_i , M_i ) is a local ring for $1\le i\le m.$ Let $I=I_1\times \cdots \times I_m$ be an ideal in R such that I_i = R_i or $M_i.$ Then for any integer $n\ge 2,$ $\gamma ({\Gamma }_{I^t}(M_n(R)))=\mathrm{\text{min}}\left\{\left|\frac{R_i}{I_i}\right|+1:I_i\ne R_i,1\le i\le m\right\}.$

7 Symmetry trace graph

Note that the graph ${\Gamma }_t(M_n(R))$ can only be defined over square matrices. Thus Dein Wonga et al. [30] attempted to improve the definition such that the newly defined graph can be over rectangular matrices. If $m\ne n$ and $A,B\in M_{m,n}(R)$ are rectangular matrices, tr($\mathit{\text{AB}})$ does not make sense and tr($\mathit{\text{AB}}\prime$) is well-defined where $B\prime$ is the transpose of B. A new graph of $M_{m,n}(R),$ denoted by ${\Gamma }^t(M_{m,n}(R))$ and called symmetry trace graph, is defined in a natural way as follows: The vertex set of ${\Gamma }^t(M_{m,n}(R))$ consists of all nonzero matrices of $M_{m,n}(R)$ and two distinct vertices A and B are adjacent if and only if tr($\mathit{\text{AB}}\prime$)=0. Having defined the new symmetry trace graphs authors have studied about the automorphisms of ${\Gamma }^t(M_{m,n}(R)).$ When R is the real field $\mathbb{R},$ with the help of characterization of the maximum cliques of ${\Gamma }^t(M_{m,n}(R))$ authors have obtained the form of an arbitrary automorphism of ${\Gamma }^t(M_{m,n}(R)).$

8 Conclusion and open problems

In this survey, we have presented results concerning graphs from matrices. In particular, we have included properties of zero-divisor graphs of matrices, trace graph of matrices and ideal based trace graph of matrices. This include basic graph theoretical properties like diameter, girth, connectedness, Eulerian, Hamiltonian and domination. These shall give a overview of the research carried in the domain of graphs from matrices over commutative rings. The research on matrices shall give a way to attempt problems related to graphs from non-commutative rings through Artin semi-simple theorem. Now, we present some problems related to trace graph the direct product of matrix rings.

Problem 1.

For two commutative rings R and S, study about the trace graph of direct product ring $M_n(R)\times M_n(S).$

Problem 2.

Study about the trace graph of direct product ring $M_{n_1}(R)\times M_{n_2}(R)$ where R is a commutative ring and n₁ and n₂ are two different integers.

Problem 3.

Study about the trace graph of direct product ring $M_{n_1}(D)\times M_{n_2}(D)\times \cdots \times M_{n_k}(D)$ where D is an integral domain and n_i are positive integers.

Problem 4.

Obtain characterization for Hamiltonian nature of symmetry trace graph of a commutative ring.

Additional information

Funding

This research work is supported by CSIR Emeritus Scientist Scheme (No. 21 (1123)/20/EMR-II) of Council of Scientific and Industrial Research, Government of India.