---
title: "Adjacency, Incidence and Laplacian"
summary: Three matrices for one graph, what each row/column product means, and the properties you can read off in O(1).
difficulty: core
tags: [matrix, spectrum, invariants]
prereq: [foundations/representation]
see: [matrices/walks-powers, matrices/matrix-tree, special/coloring]
---

:::definition label="The three matrices"
For a simple graph on $V = \{1, \dots, n\}$:
- **adjacency** $A \in \{0,1\}^{n \times n}$, $A_{ij} = 1 \iff ij \in E$. Symmetric, zero diagonal, $\deg(i) = \sum_j A_{ij}$.
- **incidence** $B \in \{0,1\}^{n \times m}$ (undirected: $B_{ie} = 1$ iff $i$ is an endpoint of $e$) or $\{-1, 0, 1\}$ for digraphs, with $-1$ at the tail.
- **Laplacian** $L = D - A$, where $D = \operatorname{diag}(\deg)$. Equivalently $L = B B^{\mathsf T}$ for the oriented incidence matrix.
:::

:::props title="What each one is for"
- $A$: walk counting, spectra, "is there an edge" queries (@matrices/walks-powers), and the semiring DP of @shortest/floyd-warshall,
- $B$: cuts and flows — a column has exactly one $-1$ and one $+1$, so the *flow conservation* equations are $B x = 0$ and a *cut* is a row-space projection,
- $L$: everything involving spanning trees, random walks, and connectivity — $x^{\mathsf T} L x = \sum_{uv \in E} (x_u - x_v)^2 \ge 0$, so $L \succeq 0$ always.
:::

:::theorem title="The Laplacian's kernel tells you the components"
$\operatorname{rank}(L) = n - c$, where $c$ is the number of connected components, and $\ker L$ is spanned by the component indicator vectors.
:::

:::proof
$x^{\mathsf T} L x = \sum_{uv \in E}(x_u - x_v)^2 = 0 \iff x$ is constant on every edge, hence constant on each component; so $\ker L$ has dimension exactly $c$. ∎
:::

That one line is the reason the *second-smallest* eigenvalue of $L$ ($\lambda_2$, the **algebraic connectivity** / Fiedler value) measures how well connected $G$ is: $\lambda_2 > 0 \iff$ connected, and Cheeger's inequality $2\sqrt{\lambda_2} \ge h \ge \lambda_2/2$ ties it to the sparsest cut — which is the theoretical basis of spectral clustering and of "the Fiedler vector splits the graph well".

:::note title="Signed vs unsigned incidence"
With $B \in \{0,1\}^{n\times m}$ (no signs), $BB^{\mathsf T} = A + D$ — not $L$. The signs are what make $L = BB^{\mathsf T}$ work, and they are also what make the flow equations exact. For bipartite graphs the unsigned version equals $\begin{pmatrix} 0 & M \\ M^{\mathsf T} & 0\end{pmatrix}$-style structure that makes matching arguments transparent (@matching/intro).
:::

## Reading properties off A in O(1)-ish
:::example title="Common neighbours, triangles, degree sequence"
```cpp bitset-adj.cpp
const int MAXN = 5000;
bitset<MAXN> adj[MAXN];
int common(int u, int v) { return (adj[u] & adj[v]).count(); }   // O(n/64)
ll triangles() {                                                  // O(n^3/64)
    ll t = 0;
    for (int u = 0; u < n; u++)
        for (int v : g[u]) if (v > u) t += (adj[u] & adj[v] & gt[v]).count();
    return t / 3;                                        // each triangle found at all 3 vertices
}
```
$\operatorname{tr}(A^3) = 6 \cdot (\#$triangles) in a simple graph, and more generally $\operatorname{tr}(A^k) = \sum_i \lambda_i^k$ counts closed walks, which is how one proves two graphs with different spectra are non-isomorphic (@trees/properties).
:::

:::figure src="AdjacencyMatrix.png" caption="The adjacency matrix of a small graph: symmetric, 0–1, row sums = degrees. Block structure visible = a candidate for bipartition or for a quotient matrix."
:::

## Quotient matrices, an underrated tool
If the partition $V = V_1 \sqcup \dots \sqcup V_k$ is *equitable* (every vertex of $V_i$ has the same number $b_{ij}$ of neighbours in $V_j$), then the $k \times k$ matrix $B = (b_{ij})$ has the property that the largest eigenvalue of $B$ equals that of $A$, and eigenvectors of $B$ lift to $A$-eigenvectors constant on the parts. This is how one computes spectra of distance-regular graphs, Johnson graphs and the hypercube $Q_n$ (whose quotient is the path with self-loops on $0..n$) in three lines instead of $2^n$.

:::problems
- [[CSES 2138]] Reachable Nodes | https://cses.fi/problemset/task/2138 | hard | transitive closure as a bitset DP
- [[CSES 1134]] Prüfer Code | https://cses.fi/problemset/task/1134 | core | degree sequences from a matrix-free encoding
:::