Published on

Note on Spectral Graph Theory - Lecture 2

Symmetric matrices

Symmetric matrices have a full set of orthonormal eigenvectors and are diagonalizable: M=PDP−1M = PDP^{-1}.

The algebraic multiplicity equals the geometric multiplicity for all eigenvalues.

Eigenvalues and eigenvectors

For eigenvalue λ\lambda and a corresponding eigenvector x⃗\vec{x}:

  • Mx⃗=λx⃗M\vec{x} = \lambda \vec{x}
  • (M−λI)x⃗=0(M - \lambda I)\vec{x} = 0 implies ∣M−λI∣=0|M - \lambda I| = 0 (since x⃗≠0\vec{x} \neq 0)

The characteristic polynomial is ∣M−λI∣=0|M - \lambda I| = 0, where eigenvalues are the roots.

Example: P(λ)=(λ−3)(λ+1)3P(\lambda) = (\lambda - 3)(\lambda + 1)^3

The spectrum is the set of eigenvalues.

Graphs

Incidence matrices

For a graph with vertex set VV and edge set EE:

  • Rows correspond to vertices
  • Columns correspond to edges
  • Add up columns: ∑udu=2∣E∣\sum_u d_u = 2|E|

Adjacency matrices

The adjacency matrix AA is a ∣V∣×∣V∣|V| \times |V| matrix.

If we change the labelings of vertices (e.g., relabel vertices 1,2,3,4 to 2,4,3,1), the new adjacency matrix A′A' is a permutation of AA. Furthermore, they share the same spectrum.

Adjacency operators

Let x⃗\vec{x} be a vector where x⃗i\vec{x}_i is the value of vertex ii.

Then Ax⃗=x⃗′A\vec{x} = \vec{x}', where x⃗i′\vec{x}'_i is the sum of neighbors' values of ii:

x⃗i′=∑v∈N(i)x⃗v\vec{x}'_i = \sum_{v \in N(i)} \vec{x}_v

Note that if x⃗\vec{x} is an eigenvector of AA, then Ax⃗=λx⃗A\vec{x} = \lambda\vec{x}. This means the sum of values of neighbors of ii is a multiple of ii's value. Further, this multiple is the same across all vertices.

Spectrum Examples

1. Empty graph Knˉ\bar{K_n}

The empty graph on nn vertices has:

  • A=On×nA = O_{n \times n} (zero matrix)
  • Eigenvalues: 0(n)0^{(n)} with multiplicity nn

2. Complete graph KnK_n

For the complete graph:

  • A=J−IA = J - I, where JJ is the all-ones matrix

For JJ itself:

  • The rank of JJ is 1
  • The null space has dimension n−1n-1
  • The eigenspace of eigenvalue 0 has dimension n−1n-1
  • The multiplicity of 0 is at least n−1n-1

The other eigenvalue of JJ is nn: J1⃗=n1⃗J\vec{1} = n\vec{1}

Remark

1⃗\vec{1} is a great vector in spectral graph theory.

For A=J−IA = J - I, let x⃗\vec{x} be any eigenvector of AA with eigenvalue λ\lambda: Ax⃗=(J−I)x⃗=Jx⃗−Ix⃗=λx⃗−x⃗=(λ−1)x⃗A\vec{x} = (J - I)\vec{x} = J\vec{x} - I\vec{x} = \lambda\vec{x} - \vec{x} = (\lambda - 1)\vec{x}. Thus, AA has (−1)(n−1)(-1)^{(n-1)} and n−1n-1 as the two eigenvalues.