Spectrum and adjacency algebra of graph

Spectrum

Definition

Let $X=(V,E)$ be a graph (directed or undirected, simple or with loops), and let $\mathbf{A}$ be its adjacency matrix. We call $f_{\mathbf{A}}(\lambda )$ the characteristic polynomial of graph $X$ (and sometimes write it as $f_X(\lambda )$), and we call all the eigenvalues $\left\{{\lambda }_1,\dots ,{\lambda }_n\right\}$ of $f(\lambda )$ the spectrum of graph $X$.

One can easily notice that, for a $k$-regular graph $X=(V,E)$, the followings hold:

• $k$ is an eigenvalue of $X$;
• If $X$ is connected, the multiplicity of $k$ is 1;
• For any eigenvalue $\lambda$ of $X$, we have $|\lambda |\le k$.

Proposition

Let $f_X(\lambda )={\lambda }^n+c_1{\lambda }^{n-1}+c_2{\lambda }^{n-2}+\cdots +c_n$ be the characteristic polynomial of a simple undirected graph $X$. Then,

• $c_1=0$;
• $-c_2=\Vert X\Vert$;
• $-c_3$ is twice the number of $C_3$-type subgraphs in $X$.

\begin{proof} See here. \end{proof}

Proposition

Let $l$ be a positive integer. Then the $(i,j)$-th entry of ${\mathbf{A}}^l$ is equal to the number of paths of length $l$ from vertex $v_i$ to vertex $v_j$.

\begin{proof} We use induction on $l$.

When $l=1$, the conclusion follows directly from the definition of $\mathbf{A}$. When $l>1$, because

$${\left({\mathbf{A}}^{l+1}\right)}_{ij}=\sum _{k=1}^n{\left({\mathbf{A}}^l\right)}_{ik}{a}_{kj}$$

by the induction hypothesis, we obtain the conclusion. \end{proof}

Adjacency Algebra

Definition

Let $\mathbf{A}$ be the adjacency matrix of a graph $X$. Let

$$\mathcal{A}(X)=\{f(\mathbf{A})\mid f(\lambda )\in \mathbb{C}[\lambda ]\}$$

Then $\mathcal{A}(X)$ is a subalgebra of the full matrix algebra $M_n(\mathbb{C})$, called the adjacency algebra of graph $X$ (with respect to its adjacency matrix $\mathbf{A}$).

Note that $\dim \mathcal{A}(X)$ is equal to the degree of the minimal polynomial of $\mathbf{A}$, and is less than $|X|$ (number of points of $X$). Furthermore, we have the following proposition.

Proposition

Let $X$ be a connected graph, and let $d$ be the diameter of $X$. Then $\dim A(X)\ge d+1$.

\begin{proof} We only need to prove that $\mathbf{I},\mathbf{A},\dots ,{\mathbf{A}}^d$ are linearly independent in $\mathcal{A}(X)$. Since $X$ is connected and has diameter $d$, we must have $d\le n-1$. There also exist two vertices $x,y$ such that $d(x,y)=d$, and there is a path $W$ of length $d$ from $x$ to $y$. Let $W=$ $v_1{v}_2\dots v_{d+1}$ be such a path, where $v_1=x,v_{d+1}=y$. Then, for $i=2,3,\dots ,d+1$, there exists a path of length $i-1$ from $v_1$ to $v_i$, but there is no path of a shorter length. This shows that

$${\left({\mathbf{A}}^{i-1}\right)}_{1i}\ne 0,\text{ but }{\left({\mathbf{A}}^j\right)}_{1i}=0\text{ for }j<i-1$$

Thus, ${\mathbf{A}}^{i-1}$ is linearly independent of $\left\{\mathbf{I},\mathbf{A},\dots ,{\mathbf{A}}^{i-2}\right\}$. In this way, by induction on $i$, we can prove the linear independence of $\left\{\mathbf{I},\mathbf{A},\dots ,{\mathbf{A}}^d\right\}$. \end{proof}

Hoffman

A graph $X$ is regular and connected if and only if $\mathbf{J}\in A(X)$, where $\mathbf{J}$ is the all-ones matrix.

\begin{proof} "←" If $\mathbf{J}\in A(X)$, then $\mathbf{J}$ is a polynomial of the adjacency matrix $\mathbf{A}$. Thus, $\mathbf{JA}=\mathbf{AJ}$. The $(i,j)$ -th entry of the left side is the degree of vertex $v_j$, which is $k_j$, while the $(i,j)$-th entry of the right side is the degree of vertex $v_i$, which is $k_i$. Thus we have $k_i=k_j$ for all $i,j$. This means $X$ is a regular graph.

Furthermore, if $X$ is disconnected, there exist two vertices $v_i,v_j$ with $i\ne j$ that are not connected by any path. Of course, they are not adjacent either. Therefore, by ^qo73tm, for any positive integer $l$, the $(i,j)$-th entry of ${\mathbf{A}}^l$ is zero. As a result, the $(i,j)$-th entry of any polynomial $f(\mathbf{A})$ of $\mathbf{A}$ is also zero, which contradicts $\mathbf{J}\in A(X)$.

"→" Let $X$ be a $k$-regular connected graph. Recall that $k$ is an eigenvalue of $X$. Let’s assume the minimal polynomial of $\mathbf{A}$ is

$$g(\lambda )=(\lambda -k)q(\lambda ).$$

Then we have $\mathbf{A}q(\mathbf{A})=kq(\mathbf{A})$. This shows that all columns of $q(\mathbf{A})$ are eigenvectors of $\mathbf{A}$ corresponding to the eigenvalue $k$, or are zero vectors. However, since the multiplicity of $k$ is one, all columns are multiples of the vector $(1,1,\dots ,1{)}^T$. Also, since $q(\mathbf{A})\ne 0$ and $q(\mathbf{A})$ is symmetric, $q(\mathbf{A})$ must be a non-zero multiple of $\mathbf{J}$. Therefore, $\mathbf{J}\in A(X)$. \end{proof}