Graphs and some of their matrices - Spectral Graph Theory

2 Graphs and some of their matrices

Graph $G = (V, E)$ : set of vertices $V$ , $| V | = n$ , $E$ is a set of (unordered) pairs of vertices.

Definition 2.1 (Adjacency matrix). The adjacency matrix of a graph $G$ is the matrix $A_{G} : V \times V \to ℝ$ defined by

A_{G} (x, y) = {\begin{matrix} 1 & {x, y} \in E (G) \\ 0 & {x, y} \notin E (G) \end{matrix}

Definition 2.2 (Degree matrix). The degree matrix of a graph $G$ is the matrix $D_{G} : V \times V \to ℝ$ defined by

D_{G} (x, y) = {\begin{matrix} \deg (x) & x = y \\ 0 & otherwise \end{matrix}

Definition 2.3 (Laplacian matrix). The Laplacian matrix of a graph $G$ is defined by $L_{G} = D - A$ .

We can now calculate:

\begin{array}{l} Q_{A} (f) & = \sum_{x, y} f (x) A (x, y) f (y) \\ = 2 \sum_{x \sim y} f (x) f (y) \\ Q_{D} (f) & = \sum_{x, y} f (x) D (x, y) f (y) \\ = \sum_{x} f {(x)}^{2} \deg (x) \\ = \sum_{x} f {(x)}^{2} \sum_{y} A (x, y) \\ = \sum_{x, y} f {(x)}^{2} A (x, y) \\ = \frac{1}{2} \sum_{x, y} (f {(x)}^{2} + f {(y)}^{2}) A (x, y) \\ = \sum_{x \sim y} (f {(x)}^{2} + f {(y)}^{2}) \\ Q_{L} (f) & = Q_{D - A} (f) \\ = Q_{D} (f) - Q_{A} (f) \\ = \sum_{x \sim y} (f {(x)}^{2} + f {(y)}^{2} - 2 f (x) f (y)) \\ = \sum_{x \sim y} {(f (x) - f (y))}^{2} \\ \geq 0 \end{array}

Corollary 2.4. For any graph $G$ , $L_{G}$ is a positive semi definite matrix with eigenvector $1$ , which has eigenvalue $1$ .

Proof. Since $Q_{L} (f) = \sum_{x \sim y} {(f (x) - f (y))}^{2}$ , we see that $Q_{L} (f) \geq 0$ , with equality when $f$ is constant. □

Proposition 2.5. $λ_{2} (L_{g}) > 0$ if and only if $G$ is connected. $λ_{k} (L_{G}) = 0$ if and only if $G$ has at least $k$ connected components.

Proof.

λ_{2} = \min_{\begin{array}{c} f ⊥ 1 \\ f \neq 0 \end{array}} \frac{\sum_{x \sim y} {(f (x) - f (y))}^{2}}{⟨ f, f ⟩} \geq 0

Equality happens if and only if $Q_{L} (f) = 0$ , which happens if and only if $f$ is constant on connected components. The dimension of ${f : constant on connected components}$ is the number of connected components of $G$ .

TODO? □

TODO

2.1 Irregular graphs

$A$ , $D$ , $L = D - A$ , $Q_{L} (f) = \sum_{x \sim y} {(f (x) - f (y))}^{2}$ , $q_{L} (f) = \frac{\sum_{x \sim y} {(f (x) - f (y))}^{2}}{\sum_{x} f {(x)}^{2}}$ .

\begin{array}{l} Q_{L} (f) & = ⟨ f, L f ⟩ \\ = ⟨, (D - A) f ⟩ \\ = ⟨ f, (2 D - (D + A)) f ⟩ \\ = ⟨ f, 2 D f ⟩ - ⟨ f, (D + A) f ⟩ \end{array}

When $G$ is $d$ -regular,

{\tilde{L}}_{G} = \frac{1}{d} L_{G} = I - \frac{1}{d} A_{G},

$λ_{i} ({\tilde{L}}_{G} \in [0, 2]$ .

q_{\tilde{L}} (f) = \frac{\sum_{x \sim y} {(f (x) - f (y))}^{2}}{\sum_{x} d (x) f {(x)}^{2}} = 2 - \frac{\sum_{x \sim y} {(f (x) + f (y))}^{2}}{\sum_{x} d (x) f {(x)}^{2}} .

Want $M$ such that $q_{M} (f)$ equals the expression above. Recall $q_{M} (f) = \frac{⟨ f, M f ⟩}{⟨ f, f ⟩}$ . But the above expression is $\frac{⟨ f, M f ⟩}{⟨ f, D f ⟩}$ .

Let $D^{\frac{1}{2}} (x, y) = 𝟙_{x = y} \sqrt{d (x)}$ . Assume $d (x) \geq 1$ for all $x \in G$ . Note

q_{M} (D^{\frac{1}{2}} f) = \frac{⟨ D^{\frac{1}{2}} f, M D^{\frac{1}{2}} f ⟩}{⟨ D^{\frac{1}{2}} f, D^{\frac{1}{2}} f ⟩} = \frac{⟨ f, D^{\frac{1}{2}} M D^{\frac{1}{2}} f ⟩}{⟨ f, D f ⟩} .

Want $D^{\frac{1}{2}} M D^{\frac{1}{2}} = L = D - A$ . Define

{\tilde{L}}_{G} = D^{- \frac{1}{2}} (D - A) D^{- \frac{1}{2}} = I - D^{- \frac{1}{2}} A D^{- \frac{1}{2}} .

{\tilde{L}}_{G} = {\begin{matrix} 1 & if x = y \\ - \frac{1}{\sqrt{d (x) d (y)}} & if x \neq y and x \sim y \\ 0 & if x \neq y and x ⁄ \sim y \end{matrix}

Also,

q_{{\tilde{L}}_{G}} (D^{\frac{1}{2}} f) = \frac{\sum_{x \sim y} {(f (x) - y (y))}^{2}}{\sum_{x} d (x) f {(x)}^{2}} .

We have

λ_{k} ({\tilde{L}}_{G}) = \min_{\dim W = K} \max_{\begin{array}{c} f \in W \\ f \neq 0 \end{array}} q_{{\tilde{L}}_{G}} (D^{\frac{1}{2}} f) .