From Edges to Matrices
An adjacency matrix records which vertices are joined, and, in a weighted network, the strength of each connection. Two further matrices organize this information in useful ways: the degree matrix records the total connection weight at each vertex, while the graph Laplacian combines degrees and adjacencies. The Laplacian can therefore be constructed directly from edge data and used to measure how a vector of values changes across the network.
Throughout, consider a finite undirected graph with vertices labelled \(1,\dots,n\), no self-loops, and nonnegative edge weights. Write \(w_{ij}\) for the weight of the edge between vertices \(i\) and \(j\), and set \(w_{ij}=0\) when there is no edge. Undirectedness means \(w_{ij}=w_{ji}\), and the absence of self-loops means \(w_{ii}=0\). An unweighted graph is the special case in which every edge has weight \(1\). If a network description has several edges between the same pair of vertices, their weights can be added and recorded as one value \(w_{ij}\).
In an unweighted graph, \(d_i\) is the number of edges incident to vertex \(i\). In a weighted graph it is the sum of their weights, not merely the number of neighbors. Because there are no self-loops, \(a_{ii}=0\). The symmetry \(w_{ij}=w_{ji}\) makes both \(\mathbf{A}\) and \(\mathbf{L}\) symmetric.
Reading the Entries of the Laplacian
Proof. By definition, \(\mathbf{L}=\mathbf{D}-\mathbf{A}\). On the diagonal, \(d_{ii}=d_i\) and \(a_{ii}=w_{ii}=0\), so \(l_{ii}=d_i-a_{ii}=d_i\). If \(i\ne j\), the degree matrix has \(d_{ij}=0\), while \(a_{ij}=w_{ij}\). Hence \(l_{ij}=d_{ij}-a_{ij}=0-w_{ij}=-w_{ij}\). \(\square\)
These entry formulas give a direct construction rule. First total the edge weights at each vertex and place those totals on the diagonal. Then, for every edge between distinct vertices \(i\) and \(j\), put the negative of its weight in both positions \((i,j)\) and \((j,i)\). Put zero in the other off-diagonal positions.
The action of the Laplacian on a vector also has a useful edge-based interpretation. If \(\mathbf{x}=(x_1,\dots,x_n)^{\top}\), then the \(i\)th component of \(\mathbf{L}\mathbf{x}\) is a weighted sum of differences between the value at vertex \(i\) and the values at its neighbors.
Proof. The \(i\)th component of \(\mathbf{D}\mathbf{x}\) is \(d_i x_i\), and the \(i\)th component of \(\mathbf{A}\mathbf{x}\) is \(\sum_{j=1}^{n}w_{ij}x_j\). Therefore \((\mathbf{L}\mathbf{x})_i=d_i x_i-\sum_{j=1}^{n}w_{ij}x_j\). Substitute the definition \(d_i=\sum_{j=1}^{n}w_{ij}\) and distribute \(x_i\): \( (\mathbf{L}\mathbf{x})_i=\sum_{j=1}^{n}w_{ij}x_i-\sum_{j=1}^{n}w_{ij}x_j=\sum_{j=1}^{n}w_{ij}(x_i-x_j)\). This proves the formula for every index \(i\). \(\square\)
Thus \((\mathbf{L}\mathbf{x})_i\) compares the value at vertex \(i\) with values at adjacent vertices, weighting each difference by the corresponding edge weight. A large edge weight gives that edge’s difference more influence in the sum. A vertex with no incident edges has degree zero, a zero row in \(\mathbf{L}\), and a zero component in \(\mathbf{L}\mathbf{x}\) for every \(\mathbf{x}\).
Paths and Cycles
Worked Example: The Path on Four Vertices
Consider the unweighted path with edges \(1\)--\(2\), \(2\)--\(3\), and \(3\)--\(4\). The degrees are \(d_1=1\), \(d_2=2\), \(d_3=2\), and \(d_4=1\). The adjacency and degree matrices are
Subtracting entry by entry gives the Laplacian:
For \(\mathbf{x}=(1,2,0,-1)^{\top}\), multiplication gives
Check: the edge-difference formula gives \((1-2,\ (2-1)+(2-0),\ (0-2)+(0-(-1)),\ -1-0)^{\top}=(-1,3,-1,-1)^{\top}\), agreeing with the matrix product. The rows of \(\mathbf{L}\) each sum to zero.
Worked Example: The Cycle on Four Vertices
Now add the edge \(4\)--\(1\) to make a four-vertex cycle. Every vertex has degree \(2\). The two neighbors of each vertex determine its off-diagonal entries, so
Take \(\mathbf{x}=(1,0,2,1)^{\top}\). Multiplying each row by \(\mathbf{x}\) gives
Check: using edge differences, the four components are \( (1-0)+(1-1)=1\), \( (0-1)+(0-2)=-3\), \( (2-0)+(2-1)=3\), and \( (1-2)+(1-1)=-1\). They match the matrix product.
Comparing these examples shows how the graph structure changes the degree matrix as well as the off-diagonal pattern. In the path, the two endpoint vertices have degree \(1\); in the cycle, every vertex has degree \(2\). The diagonal entries change accordingly, while the negative off-diagonal entries record exactly which pairs are joined.
Constructing a Weighted Laplacian
Worked Example: A Small Weighted Network
Consider four vertices and the weighted edges \(1\)--\(2\) of weight \(2\), \(1\)--\(3\) of weight \(1\), \(2\)--\(3\) of weight \(2\), \(2\)--\(4\) of weight \(2\), and \(3\)--\(4\) of weight \(4\). The vertex degrees, found by adding incident weights, are \(d_1=2+1=3\), \(d_2=2+2+2=6\), \(d_3=1+2+4=7\), and \(d_4=2+4=6\).
Placing the weights in the adjacency matrix and the degrees on the diagonal gives
Subtracting \(\mathbf{A}\) from \(\mathbf{D}\) gives
For \(\mathbf{x}=(1,0,2,1)^{\top}\), calculate each component directly:
Check: the edge-difference formula gives \(2(1-0)+(1-2)=1\) at vertex \(1\); \(2(0-1)+2(0-2)+2(0-1)=-8\) at vertex \(2\); \((2-1)+2(2-0)+4(2-1)=9\) at vertex \(3\); and \(2(1-0)+4(1-2)=-2\) at vertex \(4\). These are exactly the entries of \(\mathbf{L}\mathbf{x}\).
Two Useful Identities
The entry formulas imply that every row sum of a graph Laplacian is zero: row \(i\) contains \(d_i\) on the diagonal and off-diagonal entries whose sum is \(-\sum_{j\ne i}w_{ij}=-d_i\). Equivalently, if \(\mathbf{1}=(1,\dots,1)^{\top}\), then \(\mathbf{L}\mathbf{1}=\mathbf{0}\). This is also consistent with the edge-difference formula, since a constant value has zero difference across every edge.
Proof. Since \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), the diagonal part of \(\mathbf{x}^{\top}\mathbf{D}\mathbf{x}\) is \(\sum_i d_i x_i^2\). The adjacency part is \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=\sum_{i,j}w_{ij}x_ix_j\). Group the terms by undirected edges. An edge \(\{i,j\}\) of weight \(w_{ij}\) contributes \(w_{ij}x_i^2+w_{ij}x_j^2\) to \(\sum_i d_i x_i^2\), because its weight is included in both endpoint degrees. It contributes \(w_{ij}x_ix_j+w_{ji}x_jx_i=2w_{ij}x_ix_j\) to \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\), since \(w_{ji}=w_{ij}\). Its total contribution to the difference is therefore \(w_{ij}x_i^2+w_{ij}x_j^2-2w_{ij}x_ix_j=w_{ij}(x_i-x_j)^2\). Summing this equality over all undirected edges proves the identity. \(\square\)
Because every weight is nonnegative and every square is nonnegative, the identity also shows that \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}\ge0\). For the weighted example, the edge contributions for \(\mathbf{x}=(1,0,2,1)^{\top}\) are \(2(1-0)^2=2\), \(1(1-2)^2=1\), \(2(0-2)^2=8\), \(2(0-1)^2=2\), and \(4(2-1)^2=4\), with total \(17\). The matrix product above gives \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}=1(1)+0(-8)+2(9)+1(-2)=17\), as required.
Common Mistake: Degrees and Signs
A common error is to put the positive edge weight in an off-diagonal position of \(\mathbf{L}\), or to use the number of neighbors in place of the weighted degree. For example, in the weighted network above, vertex \(2\) has degree \(6\), not degree \(3\): its three incident weights are \(2,2,2\). A mistaken row such as \(\begin{bmatrix}2&6&2&2\end{bmatrix}\) uses the wrong diagonal and the wrong off-diagonal signs. The correct row is \(\begin{bmatrix}-2&6&-2&-2\end{bmatrix}\), because the diagonal is the total incident weight and each off-diagonal entry is the negative of the edge weight.
A reliable construction check is to verify both symmetry and zero row sums. These checks do not replace tracing each edge and degree, but they quickly expose many sign or bookkeeping errors. For an undirected graph, the Laplacian must be symmetric; for every vertex, its diagonal degree must cancel the negative weights in the rest of its row.
Check Your Understanding
For each question, state the edge or degree information used, not just the final matrix.
- Construct \(\mathbf{D}\) and \(\mathbf{L}\) for the unweighted path on vertices \(1,2,3\), with edges \(1\)--\(2\) and \(2\)--\(3\).
- A weighted graph has an edge of weight \(3\) between vertices \(1\) and \(2\), and an edge of weight \(2\) between vertices \(2\) and \(3\), with no other edges. What are the degrees and the Laplacian?
- For a four-vertex cycle, calculate \(\mathbf{L}\mathbf{x}\) when \(\mathbf{x}=(0,1,1,0)^{\top}\).
- Explain why the off-diagonal entry \(l_{ij}\) is zero when vertices \(i\) and \(j\) are not connected by an edge.
- Use the quadratic-form identity to calculate \(\mathbf{x}^{\top}\mathbf{L}\mathbf{x}\) for the unweighted path \(1\)--\(2\)--\(3\) and \(\mathbf{x}=(2,0,1)^{\top}\).
