Worked Adjacency And Laplacian Calculations

From an Edge List to Matrices

Adjacency and Laplacian matrices encode different information about a graph. The adjacency matrix records which pairs of vertices are joined; the Laplacian combines that information with the degrees. A fixed vertex order is essential: changing the order changes the displayed matrices, although it does not change their eigenvalues. In the examples below, each graph is specified by its vertex set and edge set, and the order used for its matrices is stated.

Definition: Let \(G=(V,E)\) be a finite simple graph with ordered vertices \(v_1,\ldots,v_n\). Its adjacency matrix \(\mathbf{A}(G)\) has entry \(A_{ij}=1\) if \(v_i v_j\in E\), and \(A_{ij}=0\) otherwise. Its degree matrix \(\mathbf{D}(G)\) is diagonal, with \(D_{ii}=\deg(v_i)\). The Laplacian is \(\mathbf{L}(G)=\mathbf{D}(G)-\mathbf{A}(G)\). In a simple graph, \(A_{ii}=0\), and \(\mathbf{A}(G)\) is symmetric.

Thus each row of \(\mathbf{A}\) lists the neighbors of one vertex, in the chosen order. The diagonal of \(\mathbf{L}\) contains degrees, and its off-diagonal entry \(L_{ij}\) is \(-1\) when \(v_i v_j\) is an edge and \(0\) otherwise. Every row of \(\mathbf{L}\) sums to zero: its diagonal entry is the number of incident edges, exactly balancing the \(-1\) entries in that row.

Matrix Powers Count Walks

Theorem: For every integer \(k\geq 0\), the entry \((\mathbf{A}^k)_{ij}\) is the number of walks of length \(k\) from \(v_i\) to \(v_j\). A walk may repeat vertices or edges; for \(k=0\), the length-zero walk stays at its starting vertex.

Proof. When \(k=0\), \(\mathbf{A}^0\) is the identity matrix: its \(ij\) entry is \(1\) if \(i=j\) and \(0\) otherwise, precisely the number of length-zero walks from \(v_i\) to \(v_j\). For \(k=1\), the claim is the definition of \(\mathbf{A}\). Now suppose it holds for \(k\). Matrix multiplication gives \((\mathbf{A}^{k+1})_{ij}=\sum_{r=1}^n(\mathbf{A}^k)_{ir}A_{rj}\). For each \(r\), the product counts a length-\(k\) walk from \(v_i\) to \(v_r\), followed by the edge \(v_rv_j\), if that edge exists; if it does not, \(A_{rj}=0\) and it contributes nothing. Every length-\((k+1)\) walk from \(v_i\) to \(v_j\) has exactly one penultimate vertex \(v_r\), so the sum counts each such walk exactly once. Induction proves the claim. \(\square\)

Worked Example: The Path on Three Vertices

Let \(G=(V,E)\) have \(V=\{1,2,3\}\), \(E=\{12,23\}\), and vertex order \(1,2,3\). The degrees are \(1,2,1\), so

\mathbf{A}= \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}, \qquad \mathbf{D}= \begin{pmatrix} 1&0&0\\ 0&2&0\\ 0&0&1 \end{pmatrix}, \qquad \mathbf{L}= \begin{pmatrix} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{pmatrix}.

Multiplying \(\mathbf{A}\) by itself gives

\mathbf{A}^2= \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&0&1 \end{pmatrix}.

For instance, the \((1,3)\) entry is \(0\cdot0+1\cdot1+0\cdot0=1\), counting the walk \(1,2,3\); the \((2,2)\) entry is \(1\cdot1+0\cdot0+1\cdot1=2\), counting \(2,1,2\) and \(2,3,2\). The diagonal entries \(1,2,1\) count the length-two returns from vertices \(1,2,3\), respectively. The matrix is symmetric, as the walks have corresponding reversals.

The adjacency eigenvalues can be checked from eigenvectors. For \(x=(1,0,-1)^T\), \(\mathbf{A}x=0\). For \(y=(1,\sqrt{2},1)^T\), \(\mathbf{A}y=\sqrt{2}y\); for \(z=(1,-\sqrt{2},1)^T\), \(\mathbf{A}z=-\sqrt{2}z\). These three independent vectors give eigenvalues \(0,\sqrt{2},-\sqrt{2}\). For the Laplacian, \(\mathbf{L}(1,1,1)^T=0\), \(\mathbf{L}(1,0,-1)^T=(1,0,-1)^T\), and \(\mathbf{L}(1,-2,1)^T=3(1,-2,1)^T\), giving eigenvalues \(0,1,3\).

