12 ***Graphs and matrices***12.1 Incidence matrix and connectivity 12.3 Spanning trees and Laplacian

12.2 Laplacian Matrix

The Laplacian matrix plays a fundamental role in many topics within probability, graph theory, algebraic topology and analysis. See Section 12.6 for references.

Let $D=diag[deg(1),\ldots,deg(n)]$ be the diagonal matrix with entries as the degrees of vertices. Recall that $A$ is the adjacency matrix defined in Definition 2.36. The Laplacian matrix is defined as $L=D-A$ . Verify that $L=\partial_{1}\partial_{1}^{T}$ using the matrix representation of $\partial_{1}$ and its transpose. Observe that even though $\partial_{1}$ is oriented, $L$ is unoriented. Further, it is easy to see that if we think of $\partial_{1}$ as linear transformations as in the previous sections, we have that

L:C_{0}\to C_{0};\,:\,\sum_{i=1}^{n}a_{i}v_{i}\mapsto\sum_{i=1}^{n}(a_{i}deg(v% _{i})-\sum_{j:v_{j}\sim v_{i}}a_{j})v_{i}.

For purposes of our analysis, we will view $L$ primarily as a matrix. Firstly observe that $r(L)=r(\partial_{1}\partial_{1}^{t})\leq r(\partial_{1})\wedge r(\partial_{1}^% {t})=r(\partial_{1})$ . Trivially, we have that $Ker\partial_{1}^{t}\subset KerL$ .

We set the notation $<x,y>=x.y=xy^{t}=yx^{t}$ for $x,y\in\mathbb{R}^{n}$ and $\|x\|^{2}=<x,x>=\sum_{i=1}^{n}x_{i}^{2}$ . Observe that for $x\in\mathbb{R}^{n}$ , we have that

x^{t}Lx=x^{t}\partial_{1}\partial_{1}^{t}x=<\partial_{1}^{t}x,\partial_{1}^{t}% x>=\|\partial_{1}^{t}x\|^{2}.

(12.1)

Hence, if $x\in KerL$ then by the above equation $\partial_{1}^{t}x=0$ i.e., $x\in Ker\partial_{1}^{t}$ i.e., $KerL=Ker\partial_{1}^{t}$ by our earlier observation. Hence $n(L):=r(KerL)=r(Ker\partial_{1}^{t})=n-r(\partial_{1})=\beta_{0}(G).$ Since $n(L)$ is the multiplicity of the eigenvalue $0$ , this shows that the multiplicity of $0$ is $\beta_{0}(G)$ .

From (12.1), we also have that $L$ is a positivie semi-definite matrix and hence all its eigenvalues are non-negative. Denote the eigenvalues by $\lambda_{1}\leq\lambda_{2}\ldots\leq\lambda_{n}$ . Summarizing our above conclusions, here is the theorem.

Theorem 12.9.

Let $l=\beta_{0}(G)$ . We have that $0=\lambda_{1}=\ldots=\lambda_{l}<\lambda_{l+1}\leq\ldots\lambda_{n}$ . Thus, $G$ is connected iff $\lambda_{2}>0$ .

Observe that $\partial_{1}^{t}x=(x_{i}-x_{j})_{(v_{i},v_{j})\in\overrightarrow{E}}$ and so by (12.1), we derive that

x^{t}Lx=\sum_{v_{i}\sim v_{j}}(x_{j}-X-i)^{2}.

Lemma 12.10.

Let $C_{1},\ldots,C_{l}$ be the components of $G$ . Define $x^{1},\ldots,x^{l}$ as vectors that are constant on each of the components respectively i.e., $x^{i}_{k}=\mathbf{1}[k\in C_{i}]$ . Then, we have that $x^{1},\ldots,x^{l}$ form a basis for $K e r L$ .

Proof.

Using that $\|\partial_{1}^{t}x\|^{2}=\sum_{v_{i}\sim v_{j}}(x_{i}-x_{j})^{2}$ and from (12.1), we know that if $Lx=0$ , $\partial_{1}^{t}x=0$ and hence $x_{i}=x_{j}$ for all $v_{i}\sim v_{j}$ . This implies that $x$ is a constant on each component and hence $x^{1},\ldots,x^{l}\in KerL$ . Since $r(KerL)=l$ , it suffices to show that $x^{1},\ldots,x^{l}$ are linearly independent. This follow easily as the vectors are supported on disjoint sets of vertices. ∎