10 Spectral Graph Theory

Basic Matrices

Recall that

Define Laplacian matrix $L=D-A$.

Link to original

Definition

Let $Q=D+A$ be the signless Laplacian matrix.

Let $\mathcal{L}=I-D^{-1/2}A{D}^{-1/2}$ be the normalized Laplacian.

Remark. For a graph with adjacency matrix $A$, its characteristic polynomial is $\det (xI-A)$. Since $A$, $L$, and $Q$ are real symmetric matrices, each has $n$ real eigenvalues and admits an orthonormal basis of eigenvectors. The eigenvalues of $A$ and $L$ are called the adjacency spectrum and the Laplacian spectrum, respectively.

Examples of Spectral

Complete (Bipartite) Graphs

Example

The adjacency matrix of $K_n$ is $A=J-I$, whose spectrum is $(n-1{)}^1$, $(-1{)}^{n-1}$.

Then $L=D-A=nI-J$, whose spectrum is $0^1$, $n^{n-1}$.

Example

The adjacency matrix of $K_{m,n}$ is $A=\left[\begin{array}{cc}0& J\\ J^T& 0\end{array}\right]$, whose spectrum is $(\sqrt{mn}{)}^1$, $(-\sqrt{mn}{)}^1$, $0^{m+n-2}$.

Then $L=\left[\begin{array}{cc}n{I}_m& -J\\ -J^T& m{I}_n\end{array}\right]$, whose spectrum is $0^1$, $(m+n{)}^1$, $n^{m-1}$, $m^{n-1}$.

\begin{proof} Let $(x,y)$ be an eigenvector of $A$. Then $\lambda (x,y)=A(x,y)=(Jy,J^{T}x)$. Let $s=\sum y$ and $t=\sum x$, then $Jy=s\vec{1}$ and $J^{T}x=t\vec{1}$. If $\lambda \ne 0$, then $x=a\vec{1}$ and $y=b\vec{1}$, which deduces that $\lambda a=nb$, $\lambda b=ma$ and $\lambda =\pm \sqrt{mn}$. If $\lambda =0$, then $s=t=0$ and there are $m-1+n-1$ eigenvectors of eigenvalue $0$.

The eigenvalues of $L$ are easy to check. Remark that $\vec{1}$ and $(n\cdots ,n,-m,\cdots ,-m)$ are two eigenvectors, whose eigenvalues are $0$ and $(m+n)$, respectively. Also $(x,0)$ and $(0,y)$ are eigenvectors with $\sum x_i=\sum y_j=0$.
Now we finish the proof. \end{proof}

Cycles and Paths

Example

Let $D_n$ be the directed cycle on $n$ vertices. Then

$$A(D_5)=\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0\end{array}\right].$$

Note that $A(D_n)$ has $n$ eigenvectors $(1,\xi ,\cdots ,{\xi }^{n-1})$ with $\xi =e^{2\pi ij/n}$.

Example

Let $C_n$ be the undirected cycle on $n$ vertices, then $A(C_n)=A(D_n)+A(D_n{)}^T$. Note that $A(C_n)$ and $A(D_n)$ have the same eigenvectors, and eigenvalues of $A(C_n)$ are $\xi +{\xi }^{-1}=2\cos (2\pi j/n)$.

Example

Let $P_n$ be a path with $n$ vertices. Then $A(P_n)$ has the eigenvalues $2\cos (2\pi j/(2n+2))$, where $j\in [n]$.

\begin{proof} First, we look at the eigenvectors of $C_{2n+2}$. Define $v(\xi )=(1,\xi ,\cdots ,{\xi }^{2n+1})$, then $v(\xi )$ and $v({\xi }^{-1})$ both have eigenvalues $\xi +{\xi }^{-1}=2\cos (2\pi j/(2n+2)):=\lambda$. It deduces that

$$v(\xi )-v({\xi }^{-1})=\left[\begin{array}{c}0\\ \xi -{\xi }^{-1}\\ ⋮\\ {\xi }^{n+1}-{\xi }^{-n-1}=0\\ ⋮\\ {\xi }^{2n+1}-{\xi }^{-2n-1}\end{array}\right]=\left[\begin{array}{c}0\\ v\\ 0\\ w\end{array}\right]$$

is an eigenvector with eigenvalue $\lambda$. Assume that $v=(v_1,\cdots ,v_n)$ and $w=(w_1,\cdots ,w_n)$, then $v_1+w_n=v_n+w_1=0$. It follows that