Check: the diagonal degrees sum to \(1+2+1=4\), while the two edges contribute \(2|E|=2\cdot2=4\) to the degree sum. Also, each row of the displayed Laplacian sums to zero.

Triangles and Stars

Worked Example: The Triangle

Let \(G=(V,E)\) have \(V=\{1,2,3\}\), \(E=\{12,23,13\}\), in order \(1,2,3\). Every vertex has degree \(2\), so

\mathbf{A}= \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}, \qquad \mathbf{L}= \begin{pmatrix} 2&-1&-1\\ -1&2&-1\\ -1&-1&2 \end{pmatrix}.

Let \(\mathbf{1}=(1,1,1)^T\). Each row of \(\mathbf{A}\) has two ones, so \(\mathbf{A}\mathbf{1}=2\mathbf{1}\); each row of \(\mathbf{L}\) sums to zero, so \(\mathbf{L}\mathbf{1}=0\). If \(x=(x_1,x_2,x_3)^T\) has \(x_1+x_2+x_3=0\), then \((\mathbf{A}x)_i\) is the sum of the other two coordinates, hence \((\mathbf{A}x)_i=-x_i\). Thus \(\mathbf{A}x=-x\), and \(\mathbf{L}x=3x\). The subspace of such \(x\) has dimension two, so the adjacency eigenvalues are \(2,-1,-1\), and the Laplacian eigenvalues are \(0,3,3\).

Check: the sum of the adjacency eigenvalues is \(2-1-1=0\), matching the zero diagonal of \(\mathbf{A}\). The Laplacian eigenvalues sum to \(0+3+3=6\), matching its diagonal sum \(2+2+2=6\).

Worked Example: The Star \(K_{1,3}\)

Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\), \(E=\{12,13,14\}\), with center \(1\) and order \(1,2,3,4\). Its degrees are \(3,1,1,1\), so

\mathbf{A}= \begin{pmatrix} 0&1&1&1\\ 1&0&0&0\\ 1&0&0&0\\ 1&0&0&0 \end{pmatrix}, \qquad \mathbf{L}= \begin{pmatrix} 3&-1&-1&-1\\ -1&1&0&0\\ -1&0&1&0\\ -1&0&0&1 \end{pmatrix}.

For \(\mathbf{A}\), the vectors \((\sqrt{3},1,1,1)^T\) and \((-\sqrt{3},1,1,1)^T\) have eigenvalues \(\sqrt{3}\) and \(-\sqrt{3}\): the center coordinate of the product is the sum of the three leaf coordinates, and each leaf coordinate of the product is the center coordinate. Any vector \((0,a,b,c)^T\) with \(a+b+c=0\) is sent to zero, since its center output is \(a+b+c\) and its leaf outputs are zero. This two-dimensional space gives two more eigenvalues, both zero.

For \(\mathbf{L}\), the constant vector has eigenvalue \(0\). Vectors \((0,a,b,c)^T\) with \(a+b+c=0\) have eigenvalue \(1\), because the center output is \(-(a+b+c)=0\) and the leaf outputs are \(a,b,c\). Finally, \((3,-1,-1,-1)^T\) has eigenvalue \(4\): its center output is \(3\cdot3-(-1-1-1)=12\), and each leaf output is \(-3-1=-4\). The spectra are therefore \(\sqrt{3},-\sqrt{3},0,0\) for \(\mathbf{A}\), and \(0,1,1,4\) for \(\mathbf{L}\).

Check: the adjacency eigenvalues sum to \(\sqrt{3}-\sqrt{3}=0\), matching the trace of \(\mathbf{A}\). The Laplacian eigenvalues sum to \(0+1+1+4=6\), equal to the diagonal sum \(3+1+1+1=6\).

What the Laplacian’s Zero Eigenvalues Tell Us

The Laplacian does more than record degrees and adjacencies: its zero eigenvalues detect connected components. A component is a maximal set of vertices in which every pair is joined by a path. The following result includes isolated vertices as components.

Theorem: If \(G\) has \(n\) vertices and \(c\) connected components, then the nullspace of \(\mathbf{L}(G)\) has dimension \(c\). In particular, for a nonempty graph, \(G\) is connected if and only if zero is a Laplacian eigenvalue of multiplicity one.

