*Course:* Math 535 - Mathematical Methods in Data Science (MMiDS)

*Author:* Sebastien Roch, Department of Mathematics, University of Wisconsin-Madison

*Updated:* Sep 21, 2020

*Copyright:* © 2020 Sebastien Roch

A convenient way of specifying a graph is the following matrix representation.

**Definition (Adjacency Matrix)**: Assume the undirected graph $G = (V,E)$ has
$n = |V|$ vertices. The adjacency matrix $A$ of $G$ is the $n\times n$ symmetric matrix
defined as

$\lhd$

(Source)

$$
A=
\begin{pmatrix}
0 & 1 & 1\\
1 & 0 & 1\\
1 & 1 & 0
\end{pmatrix}.
$$

$\lhd$

**Definition (Incidence Matrix):** The incidence matrix of an undirected graph $G = (V, E)$ is the $n \times m$ matrix $B$, where $n = |V|$ and $m =|E|$ are the numbers of vertices and edges respectively, such that $B_{ij} = 1$ if the vertex $i$ and edge $e_j$ are incident and 0 otherwise. $\lhd$

(Source)

$$
B
=
\begin{pmatrix}
1 & 1 & 1 & 0\\
1 & 0 & 0 & 0\\
0 & 1 & 0 & 1\\
0 & 0 & 1 & 1
\end{pmatrix}.
$$

$\lhd$

**Definition (Oriented Incidence Matrix):** An oriented incidence matrix of an (undirected) graph $G = (V, E)$ is the incidence matrix of an orientation of $G$. $\lhd$

(Source)

$\lhd$

In [2]:

```
g = complete_graph(3)
```

Out[2]:

{3, 3} undirected simple Int64 graph

In [3]:

```
A = adjacency_matrix(g)
```

Out[3]:

3×3 SparseArrays.SparseMatrixCSC{Int64,Int64} with 6 stored entries: [2, 1] = 1 [3, 1] = 1 [1, 2] = 1 [3, 2] = 1 [1, 3] = 1 [2, 3] = 1

In [4]:

```
Array(A)
```

Out[4]:

3×3 Array{Int64,2}: 0 1 1 1 0 1 1 1 0

In [5]:

```
g = smallgraph(:petersen)
A = Array(adjacency_matrix(g))
```

Out[5]:

10×10 Array{Int64,2}: 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0

In [6]:

```
Array(incidence_matrix(g))
```

Out[6]:

10×15 Array{Int64,2}: 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

Our main matrix of interest is the Laplacian matrix.

**Definition (Laplacian Matrix):** Let $G = (V,E)$ be a graph with vertices $V = \{1, \ldots, n\}$ and adjacency matrix $A \in \mathbb{R}^{n \times n}$. Let $D = \mathrm{diag}(\delta(1), \ldots, \delta(n))$ be the degree matrix. The Laplacian matrix associated to $G$ is defined as $L = D - A$. Its entries are

$\lhd$

Observe that the Laplacian matrix $L$ of a graph $G$ is symmetric:

$$ L^T = (D- A)^T = D^T - A^T = D - A $$where we used that both $D$ and $A$ are themselves symmetric. The associated quadratic form is particularly simple and will play an important role.

**Lemma (Laplacian Quadratic Form):** Let $G = (V, E)$ be a graph with $n = |V|$ vertices. Its Laplacian matrix $L$ is PSD and furthermore we have the following formula for the Laplacian quadratic form

for any $\mathbf{x} = (x_1, \ldots, x_n)^T \in \mathbb{R}^n$.

*Proof:* Let $B$ be an oriented incidence matrix of $G$. We claim that $L = B B^T$. Indeed, for $i \neq j$, entry $(i,j)$ of $B B^T$ is a sum over all edges containing $i$ and $j$ as endvertices, of which there is at most one. When $\{i,j\} \in E$, that entry is $-1$, since one of $i$ or $j$ has a $1$ in the column of $B$ corresponding to $e$ and the other one has a $-1$. For $i = j$, letting $b_{xy}$ be entry $(x,y)$ of $B$,

