Note on Spectral Graph Theory - Lecture 3

Spectrum of $K_{m,n}$

Consider the complete bipartite graph $K_{m,n}$ with adjacency matrix:

$$A = \begin{pmatrix} 0 & J \\ J^T & 0 \end{pmatrix}$$

where $J$ is the $m \times n$ all-ones matrix.

Eigenvalue 0

Consider a simpler case where $m = 2$, with two vertices $v$ and $w$ on one side. An easy eigenvector with eigenvalue 0 is:

$$\vec{v} = \begin{pmatrix} 1 \\ -1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$

where the values at $v$ and $w$ are $1$ and $-1$, respectively. This is more general than just $K_{2,n}$. In particular, whenever we have 2 vertices with the same as of neighbors in a graph, we immediately have the above eigenvector with eigenvalue 0.

Furthermore, it is easy to see that, if $v$ and $w$ are adjacent, then the eigenvalue is $-1$.

It follows that, for $K_{m,n}$, we have $(m-1) + (n-1)$ linearly independent eigenvectors of eigenvalue 0.

Additional eigenvalues

To find the remaining 2 eigenvalues, consider a vertex $\vec{x}$:

$$\vec{x} = \begin{pmatrix} a \\ \vdots \\ a \\ b \\ \vdots \\ b \end{pmatrix}, \quad A\vec{x} = \begin{pmatrix} nb \\ \vdots \\ nb \\ ma \\ \vdots \\ ma \end{pmatrix}$$

where the values of all vertices in the first partition are reals $a > 0$'s, and those of in the second partition are reals $b > 0$'s. This gives us $\lambda = \frac{nb}{a} = \frac{ma}{b}$, which implies $ma^2 = nb^2$. We can scale, thus set $a = 1$, and we have $b = \pm\sqrt{\frac{m}{n}}$, $\lambda = \pm\sqrt{mn}$.

Spectrum of Directed Cycles

Consider the adjacency matrix $A$ of a directed cycle:

$$A = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ 1 & 0 & 0 & \cdots & 0 \end{pmatrix}$$

$n$-th roots of unity are eigenvalues

An $n$-th root of unity is a complex number $z$ such that $z^n = 1$. In general, $z$ has the form:

$$z = \exp\left(\frac{2\pi i k}{n}\right) = \cos\left(\frac{2\pi k}{n}\right) + i\sin\left(\frac{2\pi k}{n}\right)$$

for $k = 0, 1, \ldots, n-1$.

Let $\omega$ be any $n$-th root of unity. Consider the vector:

$$\vec{v}_{\omega} = \begin{pmatrix} 1 \\ \omega \\ \omega^2 \\ \vdots \\ \omega^{n-1} \end{pmatrix}$$

Then:

$$A\vec{v}_{\omega} = \begin{pmatrix} \omega \\ \omega^2 \\ \omega^3 \\ \vdots \\ 1 \end{pmatrix} = \omega \cdot \vec{v}_{\omega}$$

Thus, $A$ has $n$ eigenvalues, where each eigenvalue is an $n$-th root of unity.

Circulant Matrices

A circulant matrix has the form:

$$C = \begin{pmatrix} c_0 & c_1 & \cdots & c_{n-1} \\ c_{n-1} & c_0 & \cdots & c_{n-2} \\ \vdots & \vdots & \ddots & \vdots \\ c_1 & c_2 & \cdots & c_0 \end{pmatrix} = c_0A^0 + c_1A^1 + \cdots + c_{n-1}A^{n-1}$$

where $A$ is the adjacency matrix of a directed $n$-cycle, and $c_0, \ldots, c_{n-1} \in \mathbb{R}$.

For any $n$-th root of unity $\omega$, consider the same vector $\vec{v}_{\omega}$ defined above, we have:

$$C\vec{v} = \lambda\vec{v} \quad \text{where } \lambda = c_0 + c_1\omega + c_2\omega^2 + \cdots + c_{n-1}\omega^{n-1}$$

Thus, a circulant matrix has $n$ eigenvalues.

Spectrum of Undirected Cycles

Now consider an undirected cycle $C_n$. Its adjacency matrix has the form:

$$\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & 0 & 0 & \cdots & 0 & 1 \end{pmatrix}$$

which is circulant with $\lambda = \omega + \omega^{n-1}$, where $\omega$ is any $n$-th root of unity.

Proof that $\lambda$ is real

$$\lambda = \omega + \omega^{n-1} = e^{\frac{2\pi ik}{n}} + e^{\frac{(n-1)2\pi ik}{n}} \quad (k = 0, 1, \ldots, n-1)$$ $$= e^{\frac{2\pi ik}{n}} + e^{\frac{2\pi ik}{n}} \cdot e^{-\frac{2\pi ik}{n}} = e^{\frac{2\pi ik}{n}} + e^{-\frac{2\pi ik}{n}}$$ $$= \frac{e^{i\theta} + e^{-i\theta}}{2} \cdot 2 = 2\cos\left(\frac{2\pi k}{n}\right)$$

where $\theta = \frac{2\pi k}{n}$.

Matrix Powers and Walks

Let $A$ be the adjacency matrix of an undirected graph.

1. $(A^k)_{uv} =$ number of walks of length $k$ from $u$ to $v$

2. $\text{Trace}(A) = 0 = \lambda_1 + \cdots + \lambda_n$

3. $\text{Trace}(A^2) = 2|E| = \lambda_1^2 + \lambda_2^2 + \cdots + \lambda_n^2$ (each triangle contributes to the trace)

4. $\text{Trace}(A^3) = 6 \times \text{number of triangles} = \lambda_1^3 + \lambda_2^3 + \cdots + \lambda_n^3$.

   To see this, note that each triangle is counted exactly twice by each of the vertex on this triangle.

5. $A_{ii}^2 =$ degree of vertex $i$

6. $A_{ij}^2 =$ number of common neighbors of vertices $i$ and $j$