Setting - Spectral Graph Theory - Cambridge III notes

Ω

a set (finite),

f : Ω \to ℂ

l^{2} (Ω) : = {f : Ω \to ℂ | \sum_{x} | f (x) |^{2} < \infty}

This generalises subsets: given

S \subseteq Ω

, can consider

𝟙_{S} : Ω \to ℂ

(where

x \mapsto 1

for

x \in S

, and

x \mapsto 0

otherwise).

When

S

contains only a single element, we may use the shorthand

𝟙_{x} = 𝟙_{{x}}

l^{2} (Ω)

is a

ℂ

-vector space, equipped with the inner product

⟨ ∙, ∙ ⟩ : l^{2} (Ω) \times l^{2} (Ω) \to ℂ

defined by

Matrix over

Ω

M : Ω \times Ω \to ℂ

M (x, y) = M_{x, y}

is the

x, y

entry.

M

acts on

l^{2} (Ω)

: for

f \in l^{2} (Ω)

M f \in l^{2} (Ω)

is given by

(M f) (x) = \sum_{y} M (x, y) f (y)

M (α f + β g) = α M f + β M g

(

M

is a linear map).

so define

(M N) (x, y) = \sum_{z} M (x, z) N (z, y)

, so that the formula

(M N f) (x) = \sum_{y} (M N) (x, y) f (y)

holds.

Eigenthings: for

M : Ω \times Ω \to ℂ

, we say that

λ \in ℂ

is an eigenvalue with eigenfunction

φ \neq 0

M φ = λ φ

Definition 1.1 (Hermitian). $M$ is Hermitian if $M = M^{H}$ , where $M^{H} (x, y) = \bar{M (y, x)}$ .

If $M$ is Hermitian, then $⟨ M f, g ⟩ = ⟨ f, M g ⟩$ .

Theorem 1.2 (Spectral theorem for Hermitian matrices). Assuming that:

$Ω$ finite
$M : Ω \times Ω \to ℂ$ Hermitian
$| Ω | = n$

Then there exist

λ_{1}, \dots, λ_{n} \in ℝ

and

φ_{1}, \dots, φ) n \in l^{2} (Ω)

non-zero such that

(1)
$M φ_{i} = λ_{i} φ_{i}$
(2)
$⟨ φ_{i}, φ_{j} ⟩ 𝟙_{i = j}$
(3)
$M = \sum_{i = 1}^{n} λ φ_{i} φ_{i}^{H}$
(4)
there exists $U$ orthogonal such that $U M U^{H} = diag (λ_{i})$
(5)
if $M$ is real, then can take $φ$ to be real ( $φ : Ω \to ℝ$ )

Proof. Want $M f = z f$ for some $z \in ℂ$ . So want $(z I - M) f = 0$ to have a non-trivial solution $f \neq 0$ . This happens if and only if $z I - M$ is singular, which happens if and only if $\det (z I - M) = 0$ .

$z \mapsto \det (z I - M)$ is a degree $n$ polynomial in $ℂ$ (degree $n$ since the leading term is $z^{n}$ ), so the fundamental theorem of algebra shows that there exists $λ \in ℂ$ such that $\det (λ I - M) = 0$ . □

Lemma 1.4. Assuming that:

$M$ is Hermitian

Then all eigenvalues are real

Proof.

\begin{array}{l} \bar{λ} ⟨ φ, φ ⟩ & = ⟨ λ φ, φ ⟩ \\ = ⟨ M φ, φ ⟩ \\ = ⟨ φ, M φ ⟩ \\ = ⟨ φ, λ φ ⟩ \\ = λ ⟨ φ, φ ⟩ \end{array}

Since $φ \neq 0$ , $⟨ φ, φ ⟩ = ∥ φ ∥^{2} > 0$ , hence $λ = \bar{λ}$ , i.e. $λ \in ℝ$ . □

Lemma 1.5. Assuming that:

$M$ Hermitian
$λ_{i} \neq λ_{j}$ are eigenvalues of $M$ with eigenvectors $φ_{i}$ , $φ_{j}$

Then

⟨ φ_{i}, φ_{j} ⟩ = 0

Proof.

\begin{array}{l} λ_{i} ⟨ φ_{i}, φ_{j} ⟩ & = ⟨ M φ_{i}, φ_{j} ⟩ \\ = ⟨ φ_{i}, M φ_{j} ⟩ \\ = λ_{j} ⟨ φ_{i}, φ_{j} ⟩ \end{array}

Since we assumed $λ_{i} \neq λ_{j}$ , this gives $⟨ φ_{i}, φ_{j} ⟩ = 0$ . □

Proof. Let $φ = f + i g$ . Then $M φ = M f + i M g = λ φ = λ f + i λ g$ . Hence $M f = M λ$ and $M g = λ g$ . So either $f$ or $g$ works. □

Notation. For $f, g \in l^{2} (Ω)$ , $f g^{H}$ denotes the matrix $(f g^{H}) (x, y) = f (x) \bar{g} (y)$ .