Thus, for any $\mathbf{x}$, we have $(B^T \mathbf{x})_k = x_v - x_u$ if the edge $e_k = \{u, v\}$ is oriented as $(u,v)$ under $B$. That implies

$$ \mathbf{x}^T L \mathbf{x} = \mathbf{x}^T B B^T \mathbf{x} = \|B^T \mathbf{x}\|^2 = \sum_{e = \{i,j\} \in E} (x_i - x_j)^2. $$Since the latter is always nonnegative, it also implies that $L$ is PSD. $\square$

As a convention, we denote the eigenvalues of a Laplacian matrix $L$ by

$$ 0 \leq \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n. $$Another important observation:

**Lemma ($\mu_1 = 0$):** Let $G = (V, E)$ be a graph with $n = |V|$ vertices and Laplacian matrix $L$. The constant unit vector

is an eigenvector of $L$ with eigenvalue $0$.

*Proof:* Let $B$ be an oriented incidence matrix of $G$ recall that $L = B B^T$. By construction $B^T \mathbf{y}_1 = \mathbf{0}$ since each column of $B$ has exactly one $1$ and one $-1$. So $L \mathbf{y}_1 = B B^T \mathbf{y}_1 = \mathbf{0}$ as claimed. $\square$

(Source)

In [5]:

```
g = grid([4,7])
```

Out[5]:

{28, 45} undirected simple Int64 graph

In [6]:

```
function rand_locs(g)
return rand(nv(g)), rand(nv(g)) # random x and y coord for each vertex
end
```

Out[6]:

rand_locs (generic function with 1 method)

In [7]:

```
(x, y) = rand_locs(g)
hcat(x,y)
```

Out[7]:

28×2 Array{Float64,2}: 0.191692 0.606737 0.989004 0.352409 0.189396 0.51508 0.816165 0.587919 0.436631 0.0819465 0.50328 0.586298 0.3384 0.835183 0.740025 0.818151 0.754872 0.119381 0.699313 0.38022 0.437357 0.593008 0.771573 0.61867 0.0918346 0.227644 ⋮ 0.2729 0.787315 0.0667081 0.801595 0.391096 0.387632 0.14777 0.355164 0.247434 0.194785 0.328025 0.0842352 0.406501 0.271673 0.452194 0.910649 0.699653 0.304761 0.736827 0.244049 0.791831 0.205615 0.854796 0.181293

In [9]:

```
gplot(g, layout=rand_locs)
```

Out[9]:

In [12]:

```
function spec_locs(g)
L = Array(laplacian_matrix(g)) # laplacian L of g
F = eigen(L) # spectral decomposition
v = F.vectors # eigenvectors
return v[:,2], v[:,3] # returns 2nd and 3rd eigenvectors
end
```

Out[12]:

spec_locs (generic function with 1 method)

In [13]:

```
gplot(g, layout=spec_locs)
```

Out[13]:

**Lemma (Laplacian and Connectedness):** If $G$ is connected, then the Laplacian eigenvalue $\mu_2 > 0$.

*Proof:* Let $G = (V, E)$ with $n = |V|$ and let $L = \sum_{i=1}^n \mu_i \mathbf{y}_i \mathbf{y}_i^T$ be a spectral decomposition of its Laplacian $L$ with $0 = \mu_1 \leq \cdots \leq \mu_n$. Suppose by way of contradiction that $\mu_2 = 0$. Any eigenvector $\mathbf{y} = (y_{1}, \ldots, y_{n})^T$ with $0$ eigenvalue satisfies $L \mathbf{y} = \mathbf{0}$ by definition. By the Laplacian Quadratic Form Lemma then