Proof. For a real vector \(x=(x_v)_{v\in V}\), expand using \(\mathbf{L}=\mathbf{D}-\mathbf{A}\). Each edge \(uv\) contributes \(x_u^2+x_v^2\) from the degree terms and \(-2x_ux_v\) from the adjacency terms. Hence \(x^T\mathbf{L}x=\sum_{uv\in E}(x_u-x_v)^2\). Every term is nonnegative, so \(\mathbf{L}\) has no negative eigenvalue: if \(\mathbf{L}x=\lambda x\) for a nonzero real eigenvector, then \(\lambda x^Tx=x^T\mathbf{L}x\geq0\), and \(x^Tx>0\).

Now suppose \(\mathbf{L}x=0\). Then \(x^T\mathbf{L}x=0\), so the sum of squares is zero, forcing \(x_u=x_v\) on every edge \(uv\). Along any path, these equalities imply that \(x\) is constant on that component. Conversely, if \(x\) is constant on each component, then every vertex has the same value as each of its neighbors, and \((\mathbf{L}x)_v=\deg(v)x_v-\sum_{u:\,uv\in E}x_u=0\); this also holds for an isolated vertex, whose degree and neighbor sum are both zero. Therefore the nullspace consists exactly of vectors constant on each component. The indicator vectors of the \(c\) components form a basis for this space, so its dimension is \(c\). Since \(\mathbf{L}\) is real symmetric, its eigenvalue multiplicities agree with the dimensions of its eigenspaces. For a nonempty graph, \(c=1\) exactly when the zero eigenvalue has multiplicity one. \(\square\)

Worked Example: A Disconnected Graph with Isolated Vertices

Let \(G=(V,E)\) have \(V=\{1,2,3,4\}\), \(E=\{12\}\), in order \(1,2,3,4\). Vertices \(3\) and \(4\) are isolated, so the components are \(\{1,2\}\), \(\{3\}\), and \(\{4\}\). The degrees are \(1,1,0,0\), giving

\mathbf{A}= \begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{pmatrix}, \qquad \mathbf{L}= \begin{pmatrix} 1&-1&0&0\\ -1&1&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{pmatrix}.

The vectors \((1,1,0,0)^T\) and \((1,-1,0,0)^T\) are adjacency eigenvectors with eigenvalues \(1\) and \(-1\). The coordinate vectors \((0,0,1,0)^T\) and \((0,0,0,1)^T\) have eigenvalue \(0\). Thus the adjacency eigenvalues are \(1,-1,0,0\). For the Laplacian, the same first two vectors have eigenvalues \(0\) and \(2\); the two coordinate vectors for the isolated vertices have eigenvalue \(0\). Its eigenvalues are therefore \(0,0,0,2\).

Check: the Laplacian has three zero eigenvalues, matching the three components. Its row sums are all zero, including the rows for the isolated vertices; those rows are zero because isolated vertices have degree zero.

Common Mistake: Putting Degrees in the Adjacency Matrix

For the path with edges \(12,23\), a mistaken construction might put the degrees on the diagonal of \(\mathbf{A}\), producing \(\begin{pmatrix}1&1&0\\1&2&1\\0&1&1\end{pmatrix}\). This is not the adjacency matrix: the graph has no loops, so its diagonal entries must all be zero. The degrees belong in \(\mathbf{D}\), not \(\mathbf{A}\). Subtracting the correct adjacency matrix from \(\mathbf{D}=\operatorname{diag}(1,2,1)\) gives \(\mathbf{L}=\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}\), whose row sums are zero as required. A useful check is therefore to verify separately that the adjacency diagonal is zero for a simple graph and that the Laplacian row sums are zero.

These calculations illustrate two complementary checks on graph matrices. The entries of \(\mathbf{A}^k\) answer specific walk-counting questions, while the Laplacian’s zero eigenvalue multiplicity recovers the number of components. Eigenvalues should be checked against the matrix itself—for example, by applying it to proposed eigenvectors—and against simple invariants such as the trace, which is the sum of the diagonal entries and also the sum of the eigenvalues counted with multiplicity.

Check Your Understanding

Use an explicit vertex order whenever you write a matrix, and check your computations by multiplying or applying the matrix.

For the graph \(V=\{1,2,3\}\), \(E=\{12,13\}\), write \(\mathbf{A}\), \(\mathbf{D}\), and \(\mathbf{L}\) in order \(1,2,3\).
In the path example, what does the \((1,1)\) entry of \(\mathbf{A}^2\) count? List the corresponding walk or walks.
For the triangle, verify directly that \((1,-1,0)^T\) is an adjacency eigenvector, and give its eigenvalue.
How many zero eigenvalues does the Laplacian have for a graph consisting of two disjoint edges and one isolated vertex?
Explain why the Laplacian of a simple graph has nonnegative eigenvalues using the sum-of-squares identity.