“ $(f g^{H}) h = f g^{H} h = f ⟨ g, h ⟩$ ”

Proof of Spectral theorem for Hermitian matrices. Using the above lemmas, can find $λ_{n} \in ℝ$ and $φ_{i} : Ω \to ℂ$ non-zero such that $M φ_{n} = λ_{n} φ_{n}$ and $∥ φ_{n} ∥ = 1$ .

Then let $M^{'} = M - λ_{n} φ_{n} φ_{n}^{H}$ . $l^{2} (Ω) = span (φ_{n}) \oplus span {(φ_{n})}^{⊤}$ . Then check that $M^{'}$ acts on $span {(φ_{n})}^{⊤}$ and use induction. □

Theorem 1.7 (Courant-Fischer-Weyl Theorem). Assuming: - $M : Ω \times Ω \to ℝ$ symmetric - eigenvalues $λ_{1} \leq \dots \leq λ_{n}$ Then:

λ_{k} = \min_{\begin{array}{c} W \leq l^{2} (Ω) \\ \dim W = k \end{array}} \max_{\begin{array}{c} f \in W \\ f \neq 0 \end{array}} \frac{⟨ f, M f ⟩}{⟨ f, f ⟩} = F_{k} .

Proof. Let $W^{'} = span (φ_{1}, \dots, φ_{k})$ . Note

F_{k} \leq \max_{\begin{array}{c} f \in W \\ f \neq 0 \end{array}} \frac{⟨ f, M f ⟩}{⟨ f, f ⟩} .

For $f \in W$ , $f = \sum_{i = 1}^{k} α_{i} φ_{i}$ , so

\frac{⟨ f, M f ⟩}{⟨ f, f ⟩} = \frac{\sum_{i = 1}^{k} α_{i}^{2} λ_{i}}{\sum_{i = 1}^{k} α_{i}^{2}} \leq \frac{λ_{k} \sum_{i = 1}^{k} α_{i}^{2}}{\sum_{i = 1}^{k} α_{i}^{2}} = λ_{k} .

So $F_{k} \leq λ_{k}$ .

Now suppose $W$ is a subspace with $\dim W = k$ . Let $V = span (φ_{k}, \dots, φ_{n})$ , and note $\div V = n - k + 1$ . Note

\dim (V \cap W) = \dim V + \dim W - \dim (V + W) \geq k + (n - k + 1) - n = 1 .

So for all such $W$ , there exists $f \in V \cap W$ , $f \neq 0$ such that $f = \sum_{i \geq k} α_{i} φ_{i}$ . Then

⟨ f, M f ⟩ = \sum_{i \geq k} α_{i}^{2} λ_{i} \geq λ_{k} \sum_{i \geq k} α_{i}^{2} = λ_{k} ⟨ f, f ⟩,

so $F_{k} \geq λ_{k}$ . □

Notation 1.9. Define $Q_{M} : l^{2} (Ω) \to ℂ$ by $Q_{M} (f) = ⟨ f, M f ⟩ = \sum_{x, y} f (x) M (x, y) f (y)$ .

Define $q_{m} (f) = \frac{Q_{M} (f)}{Q_{I} (f)}$ .

$λ_{1} (M) = \min_{f \neq 0} q_{M} (f)$ and it is attained only on

Lemma 1.10. eigenfunctions of $λ_{1}$ .

Proof. Let $f = \sum_{i} α_{i} φ_{i}$ and $M f = \sum_{i} α_{i} λ_{i} φ_{i}$ . Then

\begin{array}{l} Q_{M} (f) & = ⟨ f, M f ⟩ \\ \sum_{i, j} α_{i} α_{j} λ_{i} ⟨ φ_{i}, φ_{j} ⟩ \\ = \sum_{i} α_{i}^{2} λ_{i} \end{array}

and

q_{M} (f) = \frac{\sum_{i} α_{i}^{2} λ_{i}}{\sum_{i} α_{i}^{2}} \geq λ_{i} .

Equality occurs here if and only if $\sum_{i} (λ_{1} - λ_{i}) α_{i}^{2} = 0$ . So $α_{i} = 0$ whenever $λ_{i} > λ_{1}$ . □

Assuming:

Lemma 1.11. - $φ_{1}$ is an eigenfunction of $λ_{1}$ . Then: $λ_{2} (M) = \min_{\begin{array}{c} f ⊥ φ_{1} \\ f \neq 0 \end{array}} q_{M} (f)$ , and it is attained only on eigenfunctions of $λ_{2} (M)$ .

Proof.

q_{M} (f) = \frac{\sum_{i} α_{i}^{2} λ_{i}}{\sum_{i} α_{i}^{2}} \geq \frac{α_{1}^{2} λ_{1} + (\sum_{i \geq 2} α_{i}^{2}) λ_{2}}{\sum_{i} α_{i}^{2}} .

\min_{\begin{array}{c} f ⊥ φ_{i} \\ f \neq 0 \end{array}} q_{M} (f) \geq λ_{2} .

Deal with the equality case similarly to before. □

1 Setting