Graph Laplacians
system:sage

<h2> Graph Laplacians </h2>
by Robert L Miller
<br><br>
<b>Def. 1</b> Given a simple graph $G$ (no loops or multiple edges) on $n$ vertices, it is standard to define the <i> adjacency matrix </i> $A(G)$ of the graph to be an $n \times n$ integer matrix with a 1 in entry $i,j$ if and only if $\{i,j\}$ is an edge of the graph (otherwise the entry is 0).
<br><br>

{{{id=0|
P = graphs.PetersenGraph()
M = P.adjacency_matrix(); M
///
[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]
}}}

<br><br>
<b>Exercise 1</b> Prove that the $i,j$ entry of the $k^{th}$ power of the adjacency matrix is equal to the number of paths of length $k$ from vertex $i$ to vertex $j$. Hint: use induction.
<br><br>
<b>Exercise 2</b> Prove that two graphs $G$ and $H$ are isomorphic if and only if there is a permutation matrix $P$ such that $P A(G) P^T = A(H).$
<br><br>
Note that for permutation matrices, $P^T = P^{-1}$, so isomorphic graphs have similar adjacency matrices.
<br><br>
<b>Exercise 3</b> Find two nonisomorphic graphs whose adjacency matrices have the same characteristic polynomials.
<br><br>

{{{id=6|
for g in graphs(4): # iterates over isomorphism types
    print g.characteristic_polynomial()
///
x^4
x^4 - x^2
x^4 - 2*x^2
x^4 - 3*x^2 - 2*x
x^4 - 3*x^2
x^4 - 2*x^2 + 1
x^4 - 3*x^2 + 1
x^4 - 4*x^2 - 2*x + 1
x^4 - 4*x^2
x^4 - 5*x^2 - 4*x
x^4 - 6*x^2 - 8*x - 3
}}}

<br><br>
<b>Exercise 4</b> Prove that if a graph $G$ has $e$ edges and $t$ triangles (and $A := A(G)$) then:
<ul>
<li>tr$A = 0$
<li>tr$A^2 = 2e$
<li>tr$A^3 = 6t$.
</ul>
<br><br>

{{{id=2|
# For example:
G = graphs.BullGraph(); G.show()
///
}}}

{{{id=4|
M = G.adjacency_matrix(); show((M,M^2,M^3))
///
<html><div class="math">\left(\left(\begin{array}{rrrrr}
0 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0
\end{array}\right), 
 \left(\begin{array}{rrrrr}
2 & 1 & 1 & 1 & 1 \\
1 & 3 & 1 & 0 & 1 \\
1 & 1 & 3 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 & 1
\end{array}\right), 
 \left(\begin{array}{rrrrr}
2 & 4 & 4 & 1 & 1 \\
4 & 2 & 5 & 3 & 1 \\
4 & 5 & 2 & 1 & 3 \\
1 & 3 & 1 & 0 & 1 \\
1 & 1 & 3 & 1 & 0
\end{array}\right)\right)</div></html>
}}}

