11-12-2024 - Graph Theory

Recall from 11-12-2024 - Graph Theory:

G = (v er t i ces V, e d g es E)

(i, j) \in E

means $\exists$ edge between $i$ & $j$ . $A =$ adjacency matrix $D =$ degree $L = D - A =$ Laplacian matrix Fact: eigenvalues of $L$ are nonnegative.

Moreover, if we order the eigenvalues $λ_{1} \leq \dots \leq λ_{n}$ , then
$λ_{1} = 0$ and
$λ_{2}, λ_{3}, \dots, λ_{n} > 0$
$∣ \overset{ˉ}{v}_{i} ∣^{2} = 1$
$\overset{ˉ}{v}_{1} = 1 ⋮ 1 \frac{1}{n}$ because sum of elements in each row of $L$ is 0.
$\overset{ˉ}{v}_{2}$ is called Fiedler vector
$\overset{ˉ}{v}_{2}, \overset{ˉ}{v}_{3}, \dots, \overset{ˉ}{v}_{n}$ all have sum of entries = 0 because $[\overset{ˉ}{v}_{1} ∣ \overset{ˉ}{v}_{2} ∣ \dots ∣ \overset{ˉ}{v}_{n}]$ is precisely the matrix that diagonalizes $L$ . $[\overset{ˉ}{v}_{1} ∣ \overset{ˉ}{v}_{2} ∣ \dots ∣ \overset{ˉ}{v}_{n}] [λ_{1} \dots \dots λ_{n}] [\overset{ˉ}{v}_{1} ∣ \overset{ˉ}{v}_{2} ∣ \dots ∣ \overset{ˉ}{v}_{n}]^{T} = L$ , i.e. $[\overset{ˉ}{v}_{1} ∣ \overset{ˉ}{v}_{2} ∣ \dots ∣ \overset{ˉ}{v}_{n}]$ is orthogonal.
$\overset{ˉ}{v}_{i} ⊥ \overset{ˉ}{v}_{j}, \forall i \neq = j$ ; $\overset{ˉ}{v}_{2} ⊥ \overset{ˉ}{v}_{1}$ , i.e. $\overset{ˉ}{v}_{2} \cdot \overset{ˉ}{v}_{1} = 0$ .

Main Theorem (12.4.8.1)

The $\overset{ˉ}{v}_{2}$ is a solution of the optimization problem:

(i, j) \in E min \sum (x_{i} - x_{j})^{2}

under the constraints (*)

i = 1 \sum n x_{i} = 0

and (**)

i = 1 \sum n x_{i}^{2} = n

Ideas

Idea #1

The constraint (*) means

x \in span {\overset{ˉ}{v}_{2}, \overset{ˉ}{v}_{3}, \dots, \overset{ˉ}{v}_{n}}

rewritten as $x ⊥ \overset{ˉ}{v}_{1}$ , means x is in

Implies

x = i = 2 \sum n w_{i} \overset{ˉ}{v}_{i}

(uniquely). ( $\exists w_{2}, \dots, w_{n} \in R$ determined uniquely.)

Translate our optimization problem in terms of the parameters $w_{2}, \dots, w_{n}$ : (*) disappears (**)? $∣ x ∣^{2} = n = (\sum_{i = 2}^{n} w_{i} \overset{ˉ}{v}_{i}) \cdot (\sum_{j = 2}^{n} w_{j} \overset{ˉ}{v}_{j}) = \sum_{i = 2}^{n} w_{i}^{2}$ , since $\overset{ˉ}{v}_{i}$ and $\overset{ˉ}{v}_{j}$ are orthogonal.

Remains to rewrite the objective function in terms of $w_{i}$ s.

(i, j) \in E \sum (x_{i} - x_{j})^{2} = x^{T} Lx = (i = 2 \sum n w_{i} \overset{ˉ}{v}_{i})^{T} L (j = 2 \sum n w_{j} \overset{ˉ}{v}_{j})

= i, j = 2 \sum n w_{i} w_{j} \overset{ˉ}{v}_{i}^{T} L \overset{ˉ}{v}_{j} = i, j = 2 \sum n w_{i} w_{j} \overset{ˉ}{v}_{i}^{T} λ_{j} \overset{ˉ}{v}_{j} = i = 2 \sum n w_{i}^{2} λ_{i} ∣ \overset{ˉ}{v}_{i} ∣^{2}

Reformatted Optimization Problem

Minimize

i = 2 \sum n w_{i}^{2} λ_{i}

under the constraint

i = 2 \sum n w_{i}^{2} = n

Intuition: minimizer will be $x = w_{2} \overset{ˉ}{v}_{2} = n \overset{ˉ}{v}_{2}$ .

Rigorous Derivation

w_{2}^{2} = n - w_{3}^{2} - \dots - w_{n}^{2}

i = 2 \sum n w_{i}^{2} λ_{i} = w_{2}^{2} λ_{2} + i = 3 \sum n w_{i}^{2} λ_{i}

= (n - w_{3}^{2} - \dots - w_{n}^{2}) λ_{2} + i = 3 \sum n w_{i}^{2} λ_{i}

= n λ_{2} + i = 3 \sum n w_{i}^{2} (λ_{i} - λ_{2})

Objective function $\geq n λ_{2} > n λ_{2}$ when at least one $w_{i}^{2} > 0, i \geq_{3}$ ⇒ choose $w_{3} = w_{4} = \dots = w_{n} = 0$ will minimize the objective function so that

x = w_{2} \overset{ˉ}{v}_{2}

and

w_{2} = n

Final Thoughts

(i, j) \in E \sum (x_{i} - x_{j})^{2} = (i, j) \in E \sum x_{i}^{2} + x_{j}^{2} - 2 (i, j) \in E \sum x_{i} x_{j}

x^{T} Lx = x^{T} (D - A) x = x^{T} Dx - x^{T} Ax = i = 1 \sum n d_{ii} x_{i}^{2} - 2 (i, j) \in E \sum x_{i} x_{j}

Davy's Notes

Explorer