Incidence Matrices

From the Fibonacci matrix to graph topology: how a table of 0s and 1s encodes every cycle, every tree, and every boundary in a network.

A prerequisite for quantum error correction

01 Why Matrices? The Fibonacci Example

The Fibonacci sequence \(0, 1, 1, 2, 3, 5, 8, 13, \ldots\) is defined by the recurrence \(F_{n+1} = F_n + F_{n-1}\). This is a rule that takes two numbers and produces the next. We can write it as a matrix multiplication:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$$

Call this the Fibonacci matrix \(Q\). Repeated application gives \(Q^n\) acting on the initial state. The matrix packages two things at once: the rule (top row: add the two inputs) and the memory (bottom row: pass the first input through unchanged).

Fibonacci Matrix PowersQn
Q¹ = [[1,1],[1,0]]. det(Q) = −1.

The determinant as an invariant

The determinant of \(Q\) is \(1 \cdot 0 - 1 \cdot 1 = -1\). Since the determinant is multiplicative, \(\det(Q^n) = (-1)^n\). Written out, this says:

$$F_{n+1}\, F_{n-1} \;-\; F_n^2 \;=\; (-1)^n$$

This is Cassini's identity. The determinant tells you that adjacent Fibonacci numbers are always coprime (their greatest common divisor is 1), because the identity shows a linear combination equalling \(\pm 1\).

The lesson. A matrix is not just a grid of numbers. It encodes a transformation, and its determinant is a conserved quantity under that transformation. The Fibonacci matrix preserves (signed) area. We now ask: what transformation does a graph encode?

02 Graphs and the Adjacency Matrix

A graph is a set of vertices (nodes) connected by edges. The simplest matrix encoding is the adjacency matrix \(A\): an \(n \times n\) matrix where \(A_{ij} = 1\) if vertex \(i\) is connected to vertex \(j\), and \(0\) otherwise. For an undirected graph, \(A\) is symmetric.

Graph ↔ Adjacency MatrixClick vertices to toggle edges
Triangle: 3 vertices, 3 edges.

The adjacency matrix tells you which vertices are neighbours. Its powers count walks: \((A^k)_{ij}\) is the number of walks of length \(k\) from vertex \(i\) to vertex \(j\). But it conflates two different objects (vertices and edges) into one matrix. To separate them, we need a different matrix.

03 The Incidence Matrix

The incidence matrix \(B\) is a rectangular matrix with one row per vertex and one column per edge. Entry \(B_{v,e} = 1\) if vertex \(v\) is an endpoint of edge \(e\), and \(0\) otherwise.

$$B \;\in\; \{0,1\}^{|V| \times |E|}, \qquad B_{v,e} = \begin{cases} 1 & \text{if } v \in \partial e \\ 0 & \text{otherwise} \end{cases}$$

This matrix is honest about what a graph actually is: a relationship between two different kinds of object (vertices and edges). Each column has exactly two 1s, because every edge has exactly two endpoints. Each row has as many 1s as the degree of that vertex.

Incidence Matrix BuilderSelect a graph
Each column has exactly two 1s. Each row count = vertex degree.

Recovering adjacency from incidence

The adjacency and incidence matrices are related. Over the real numbers:

$$B\, B^\top = D + A$$

where \(D\) is the diagonal degree matrix. The combination \(L = D - A = B\, B^\top - 2A\) is the graph Laplacian, fundamental to spectral graph theory, diffusion, and network analysis.

04 The Kernel: Where Cycles Live

Now the key insight. Think of a vector \(\mathbf{c} \in \{0,1\}^{|E|}\) as a selection of edges (1 = selected, 0 = not). Apply the incidence matrix over \(\mathbb{F}_2\) (arithmetic mod 2):

$$B\, \mathbf{c} = \mathbf{0} \quad (\text{mod } 2) \qquad \Longleftrightarrow \qquad \mathbf{c} \text{ is a cycle}$$

