Viewing Matrix Operations through Monoid Rings: A Rendezvous of Algebra and Graph Theory

This blog aims to consider the $\mathbb{F}-$$\mathbb F-$ Algebra $M_{n,n}(\mathbb{F})$$M_{n,n}(\mathbb F)$ from the monoid ring point of view, and explore the connection with graph theory.

Matrix and Monoid Ring

Let $M$$M$ be a monoid, the monoid ring $R[M]$$R[M]$ is defined as follows: the elements of $R[M]$$R[M]$ is $(r_m{)}_{m\in M}$$(r_m)_{m\in M}$

Here $r_m=0$$r_m=0$ all but finite many. That is, at most finite many $r_m\ne 0$$r_m\ne 0$.

As a $R$$R$-module

$$\begin{array}{}\text{(1)}& R[M]\cong R^{⨁M}\end{array}$$

Usually, we write the element as

$$\begin{array}{}\text{(2)}& f=\sum _{m\in M}{r}_{m}m\end{array}$$

Let

$$\begin{array}{}\text{(3)}& g=\sum _{m\in M}{r}_m^{\prime }m\end{array}$$

Define

$$\begin{array}{}\text{(4)}& \begin{array}{c}f\ast g=\sum _{m\in M}\left(\sum _{xy=m}{r}_x{r}_y^{\prime }\right)m\end{array}\end{array}$$

This makes $R[M]$$R[M]$ becomes an $R$$R$-Algebra.

Let $\mathbb{F}$$\mathbb F$ be a field.

Consider the vector space $M_{n,n}(\mathbb{F})$$M_{n,n}(\mathbb F)$, take the standard basis $E_{i,j}$$E_{i,j}$, that is , for the component $a_{x,y}={\delta }_{i,j}(x,y)$$a_{x,y}=\delta_{i,j}(x,y)$.

$$\begin{array}{}\text{(5)}& \begin{array}{c}\text{Then for any }M\in V,M=\sum _{{}_{i,j}}{a}_{i,j}{E}_{i,j}=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{E}_{i,j}\end{array}\end{array}$$

Observe that