$$A(C_{2n+2})(v(\xi )-v({\xi }^{-1}))=\left[\begin{array}{c}{v}_1+w_n\\ A(P_n)v\\ v_n+w_1\\ A(P_n)w\end{array}\right]=\lambda (v(\xi )-v({\xi }^{-1})),$$

and so $\lambda$ is an eigenvalue of $P_n$. \end{proof}

Remark. As an example, the following matrix is the adjacent matrix of $C_6$.

Bipartite Graphs

Proposition

Let $A$ be an adjacency matrix of a bipartite graph. Then $A=\left[\begin{array}{cc}0& B\\ B^T& 0\end{array}\right]$. If $\lambda$ is an eigenvalue with eigenvector $\left[\begin{array}{c}{u}_1\\ u_2\end{array}\right]$, then $-\lambda$ is an eigenvalue with eigenvector $\left[\begin{array}{c}{u}_1\\ -u_2\end{array}\right]$.

\begin{proof} Easy. \end{proof}

Graph Products and Cayley Graphs

There are more examples…

• $\Gamma ,\Delta$ graphs with vertex sets $V$ and $W$. Then $\Gamma \square \Delta$ has vertex set $V\times W$ and $(v,w)\sim (v^{\prime },w^{\prime })$ when $v=v^{\prime },w\sim w^{\prime }$ or $v\sim v^{\prime },w=w^{\prime }$. ^rg4dj1
  • Define $Q_0$ is a point, $Q_1=K_2$, $Q_2=Q_1\square Q_1$, $Q_{d+1}=Q_1\square Q_d$.
  • Notice that $A(\Gamma \square \Delta )=A(\Gamma )\otimes I+I\otimes A(\Delta )$
  • It deduces that
    • spectrum of $Q_1=1,-1$
    • spectrum of $Q_2=2,0^2,-2$
    • spectrum of $Q_3=3,1^3,-1^3,-3^1$
• Kronecker product and bipartite doubles $\Gamma ,\Delta$ graphs with vertex sets $V,W$.
  • Kronecker product $\Gamma \otimes \Delta$ has vertex set $V\times W$, $(v,w)\sim (v^{\prime },w^{\prime })$ when $v\sim v^{\prime }$, $w\sim w^{\prime }$.
  • $A(\Gamma \otimes \Delta )=A(\Gamma )\otimes A(\Delta )$, so it is easy to obtain eigenvalues.
  • Definition of bipartite double: $\Gamma \otimes K_2$, spectrum: $\lambda \to \lambda ,-\lambda$
  • Some people write $\Gamma \times \Delta$ for $\Gamma \otimes \Delta$ or for $\Gamma \square \Delta$.
• Strong product
  • $\Gamma ⊠\Delta$ has vertex set $V\times W$, distinct $(v,w)\sim (v^{\prime },w^{\prime })$ iff $v=v^{\prime }$ or $v\sim v^{\prime }$, and $w=w^{\prime }$ or $w\sim w^{\prime }$
  • $A(\Gamma ⊠\Delta )=(A(\Gamma )+I)\otimes (A(\Delta )+I)-I$, spectrum: $\lambda ,\mu \to (\lambda +1)(\mu +1)-1$
• Cayley graph
  • $G$ abelian group, $S\subseteq G$.
  • A Cayley graph on $G$ with difference set $S$ is the (directed) graph $\Gamma$ with $V(\Gamma )=G$ and $E(\Gamma )=\{(x,y):y-x\in S\}$. This graph is undirected iff $-S=S$
  • Note that $\Gamma$ is regular with degree $|S|$.
  • Let $\chi$ be a character of $G$.
  • Then ${\sum }_{y\sim x}\chi (y)=({\sum }_{s\in S}\chi (s))\chi (x)$, so $(\chi (x){)}_{x\in G}$ is a eigenvector of $A(\Gamma )$ with eigenvalue $\chi (S):={\sum }_{s\in S}\chi (s)$.
  • A group $G$ of order $n$ has $n$ orthogonal characters, so we have found all the eigenvalues.
  • For example, when $G={\mathbb{Z}}_5$ and $S=\{1\}$, $\mathrm{Cay}(G,S)$ has spectrum $1,\xi ,\cdots ,{\xi }^4$, where $\xi$ is a primitive $5$th root of unity.

Interlacing & Projections onto Eigenspaces