Why? The product \(B \mathbf{c}\) gives, at each vertex, the number of selected edges incident to that vertex, reduced mod 2. This is zero at every vertex precisely when every vertex in the subgraph has even degree. A subgraph where every vertex has even degree is a union of cycles.

Cycle DetectorToggle edges, check if the selection is a cycle
Click edges to select them. The boundary Bc (mod 2) is shown at each vertex.

The set of all cycles forms a vector space over \(\mathbb{F}_2\): if \(\mathbf{c}_1\) and \(\mathbf{c}_2\) are cycles, so is their symmetric difference \(\mathbf{c}_1 + \mathbf{c}_2\) (mod 2). The dimension of this cycle space is:

$$\dim \ker(B) = |E| - |V| + k$$

where \(k\) is the number of connected components. For a connected graph, this is \(|E| - |V| + 1\). Every independent cycle corresponds to one "extra" edge beyond what a spanning tree needs.

The Matrix-Tree theorem. Delete any one row from \(B\), forming the reduced incidence matrix \(\tilde{B}\). Then \(\det(\tilde{B}\tilde{B}^\top)\) equals the number of spanning trees of the graph. For the triangle: \(\det = 3\) (three spanning trees). For \(K_4\): \(\det = 16\). The determinant counts trees, just as the Fibonacci determinant counted... well, \(\pm 1\). Both are topological invariants extracted from matrix algebra.

05 The Boundary Operator and \(\partial^2 = 0\)

Rename the incidence matrix: call it \(\partial_1\) (the boundary operator on 1-chains). A "1-chain" is a formal sum of edges. The boundary operator maps each edge to the sum of its two endpoints. Over \(\mathbb{F}_2\), "sum" means XOR.

If the graph is the 1-skeleton of a surface (a mesh of faces), there is a second operator \(\partial_2\) mapping each face to its boundary edges. The composition satisfies:

$$\partial_1 \circ \partial_2 = 0$$

In matrix language, \(B \cdot \partial_2 = 0\) mod 2. This is because every face boundary is a cycle, and cycles are in the kernel of \(\partial_1\) by definition.

Chain Complex Visualiserfaces → edges → vertices
Click a face. Its boundary edges light up. Apply ∂₁ to see the vertex boundary vanish.
Why this matters for quantum error correction. In the surface code, data qubits live on edges, Z-stabilisers are face boundaries (\(\text{im}(\partial_2)\)), and X-stabilisers live on the dual lattice. The condition that stabilisers commute is \(\partial^2 = 0\). The logical operators are cycles that are not boundaries: the homology group \(H_1 = \ker(\partial_1) / \text{im}(\partial_2)\). The entire error correction scheme is the linear algebra of the incidence matrix over \(\mathbb{F}_2\).

Summary of the chain

The conceptual path we have followed:

Fibonacci matrix → a matrix encodes a rule; its determinant is an invariant
Adjacency matrix → encodes vertex-vertex connectivity, but conflates vertices and edges
Incidence matrix → honestly separates vertices and edges; each column has exactly two 1s
Kernel over \(\mathbb{F}_2\) → cycles are edge-sets with vanishing boundary
Boundary operator → \(\partial_1\) on a mesh; face boundaries are automatically cycles (\(\partial^2 = 0\))
Homology → cycles that are not boundaries = topological information = logical qubits

06 Fibonacci Matrices, Binet, and Field Extensions

We began with the Fibonacci matrix \(Q = \begin{pmatrix}1&1\\1&0\end{pmatrix}\) as a motivating example: its determinant is an invariant (\(-1\) at every power), and its characteristic polynomial \(\lambda^2 - \lambda - 1\) has roots \(\phi, \hat\phi\) (the golden ratio and its conjugate). These roots give Binet's formula \(F_n = \frac{\phi^n - \hat\phi^n}{\sqrt{5}}\) directly from diagonalisation. But the Fibonacci matrix has a richer algebraic life that connects back to everything we have built.

Complex Fibonacci matrices