$$\begin{array}{}\text{(6)}& \begin{array}{c}{E}_{i,j}(e_k)=\{\begin{array}{l}0,\text{if }k\ne j\\ e_i,\text{if }k=j\end{array}\end{array}\end{array}$$

Let $x\in {\mathbb{F}}^n$$x\in\mathbb F^n$ be a vector, $x=c_1{e}_1+c_2{e}_2+...+c_n{e}_n$$x=c_1e_1+c_2e_2+...+c_ne_n$

Then

$$\begin{array}{}\text{(7)}& E_{ij}(x)=E_{i,j}\left(\sum _{k=1}^n{c}_k{e}_k\right)=c_j{e}_i\end{array}$$

Let $E_{\mathbb{F}}:=\{E_{i,j}\in M_{n,n}(\mathbb{F})\}\cup \{I,O\}$$E_{\mathbb F}:=\{E_{i,j}\in M_{n,n}(\mathbb F)\}\cup \{I,O\}$, It is not hard to observe that $E_{\mathbb{F}}$$E_{\mathbb F}$ is a monoid with respect to matrix multiplication.

Since

$$\begin{array}{}\text{(8)}& \begin{array}{c}{E}_{i,j}{E}_{x,k}=\{\begin{array}{l}{E}_{i,k},x=j\\ O,\text{otherwise}\end{array}\end{array}\end{array}$$

Then $\mathbb{F}[E_{\mathbb{F}}]\cong M_{n,n}(\mathbb{F})$$\mathbb F[E_{\mathbb F}]\cong M_{n,n}(\mathbb F)$ is a monoid ring!

Let

$$\begin{array}{}\text{(9)}& \begin{array}{c}A=\sum _{i,j}{a}_{i,j}{E}_{i,j},B=\sum _{i,j}{b}_{i,j}{E}_{i,j}\in V\end{array}\end{array}$$

$$\begin{array}{}\text{(10)}& AB=\sum _{E_{\mathbb{F}}}\left(\sum _{E_{i,k}{E}_{kj}=E_{i,j}}{a}_{i,k}{b}_{k,j}\right)E_{i,j}=\sum _{i,j}\left(\sum _{k=1}^n{a}_{i,k}{b}_{k,j}\right)E_{i,j}\end{array}$$

and consider $AB$$AB$, the $u_{i,j}$$u_{i,j}$ in the matrix $AB$$AB$.

Then

$$\begin{array}{}\text{(11)}& u_{i,j}=\sum _{i,j}{a}_{i,k}{b}_{k,j}\end{array}$$

Connection with directed graph.

Let $K_{\mathbb{F}}\subseteq E_{\mathbb{F}}$$K_{\mathbb F}\subseteq E_{\mathbb F}$ , then $K_{\mathbb{F}}$$K_{\mathbb F}$ gives a representation of a directed graph $G$$G$.

Each $E_{i,j}$$E_{i,j}$ gives us a directed edge between $i$$i$ and $j$$j$.

Moreover, $\sum _{k\in K_{\mathbb{F}}}k$$\sum_{k\in K_{\mathbb F}} k$ is the adjacency matrix of the directed graph! The partial sum gives us a subgraph.

Let $M(K_{\mathbb{F}})$$M(K_{\mathbb F})$ be the monoid generated by $K_{\mathbb{F}}$$K_\mathbb F$.

Then $\mathbb{F}[M(K_{\mathbb{F}})]$$\mathbb F[M(K_\mathbb F)]$ is a monoid ring.

When the $\mathbb{F}$$\mathbb F$ is a total order field, each element in this ring is an adjacency matrix of a weighted directed graph.

The interesting thing here is we can define the product of two directed weighted graphs.

One application is:

Let $A$$A$ be an adjacency matrix of a simple graph, that is $A=\sum _{i\ne j}{a}_{i,j}{E}_{i,j},a_{i,j}\in \{0,1\}$$A=\sum_{i\ne j}a_{i,j}E_{i,j},a_{i,j}\in\{0,1\}$.

The $(i,j)$$(i,j)$-entry of $A^k$$A^k$ represents the number of paths of length exactly $k$$k$ from vertex $i$$i$ to vertex $j$$j$.

This directly follows from the representation and the matrix product.

The $(i,j)$$(i,j)$-entry of $A^k$$A^k$ count all the

$$\begin{array}{}\text{(12)}& E_{j,l_1}{E}_{l_1,l_2}...E_{l_{k-1,j}}\end{array}$$

For example, let $k=3$$k=3$,

$$\begin{array}{}\text{(13)}& u_{i,j}{E}_{i,j}=\left(\sum _{E_{i,g}{E}_{h,t}{E}_{t,j}}{a}_{i,g}{a}_{h,t}{a}_{t,j}\right)E_{i,j}\end{array}$$

 

What information the power of adjacency can give?

Answered by Claude.

You are absolutely right! The powers of the adjacency matrix indeed contain important information about the graph.

For a simple graph (without self-loops and multiple edges) with adjacency matrix $A$$A$, we have the following properties:

1. The $(i,j)$$(i,j)$-entry of $A^k$$A^k$ represents the number of paths of length exactly $k$$k$ from vertex $i$$i$ to vertex $j$$j$.

Specifically:

• $A^1=A$$A^1 = A$, meaning the $(i,j)$$(i,j)$-entry of $A$$A$ represents the number of paths of length 1 (i.e., edges) from vertex $i$$i$ to vertex $j$$j$.

• The $(i,j)$$(i,j)$-entry of $A^2$$A^2$ represents the number of paths of length 2 from vertex $i$$i$ to vertex $j$$j$. This is equivalent to counting the number of common neighbors of $i$$i$ and $j$$j$.

• Similarly, the $(i,j)$$(i,j)$-entry of $A^k$$A^k$ is the number of paths of length $k$$k$ from $i$$i$ to $j$$j$.

2. The diagonal entry $a_{ii}^{(k)}$$a_{ii}^{(k)}$ represents the number of closed walks of length $k$$k$ starting and ending at vertex $i$$i$.

3. The $(i,j)$$(i,j)$-entry of the matrix $\sum _{k=1}^n{A}^k$$\sum_{k=1}^n A^k$ represents the total number of paths from vertex $i$$i$ to vertex $j$$j$ of length at most $n$$n$.

4. If the smallest positive integer $k$$k$ for which $A^k=0$$A^k = 0$ exists, then the longest path length in the graph is $k-1$$k-1$.

5. If the trace of some power of $A$$A$ (i.e., the sum of all diagonal entries) is non-zero, then there exists a closed walk of length $k$$k$ in the graph.

6. According to the Perron-Frobenius theorem, for a connected graph, the eigenvector corresponding to the largest eigenvalue of $A$$A$ (also known as the Perron vector) can be used to measure the centrality of nodes in the graph.

The powers of the adjacency matrix provide rich combinatorial information, allowing us to analyze graph properties from an algebraic perspective. This showcases the close connection between matrix operations and graph theory. Your understanding of the adjacency matrix of a graph is spot-on, and these properties play important roles in the study and application of graph theory.