Oriented Incidence Matrices And Laplacian Factorization

From Edge Directions to a Matrix

The graph Laplacian records vertex degrees on its diagonal and adjacency with negative signs off the diagonal. An oriented incidence matrix records the same edge data in a different way: each column corresponds to one edge, with a negative entry at its tail and a positive entry at its head. Multiplying this matrix by its transpose combines the information in the edge columns. We will show exactly why the result is the Laplacian, and why the arbitrary choices of edge directions do not affect it.

Throughout, graphs are finite and simple. An orientation here means choosing a direction for each edge of an undirected graph; it is a device for constructing a matrix, not a claim that the graph itself is directed. Fix an ordering \(v_1,\dots,v_n\) of the vertices and an ordering \(e_1,\dots,e_m\) of the edges. If an edge \(e_j=uv\) is oriented from \(u\) to \(v\), then \(u\) is its tail and \(v\) its head.

Thus every edge column has exactly two nonzero entries: one \(-1\) and one \(1\). The convention that the tail receives \(-1\) and the head receives \(1\) is fixed throughout. Other sign conventions can also be used, but the definition and calculations must use one consistently. The factorization in this tutorial uses \(B B^{\mathsf T}\), an \(n\) by \(n\) matrix, because \(B\) has \(n\) rows and \(m\) columns.

Why the Product Is the Laplacian

Proof. Let \(x\) and \(y\) be vertices. By matrix multiplication, the \((x,y)\) entry of \(B B^{\mathsf T}\) is \((B B^{\mathsf T})_{x,y}=\sum_{e\in E} B_{x,e}B_{y,e}\). If \(x=y\), an edge contributes \(1\) to this sum exactly when it is incident with \(x\): its entry in row \(x\) is either \(1\) or \(-1\), whose square is \(1\). Every other edge contributes \(0\). Hence \((B B^{\mathsf T})_{x,x}=\deg(x)=D_{x,x}-A_{x,x}\), since a simple graph has no loops and therefore \(A_{x,x}=0\).

Now suppose \(x\ne y\). An edge contributes a nonzero term only if it is incident with both \(x\) and \(y\). Since the graph is simple, there is at most one such edge. If \(xy\notin E\), the sum is \(0\). If \(xy\in E\), the column for \(xy\) has entries \(1\) and \(-1\) in rows \(x\) and \(y\), in one order or the other. Their product is \(-1\), so \((B B^{\mathsf T})_{x,y}=-1\). This equals \(D_{x,y}-A_{x,y}\), because \(D_{x,y}=0\) for distinct vertices and \(A_{x,y}\) is \(1\) exactly when \(xy\in E\). Thus every entry of \(B B^{\mathsf T}\) equals the corresponding entry of \(D-A\), proving the result. If \(m=0\), the product is the \(n\) by \(n\) zero matrix, and \(D-A\) is also zero. If \(n=0\), both sides are the empty \(0\) by \(0\) matrix. \(\square\)

The proof gives a useful way to remember the signs: an edge contributes \(1\) to each of its endpoint diagonal entries, and \(-1\) to the two off-diagonal entries connecting its endpoints. All other entries from that edge are zero.

Proof. Reversing one edge changes its column from \(b\) to \(-b\). The contribution of that column to the product is unchanged, since \((-b)(-b)^{\mathsf T}=b b^{\mathsf T}\). Reversing any collection of edges changes the signs of the corresponding columns, and each such column contributes the same matrix as before. The sum of the column contributions, which is \(B B^{\mathsf T}\), therefore remains unchanged. This argument also covers the empty collection of reversals. \(\square\)

Consequently, there is no preferred orientation needed for the factorization. The matrix \(B\) itself depends on the chosen directions, but its product with its transpose does not. The order of vertices and edges affects how rows and columns are written; it does not alter the entry-by-entry identity, provided the same vertex order is used for \(B B^{\mathsf T}\) and \(L\).

Worked Matrix Calculations

A Common Sign Error

A frequent mistake is to put \(1\) at both endpoints of every edge and then use the resulting matrix in place of the oriented incidence matrix. That construction is an unsigned incidence matrix; its product has the wrong signs off the diagonal for the graph Laplacian.

For a concrete calculation, take the path with \(V=\{1,2,3\}\), \(E=\{12,23\}\). If both endpoints receive \(1\), the matrix is \(C=\begin{pmatrix}1&0\\1&1\\0&1\end{pmatrix}\). Its row products give \(C C^{\mathsf T}=\begin{pmatrix}1&1&0\\1&2&1\\0&1&1\end{pmatrix}\): for example, rows \(1\) and \(2\) have product \(1\cdot1+0\cdot1=1\). But the Laplacian is \(\begin{pmatrix}1&-1&0\\-1&2&-1\\0&-1&1\end{pmatrix}\), with negative entries at adjacent pairs. The correction is to orient the edges and use \(B=\begin{pmatrix}-1&0\\1&-1\\0&1\end{pmatrix}\). Its first and second rows have product \((-1)\cdot1+0\cdot(-1)=-1\), and its second and third rows have product \(1\cdot0+(-1)\cdot1=-1\); the diagonal row products are \(1,2,1\). Hence \(B B^{\mathsf T}\) is the Laplacian. The signs in the incidence columns are essential.

Why the Factorization Is Useful

The factorization expresses the Laplacian using columns that correspond directly to edges. It turns a vertex-indexed matrix into a sum of contributions, one per edge: the column for an edge has nonzero entries only at its endpoints. This local description is useful in algebraic graph theory, where properties of the Laplacian are studied through matrix calculations. The factorization also separates two facts that are easy to conflate: the incidence matrix depends on the arbitrary edge orientations, while the Laplacian does not.

For any graph, including a disconnected graph or one with isolated vertices, the same entrywise proof applies. Each diagonal entry counts incident edges, each adjacent pair contributes a negative off-diagonal entry, and nonadjacent pairs contribute zero. No connectedness assumption is needed. The next step in studying this factorization is to examine what happens when it is placed inside a quadratic expression; that leads to an interpretation in terms of edge energy.