In order for this to hold, it must be that any two adjacent vertices $i$ and $j$ have $y_{i} = y_{j}$. Furthermore, because $G$ is connected, between any two of its vertices $u$ and $v$ - adjacent or not - there is a path $u = w_0 \sim \cdots \sim w_k = v$ along which the $y_{w}$'s must be the same. Thus $\mathbf{y}$ is a constant vector. But that is a contradiction since the eigenvectors $\mathbf{y}_1, \ldots, \mathbf{y}_n$ are in fact linearly independent, so that $\mathbf{y}_1$ and $\mathbf{y}_2$ cannot both be a constant vector. $\square$

**Lemma (Number of Connected Components):** If $\mu_{k+1}$ is the smallest nonzero Laplacian eigenvalue of $G$, then $G$ has $k$ connected components.

We will be interested in more quantitative results of this type. Before proceeding, we start with a simple observation. By our proof of the Spectral Theorem, the largest eigenvalue $\mu_n$ of the matrix Laplacian $L$ is the solution to the optimization problem

$$ \mu_n = \max\{\langle \mathbf{x}, L \mathbf{x}\rangle:\|\mathbf{x}\| = 1\}. $$Such extremal characterization is useful in order to bound the eigenvalue $\mu_n$, since any choice of $\mathbf{x}$ with $\|\mathbf{x}\| =1$ gives a lower bound through the quantity $\langle \mathbf{x}, L \mathbf{x}\rangle$. That perspective will be key to our application to graph partitioning.

**Lemma (Laplacian and Degree):** Let $G = (V, E)$ be a graph with maximum degree $\bar{\delta}$. Let $\mu_n$ be the largest eigenvalue of its matrix Laplacian $L$. Then

*Proof idea:* As explained before the statement of the lemma, it suffices to find a good test unit vector $\mathbf{x}$ to plug into $\langle \mathbf{x}, L \mathbf{x}\rangle$. A clever choice does the trick.

In [14]:

```
A = [0 1 1 0 0; 1 0 1 0 0; 1 1 0 0 0; 0 0 0 0 1; 0 0 0 1 0]
```

Out[14]:

5×5 Array{Int64,2}: 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0

In [15]:

```
degrees = reshape(sum(A,dims=1),:)
```

Out[15]:

5-element Array{Int64,1}: 2 2 2 1 1

In [16]:

```
D = Diagonal(degrees)
```

Out[16]:

5×5 Diagonal{Int64,Array{Int64,1}}: 2 ⋅ ⋅ ⋅ ⋅ ⋅ 2 ⋅ ⋅ ⋅ ⋅ ⋅ 2 ⋅ ⋅ ⋅ ⋅ ⋅ 1 ⋅ ⋅ ⋅ ⋅ ⋅ 1

In [17]:

```
L = D - A
```

Out[17]:

5×5 Array{Int64,2}: 2 -1 -1 0 0 -1 2 -1 0 0 -1 -1 2 0 0 0 0 0 1 -1 0 0 0 -1 1

In [18]:

```
F = eigen(L)
F.values
```

Out[18]:

5-element Array{Float64,1}: 1.1102230246251565e-15 1.3322676295501878e-15 2.0 3.0 3.0

In [19]:

```
g = smallgraph(:petersen)
L = Array(laplacian_matrix(g))
```

Out[19]:

10×10 Array{Int64,2}: 3 -1 0 0 -1 -1 0 0 0 0 -1 3 -1 0 0 0 -1 0 0 0 0 -1 3 -1 0 0 0 -1 0 0 0 0 -1 3 -1 0 0 0 -1 0 -1 0 0 -1 3 0 0 0 0 -1 -1 0 0 0 0 3 0 -1 -1 0 0 -1 0 0 0 0 3 0 -1 -1 0 0 -1 0 0 -1 0 3 0 -1 0 0 0 -1 0 -1 -1 0 3 0 0 0 0 0 -1 0 -1 -1 0 3

In [20]:

```
F = eigen(L)
F.values
```

Out[20]:

10-element Array{Float64,1}: 2.6645352591003757e-15 1.9999999999999982 1.9999999999999982 1.9999999999999984 2.0 2.0000000000000027 4.999999999999998 5.000000000000001 5.000000000000002 5.0000000000000036