Let $A\in {\mathbb{R}}^{n\times n}$ with $A=A^T$. Then $A$ has a basis of orthonormal eigenvectors $u_1,\cdots ,u_n$, with eigenvalues ${\lambda }_1⩾\cdots ⩾{\lambda }_n$, respectively. If we work with more than one matrix ${\lambda }_i(A)={\lambda }_i$, $u_i(A)=u_i$. Denote the eigenspace of $\lambda$ by $V(\lambda )$. If $A$ has $m+1$ distinct eigenvalues ${\mu }_0,\cdots ,{\mu }_m$, ${\mu }_j>{\mu }_{j+1}$, then write $V_j=V_j({\mu }_j)$.

(This is not standard in general spectra graph but it will make everything more uniform for SRG, DRGs, association schemes. )

Define $E_j$ as the orthogonal projection (a matrix, not a map) onto $V_j$, that is, $E_j={\sum }_{u_i:{\lambda }_i={\mu }_j}{u}_i{u}_i^T$.

property of Rayleigh quotient

The Rayleigh quotient of $u$ w.r.t. $A$ is $u^{T}Au/u^{T}u$.

If $u={\sum }_{i=1}^n{\alpha }_i{u}_i$, then $u^{T}u={\sum }_{i=1}^n{\alpha }_i^2$ and

$$u^{T}Au=(\sum _{i=1}^n{\alpha }_i{u}_i^T)(\sum _{i=1}^n{\lambda }_i{u}_i{u}_i^T)\sum _{i=1}^n{\alpha }_i{u}_i=\sum _{i=1}^n{\alpha }_i^2{\lambda }_i.$$

Thus,

• $u^{T}Au/u^{T}u⩾{\lambda }_i$ if $u\in ⟨u_1,\cdots ,u_i⟩\setminus \{0\}$, and
• $u^{T}Au/u^{T}u⩽{\lambda }_i$ if $u\in {⟨u_1,\cdots ,u_{i-1}⟩}^{\perp }\setminus \{0\}$.

In both cases equality implies that $Au={\lambda }_{i}u$.

Definition

Let $A\in {\mathbb{R}}^{n\times n}$ and $B\in {\mathbb{R}}^{m\times m}$, both symmetric, $n⩾m$. If for all $i=1,\cdots ,m$,

$${\lambda }_i(A)⩾{\lambda }_i(B)⩾{\lambda }_{n-m+i}(A),$$

then we say that the eigenvalues of $B$ interlace the eigenvalues of $A$.

If there exists an integer $k$, $0⩽k⩽m$ such that

• ${\lambda }_i(A)={\lambda }_i(B)$ for $i=1,\cdots ,k$, and
• ${\lambda }_{n-m+i}(A)={\lambda }_i(B)$ for $i=k+1,\cdots ,m$,

then the interlacing is tight.

Cauchy interlacing

Let $S\in {\mathbb{R}}^{n\times m}$ such that $S^{T}S=I_m$. Let $A\in {\mathbb{R}}^{n\times m}$ with $A^T=A$. Put $B=S^{T}AS$. Then

• the eigenvalues of $B$ interlace the eigenvalues of $A$;
• if ${\lambda }_i(B)\in \{{\lambda }_i(A),{\lambda }_{n-m+i}(A)\}$, then there exists an eigenvector $v$ of $B$ for ${\lambda }_i(B)$ such that $Sv$ is an eigenvector of $A$ with eigenvalue ${\lambda }_i(B)$;
• if for some $\ell \in \{1,\cdots ,m\}$, ${\lambda }_i(A)={\lambda }_i(B)$ for all $i=1,\cdots ,\ell$, then $S{u}_i(B)$ is an eigenvector of $A$ for ${\lambda }_i(A)$ for all $i=1,\cdots ,\ell$.
• if the interlacing is tight, then $SB=AS$.

\begin{proof} i) Take $v_i\in ⟨u_1(B),\cdots ,u_i(B)⟩\cap {⟨S^T{u}_i(A),\cdots ,S{u}_{i-1}(A)⟩}^{\perp }$, $v_i\ne 0$.
Then $S{v}_i\in {⟨u_1(A),\cdots ,u_{i-1}(A)⟩}^{\perp }$, and so

$${\lambda }_i(A)⩾\frac{v_i^T{S}^{T}AS{v}_i}{v_i^T{S}^{T}S{v}_i}=\frac{v_i^{T}B{v}_i}{v_i^T{v}_i}⩾{\lambda }_i(B).$$

Also $-{\lambda }_i(B)={\lambda }_{m-i+1}(-B)⩽{\lambda }_{m-i+1}(-A)=-{\lambda }_{n-m+1}(A)$.

ii) In case of equality, $v_i$ and $S{v}_i$ must be eigenvectors of $B$ and $A$, respectively.