<br><br>
<b>Def. 2</b> Given a simple graph $G$, we can also define the <i>Laplacian</i> (or <i>Kirchhoff</i>) matrix to be $L(G) = D - A(G)$, where $D$ is the diagonal matrix whose $i,i$ entry is the degree of vertex $i$. (Note- I have seen grown men bicker over whether this definition should be $A(G) - D$ or $D - A(G)$. It doesn't really matter, since the mathematics works the same either way.)
<br><br>

{{{id=5|
P = graphs.PetersenGraph()
M = P.laplacian_matrix(); M
///
[ 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]
}}}

<br><br>
<b>Exercise 5</b> Show that the rank of the Laplacian matrix is never full. Show that a graph on $n$ vertices is connected if and only if the rank of the Laplacian is equal to $n-1$. Show that $n$ minus the rank of the Laplacian is equal to the number of connected components of the graph.
<br><br>

{{{id=7|
M.rank()
///
9
}}}

{{{id=9|
(2*P).laplacian_matrix().rank()
///
18
}}}

{{{id=10|
(2*P).show()
///
}}}

<br><br>
Note that adjacency matrices and Laplacian matrices are symmetric. Recall that symmetric matrices always have real eigenvalues, and if $v$ and $w$ are eigenvectors with different eigenvalues, then $v \perp w$. Further, if $M$ is a symmetric $n \times n$ matrix, then $R^n$ has an orthonormal basis consisting of eigenvectors of $M$. For a graph $G$, we can view $A(G)$ or $L(G)$ as a linear mapping on $R^{V(G)}$, the space of real-valued functions on $V(G)$.<br>
If $A = A(G)$, and $f \in R^{V(G)}$, then the value of $Af$ at $u$ is the sum of $f(v)$, where $v$ ranges over neighbors of $u$.
<br><br>
<b>Exercise 6</b> Work out a similar interpretation for $Lf$, where $L = L(G)$.
<br><br>
<b>Exercise 7</b> Compute the eigenvectors of $A(C_5)$ and $L(C_5)$ where $C_5$ is the five-cycle, and make plots demonstrating the functions these represent. Think of these plots in terms of the interpretations of $A$ and $L$ above.
<br><br>
Hints:

{{{id=11|
C = graphs.CycleGraph(5)
G = C.plot()
G += text("0", (0.1,1.1))
G.axes(False)
G.show()
///
}}}

{{{id=15|
L = C.laplacian_matrix()
for eval,espace in L.eigenspaces():
    print eval
    print espace.basis()
    print
///
0
[
(1, 1, 1, 1, 1)
]

a1
[
(1, 0, -1, a1 - 2, -a1 + 2),
(0, 1, -a1 + 2, a1 - 2, -1)
]
}}}

{{{id=18|
L.eigenspaces()[1][0]
///
a1
}}}

{{{id=19|
L.eigenspaces()[1][0].complex_embedding()
///
1.38196601125
}}}

<br><br>
<b>Exercise 8</b> Since $R^n$ has an orthonormal basis consisting of eigenvectors of $L = L(G)$ ($|G|=n$), and since $L$ is positive semidefinite (given here as fact), the eigenvalues of $L$ are all nonnegative. Denote them by $0 \leq \lambda_1 \leq ... \leq \lambda_n$. Show that for a $k$-regular graph (one whose vertices are all of degree $k$), the eigenvalues of the adjacency matrix $A$ are $k - \lambda_1, ..., k - \lambda_n$.
<br><br>

{{{id=20|
D = graphs.DodecahedralGraph()
D.show(figsize=[2,2], vertex_labels=False, vertex_size=0)
///
}}}

{{{id=21|
A = D.adjacency_matrix()
L = D.laplacian_matrix()
A=A.change_ring(RDF)
L=L.change_ring(RDF)
///
}}}

{{{id=22|
A_e = sorted([es[0] for es in A.eigenspaces()], reverse=True)
///
}}}

{{{id=23|
L_e = sorted([es[0] for es in L.eigenspaces()])
///
}}}

{{{id=27|
[A_e[i] + L_e[i] for i in xrange(20)]
///
[3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0, 3.0]
}}}

{{{id=28|
D.degree()
///
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
}}}

<br><br>
<b>Exercise 9</b> Show that the multiplicity of the eigenvalue 0 (for $L$) is the number of connected components of the graph, and hence that $0 = \lambda_1$ is always an eigenvalue.
<br><br>
<b>Exercise 10</b> Find $\lambda_2$ for $L(D)$ where $D$ is the dodecahedron, and find the associated eigenspace $V$ (note that the dimension of $V$ is three). Take a basis $\{b_1, b_2, b_3\}$ for the eigenspace consisting of unit length vectors. Construct an embedding of $D$ in $R^3$ by placing vertex $i$ at position $(b_{1,i},b_{2,i},b_{3,i})$ for each $0 \leq i < 20$. Plot the embedding in 3d.
<br><br>
Hint:

{{{id=29|
G = graphs.CycleGraph(3)
G.vertices()
///
[0, 1, 2]
}}}

{{{id=30|
G.plot3d(pos3d={0:[0,0,0],1:[1,0,1],2:[1,1,2]})
///
}}}

{{{id=31|

///
}}}

{{{id=32|

///
}}}

{{{id=33|

///
}}}

{{{id=34|

///
}}}

{{{id=35|

///
}}}

{{{id=36|

///
}}}

{{{id=37|

///
}}}