Consider replacing the off-diagonal 1s in the Fibonacci matrix with \(i\). The complex matrix \(M^{(2)} = \begin{pmatrix}1&i\\i&1\end{pmatrix}\) has determinant \(1 - i^2 = 2 = F_3\). Its characteristic polynomial is \(\lambda^2 - 2\lambda + 2\) with eigenvalues \(1 \pm i \in \mathbb{Q}(i)\).

Extending to \(n \times n\) tridiagonal matrices with 1s on the diagonal and \(mi\) on the off-diagonals (where \(m\) is the metallic number), the determinant always yields the next Fibonacci number:

$$\det(J_n) = \prod_k \lambda_k = F_{n+1}$$
Complex Fibonacci Eigenvaluesdet(Jₙ) = Fₙ₊₁
Eigenvalues of the n×n complex Fibonacci matrix, plotted in the complex plane.

The field extension hierarchy

The eigenvalues of each \(J_n\) live in progressively richer algebraic extensions of \(\mathbb{Q}\):

\(n = 2\): eigenvalues \(1 \pm i \in \mathbb{Q}(i)\), \(\quad\det = 2\)
\(n = 3\): eigenvalues \(1, \; 1 \pm \sqrt{2}\,i \in \mathbb{Q}(i, \sqrt{2})\), \(\quad\det = 3\)
\(n = 4\): eigenvalues \(1 \pm \tfrac{i}{\sqrt{2}}\phi, \; 1 \pm \tfrac{i}{\sqrt{2}}\hat\phi \in \mathbb{Q}(i, \sqrt{2}, \sqrt{5})\), \(\quad\det = 5\)
\(n = 5\): eigenvalues include \(1 \pm i, \; 1 \pm \sqrt{3}\,i \in \mathbb{Q}(i, \sqrt{3})\), \(\quad\det = 8\)
\(n = 7\): eigenvalues include \(1 \pm \sqrt{2}\,i, \; 1 \pm i\sqrt{2 \pm \sqrt{2}} \in \mathbb{Q}(i, \sqrt{2}, \sqrt{2-\sqrt{2}})\), \(\quad\det = 21\)

Smaller eigenvalue sets nest inside larger ones: the eigenvalues of \(J_2\) appear in \(J_5\), those of \(J_3\) in \(J_7\), and all appear in \(J_{11}\). For prime \(n\), the eigenvalue structure is simpler (fewer nested radicals); for composite \(n\), the expressions become more opaque.

Primes splitting in field extensions. The integer 2 splits as \((1+i)(1-i)\) in \(\mathbb{Z}[i]\). The integer 3 remains inert in \(\mathbb{Z}[i]\) but splits in \(\mathbb{Q}(i, \sqrt{2})\). The eigenvalue products \(\det(J_n) = F_{n+1}\) thus exhibit the arithmetic of algebraic number fields: each Fibonacci number factorises into conjugate pairs of algebraic integers, and the factorisation type (split, inert, ramified) depends on the field extension required.

Connection to graph invariants

The characteristic polynomial of the adjacency matrix encodes the graph spectrum, and its coefficients count subgraph structures. The characteristic polynomial of the complex Fibonacci matrix plays an analogous role: its coefficients (Table 1 in the paper) encode Fibonacci combinatorics, and its roots live in field extensions whose Galois groups capture the symmetry of the factorisation.

The Tutte polynomial of a graph generalises the characteristic polynomial and encodes the Potts partition function. The complex Fibonacci eigenvalues generalise Binet's formula and encode the factorisation of \(F_{n+1}\) as a product of algebraic integers. Both are instances of the same principle: the determinant of a structured matrix, decomposed via its characteristic polynomial, reveals the arithmetic and topology of the system it encodes.

The invariant thread. Fibonacci determinant (\(\det Q^n = (-1)^n\)) → complex Fibonacci determinant (\(\det J_n = F_{n+1}\)) → graph Laplacian determinant (= spanning tree count) → Tutte polynomial (= universal graph invariant) → Potts partition function (= error correction threshold). The determinant, in each case, is the bridge between algebra and topology.