iii) and iv) are similar. \end{proof}

Corollary

If $B$ is a principal submatrix of $A$, then the eigenvalues of $B$ interlace the eigenvalues of $A$.

\begin{proof} Take $S=(I_m,O{)}^T$. \end{proof}

Quotient Matrix

Definition

If we partition $A\in {\mathbb{R}}^{n\times n}$ with $A^T=A$ as

$$A=\left(\begin{array}{ccc}{A}_{11}& \cdots & A_{1m}\\ ⋮& & ⋮\\ A_{m1}& \cdots & A_{mm}\end{array}\right),$$

then the matrix $B=(b_{ij})$ with $b_{ij}=$ average row sum of $A_{ij}$, i.e. $b_{ij}=\frac{{\sum }_k{\sum }_{\ell }(A_{ij}{)}_{k\ell }}{\#\text{rows of }{A}_{ij}}$, is called a quotient matrix of $A$.

We call the partition equitable if $A_{ij}\vec{j}=b_{ij}\vec{j}$ for all $i,j$, where $\vec{j}=(1,\cdots ,1{)}^T$.

Remark. In other words, perfect coloring = equitable partition. Let index $X=X_1\cup X_2$, blablabla, $X_1$ is regular set.

Corollary

Let $B$ be a quotient matrix of $A$. Then

• the eigenvalues of $B$ interlace the eigenvalues of $A$;
• if the interlacing is tight, then the partition is equitable.

Remark. If graph $\Gamma$ is $d$-regular, then ${\lambda }_1=d$. If $\Gamma$ is connected, then $\dim (V({\lambda }_1))=1$.

Spectral Bound

Let $\Gamma =(X,\sim )$ be a $d$-regular graph on $n$ vertices, $d⩾1$, connected.

Ratio Bound/Delsarte-Hoffman bound

Write $\lambda ={\lambda }_n$. Let $Y\subseteq X$ be a coclique. Then

$$|Y|⩽\frac{n}{1-\frac{d}{\lambda }}=\frac{-\lambda n}{d-\lambda }.$$

If equality holds, then the characteristic vector $\chi$ of $Y$ satisfies $\chi \in ⟨\vec{j}⟩+V(\lambda )$, where

$$\chi (x)=\{\begin{array}{ll}1& \text{if }x\in Y,\\ 0& \text{otherwise.}\end{array}$$

In particular, $Y\cup (X\setminus Y)$ is an equitable bipartition of the form $\left[\begin{array}{cc}0& d\\ -\lambda & d+\lambda \end{array}\right]$.

\begin{proof} 没看懂 Write $A={\sum }_{j=0}^m{\mu }_j{E}_j$ and $x={\sum }_{j=0}^m{E}_j\chi$. Note that ${\mu }_0=d$ with multiplicity $1$ and eigenvector $j$, so $E_0=\frac{1}{n}J$. Put $y=|Y|$. Also $E_0\chi =(\frac{1}{n}J)\chi =\frac{1}{n}|Y|j=\frac{y}{n}j$. Then

$$\begin{array}{rl}0& =x^{T}Ax=x^T(\frac{d}{n}J+\sum _{j=1}^m{\mu }_j{E}_j)\\ & =\frac{y}{n}({\chi }^{T}j)+\sum _{j=1}^n{\mu }_j{\chi }^T{E}_j\chi \\ & ⩾\frac{y^2}{n}d+\lambda \sum _{j=1}^m{\chi }^T{E}_j\chi .\end{array}$$

A $\chi$ is a $0$-$1$-vector, $y={\chi }^T\chi =y^2/n+{\sum }_{j=1}^m{\chi }^T{E}_j\chi$.

Thus $0⩾d{y}^2/n+\lambda (y-y^2/n)$.

Rearranging yields $y⩽\frac{-\lambda n}{d-\lambda }$. Equality holds if $\chi \in ⟨j⟩+V_m$.

Now let $\varphi$ be the characteristic vector of $\{x\}$ for $x$ vertex.

\end{proof}

Remark. We can replace $A$ by any matrix that satisfies these conditions.

• $(A{)}_{xy}⩽0$ if $x\sim y$ or $x=y$
• $Aj=dj$ and $A=A^T$

Here is another proof.

\begin{proof} Write $X=Y\cup (X\setminus Y)$. Then w.r.t. this partition, we obtain the quotient matrix

$$B=\left(\begin{array}{cc}0& d\\ \frac{dy}{n-y}& d-\frac{dy}{n-y}\end{array}\right).$$

Eigenvalues of $B$ are $d$ and $-\frac{dy}{n-y}$. By interlacing, we have $\lambda ⩽\frac{dy}{n-y}$ and so $y⩽\frac{-\lambda n}{d-\lambda }$. \end{proof}

Lemma

Let $\alpha (\Gamma )$ be the independence number of $\Gamma$, and let $\chi (\Gamma )$ be the chromatic number of $\Gamma$. Then $\chi (\Gamma )\alpha (\Gamma )⩾n$, where $n$ is the order of $\Gamma$.

\begin{proof} Each color class in a coloring is an independent set. \end{proof}

Hoffman/Ratio bound

$\alpha (\Gamma )⩽\frac{-\lambda }{d-\lambda }n$, which deduces that $\chi (\Gamma )⩾1-d/\lambda$, where $\lambda$ is the minimal eigenvalue.

Inertia bound/Cvetkovie bound

We have $\alpha (\Gamma )⩽n-n_{-}:=|\{i:{\lambda }_i⩾0\}|$ and $\alpha (\Gamma )⩽n-n_{+}:=|\{i:{\lambda }_i⩽0\}|$.

\begin{proof} The adjacent matrix $A$ has an all $0$ principal submatrix $B$ of order $\alpha (\Gamma )$, that is, $A=\left(\begin{array}{cc}0& \ast \\ \ast & \ast \end{array}\right)$, where the $0$ matrix has $|Y|=\alpha (\Gamma )$ lines. All eigenvalues of $B$ are $0$. By ^ve7qqg, the eigenvalues of $B$ interlace the eigenvalues of $A$, so the claim follows. \end{proof}

Remark. For graphs with $⩽10$ vertices, always tight for some such $A$.

Question. (Godsil) is this bound always tight?

Rooney(?): Counterexample for $n=16$ or $n=17$.

Theorem

Let $\Gamma$ be $d$-regular, $Y\subseteq X$, $y=|Y|$, then

$$\frac{{\lambda }_n}{n}y(n-y)⩽E(Y,Y)-\frac{d}{n}{y}^2⩽\frac{{\lambda }_2}{n}y(n-y),$$

where $E(Y,Y)$ is the actual number of edges in $Y$ and $\frac{d}{n}{y}^2$ is the expected number of edges in $Y$.

\begin{proof}

\end{proof}

Expander-Mixing

Let $\Gamma =(X,\sim )$ be a $d$-regular graph, $Y,Z\subseteq X$, $\lambda =\max ({\lambda }_2,-{\lambda }_n)$. Then

$$|E(Y,Z)-\frac{d|Y||Z|}{n}|⩽\lambda \sqrt{|Y||Z|(1-\frac{|Y|}{n})(1-\frac{|Z|}{n})}⩽\lambda \sqrt{|Y||Z|}.$$

Remark. If $\Gamma$ is bipartite, then $\lambda =d$, by ^vnqcpz. We get $|E(Y,Z)-\frac{d}{n}|Y||Z||⩽d\sqrt{|Y||Z|}$, which is useless.

So we have the following lemma.

Bipartite Expander-Mixing

Let $\Gamma$ be a $d_1,d_2$-biregular bipartite graph on $x_1+x_2$ vertices with parts $X_1$ and $X_2$. Let $Y_i\subseteq X_i$ and $y_i=|Y_i|$. Then

$$|\sqrt{x_1{x}_2}E(Y_1,Y_2)-\sqrt{d_1{d}_2}{y}_1{y}_2|⩽{\lambda }_2\sqrt{y_1{y}_2(x_1-y_1)(x_2-y_2)}.$$

\begin{proof} Using the partition $Y_1\cup (X_1\setminus Y_1)\cup Y_2\cup (X_2\setminus Y_2)$, obtain the quotient matrix

$$B=\left(\begin{array}{cccc}0& 0& E/y_1& d_1-E/y_1\\ 0& 0& \frac{y_2{d}_2-E}{x_1-y_1}& d_1-\frac{y_2{d}_2-E}{x_1-y_1}\\ E/y_2& d_2-E/y_2& 0& 0\\ \frac{y_1{d}_1-E}{x_2-y_2}& d_2-\frac{y_1{d}_1-E}{x_2-y_2}& 0& 0\end{array}\right).$$

Trace of $B$ and determinant of $B$ are easy to calculate. Then the eigenvalues of $B$ are $\pm \sqrt{d_1{d}_2}$ and $\pm \mu$ for some $\mu$. \end{proof}