1. Linear Algebra for Graph Theory
Graphs can be studied visually, but computers analyze them algebraically. By translating a graph into a matrix, we unlock linear algebra algorithms that can count paths, detect disconnected clusters, partition data, and calculate page rankings in sub-second execution times.
Vectors, Matrices & Linear Transformations
A vector space $V$ over a field $\mathbb{R}$ is a set of objects (vectors) closed under addition and scalar multiplication. A basis is a linearly independent set of vectors that spans the space. The number of basis vectors defines the dimension.
A matrix $A \in \mathbb{R}^{m \times n}$ acts as a linear transformation mapping vectors from $\mathbb{R}^n$ to $\mathbb{R}^m$. Two fundamental subspaces associated with matrix $A$ are:
- Image (or Column Space): The space spanned by the column vectors of $A$. Its dimension is the rank of $A$.
- Kernel (or Null Space): The set of vectors $x$ satisfying $Ax = 0$. Its dimension is the nullity of $A$.
The Rank-Nullity Theorem bridges these dimensions for any $n$-column matrix:
$$\text{rank}(A) + \text{nullity}(A) = n$$
Eigenvalues, Eigenvectors & The Spectral Theorem
For an $n \times n$ square matrix $A$, a non-zero vector $v \in \mathbb{R}^n$ is an eigenvector with corresponding eigenvalue $\lambda \in \mathbb{R}$ if matrix multiplication simply scales $v$:
$$A v = \lambda v$$
Real-World Analogy: Think of a vibrating drumhead. While most initial strikes cause chaotic, multi-directional vibrations, certain fundamental frequencies cause the entire drum membrane to move uniformly up and down without changing its underlying wave shape. These pure fundamental standing waves are the eigenvectors, and their vibration frequencies correspond to the eigenvalues.
The Spectral Theorem for Real Symmetric Matrices
Because undirected graphs have mutual edges ($u \to v$ if and only if $v \to u$), their adjacency matrices are always symmetric ($A = A^T$). The Spectral Theorem guarantees that any real symmetric matrix $A \in \mathbb{R}^{n \times n}$ has:
1. Exactly $n$ real eigenvalues: $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n$.
2. An orthonormal basis of $n$ eigenvectors $\{v_1, v_2, \dots, v_n\}$ such that $v_i^T v_j = 0$ for $i \neq j$ and $v_i^T v_i = 1$.
This theorem guarantees that we can decompose complex graph matrices into orthogonal spatial components without introducing complex numbers or unstable basis vectors.
Key Insight: Graph Isomorphism & Spectral Invariance
Graph eigenvalues are basis-independent — relabeling the nodes of a graph permutes the rows and columns of its matrix ($P A P^T$), but leaves its eigenvalue multiset (its spectrum) completely unchanged. If two graphs have different spectra, they cannot be isomorphic!
Adjacency Matrix, Walk Counts & The Laplacian
For a graph $G = (V, E)$ with $n$ vertices, the Adjacency Matrix $A$ is an $n \times n$ matrix defined as:
$$A_{ij} = \begin{cases} 1 & \text{if } \{i, j\} \in E \\ 0 & \text{otherwise} \end{cases}$$
Counting Paths and Walks via Matrix Exponentiation
Theorem: The entry $(A^k)_{ij}$ of the $k$-th power of the adjacency matrix $A^k$ equals the exact number of distinct walks of length $k$ between vertex $i$ and vertex $j$.
Proof via Induction:
• Base Case ($k = 1$): $(A^1)_{ij} = A_{ij}$, which is $1$ if an edge (walk of length 1) exists between $i$ and $j$, and $0$ otherwise.
• Inductive Step: Assume $(A^k)_{ij}$ correctly counts length-$k$ walks. By matrix multiplication:
$$(A^{k+1})_{ij} = \sum_{m=1}^{n} (A^k)_{im} A_{mj}$$
A walk of length $k+1$ from $i$ to $j$ consists of a walk of length $k$ from $i$ to an intermediate neighbor $m$, followed by a step along edge $(m, j)$. Summing over all possible neighbors $m$ yields the exact count of length-$(k+1)$ walks. $\blacksquare$
Beyond the adjacency matrix, two other structural matrices are essential:
- Degree Matrix ($D$): A diagonal matrix where $D_{ii} = \deg(i)$ and $D_{ij} = 0$ for $i \neq j$.
- Graph Laplacian ($L$): Defined as $L = D - A$.
The Laplacian $L$ acts as a discrete differential operator. For a potential vector $x \in \mathbb{R}^n$ assigned to vertices, the quadratic form yields:
$$x^T L x = \sum_{\{i, j\} \in E} (x_i - x_j)^2$$
This quadratic form proves that $L$ is positive semi-definite (eigenvalues $\lambda_i \ge 0$). The multiplicity of eigenvalue $\lambda = 0$ equals the exact number of connected components in the graph!
Below is executable Python code calculating walk counts and matrix spectra using NumPy:
import numpy as np
# Define a 4-cycle graph A-B-C-D-A
# Nodes: 0:A, 1:B, 2:C, 3:D
A = np.array([
[0, 1, 0, 1], # Node A connected to B, D
[1, 0, 1, 0], # Node B connected to A, C
[0, 1, 0, 1], # Node C connected to B, D
[1, 0, 1, 0] # Node D connected to A, C
])
# 1. Walk Counts via Matrix Exponentiation
A_squared = np.linalg.matrix_power(A, 2)
A_cubed = np.linalg.matrix_power(A, 3)
print("Length-2 Walk Matrix (A^2):\n", A_squared)
print("Length-2 walks A -> A (0 -> 0):", A_squared[0, 0]) # 2: (A-B-A and A-D-A)
print("Length-2 walks A -> C (0 -> 2):", A_squared[0, 2]) # 2: (A-B-C and A-D-C)
# 2. Spectral Analysis (Eigenvalues of Adjacency Matrix)
adj_eigenvalues = np.linalg.eigvalsh(A)
print("\nAdjacency Spectrum:", np.round(adj_eigenvalues, 4)) # [-2, 0, 0, 2]
# 3. Laplacian Matrix Analysis
degree_sequence = np.sum(A, axis=1)
D = np.diag(degree_sequence)
L = D - A
lap_eigenvalues = np.linalg.eigvalsh(L)
print("Degree Matrix D:\n", D)
print("Laplacian Matrix L:\n", L)
print("Laplacian Spectrum:", np.round(lap_eigenvalues, 4)) # [0, 2, 2, 4]
print("Multiplicity of lambda=0:", np.count_nonzero(np.isclose(lap_eigenvalues, 0))) # 1 connected component
2. Cycle Space and Cut Space
Vector Spaces over GF(2)
Linear algebra applies to discrete structures over finite fields as well. Consider the Galois Field of two elements, $\text{GF}(2) = (\{0, 1\}, \oplus, \cdot)$, where addition $\oplus$ corresponds to bitwise XOR:
$$0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \quad 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0$$
For a graph $G = (V, E)$ with $m = |E|$ edges, every edge subset $E' \subseteq E$ can be uniquely represented as a characteristic binary vector $x \in \text{GF}(2)^m$, where $x_i = 1$ if edge $e_i \in E'$ and $0$ otherwise. Vector addition of two edge subsets corresponds to their Symmetric Difference ($E_1 \Delta E_2 = (E_1 \cup E_2) \setminus (E_1 \cap E_2)$).
Under this algebraic setup, two spaces emerge:
- Cycle Space ($\mathcal{C}(G)$): The subspace spanned by all cycle vectors in $G$. Its dimension (circuit rank) is $\dim(\mathcal{C}(G)) = |E| - |V| + c$, where $c$ is the number of connected components.
- Cut Space ($\mathcal{B}(G)$): The subspace spanned by all edge cuts (partitioning $V$ into two sets $S$ and $V \setminus S$). Its dimension is $\dim(\mathcal{B}(G)) = |V| - c$.
Orthogonality & Mac Lane's Planarity Criterion
Define an inner product over $\text{GF}(2)^m$ for two edge vectors $x, y$ as $\langle x, y \rangle = \sum_{i=1}^m x_i y_i \pmod 2$. Under this product, the cycle space and cut space are orthogonal complements:
$$\mathcal{C}(G) = \mathcal{B}(G)^\perp$$
Real-World Application: Mac Lane's Planarity Criterion
How does CAD software know if a circuit board trace can be laid out flat without wires overlapping? It checks planarity algebraically!
Mac Lane's Theorem (1937): A graph $G$ is planar if and only if its cycle space $\mathcal{C}(G)$ possesses a basis where every edge in $G$ appears in at most two basis cycles. This transforms geometric wire-crossing problems into linear basis checks over $\text{GF}(2)$.
3. Just Enough Topology
Metric & Topological Spaces
Topology formalizes concepts like continuity, connectedness, and boundaries without relying on fixed geometric measurements.
A Metric Space $(X, d)$ is a set $X$ with a distance function $d: X \times X \to \mathbb{R}_{\ge 0}$ satisfying non-negativity, identity of indiscernibles, symmetry, and the triangle inequality. A Topological Space $(X, \mathcal{T})$ generalizes this by specifying a collection $\mathcal{T}$ of subsets of $X$, called open sets, that are closed under arbitrary unions and finite intersections.
A continuous bijection with a continuous inverse is a Homeomorphism. Two spaces are topologically equivalent ("same shape") if a homeomorphism exists between them.
Connectedness, Compactness & Geometric Realization
To analyze planarity, we convert discrete graphs into continuous topological spaces:
- Geometric Realization ($|G|$): Map each vertex $v \in V$ to a point in $\mathbb{R}^3$, and map each edge $e = (u, v) \in E$ to a continuous arc (homeomorphic to the unit interval $[0, 1]$) connecting those endpoints.
- Topological Connectedness: A space $|G|$ is connected if it cannot be partitioned into two disjoint open sets. For finite graphs, topological path connectedness aligns with path existence.
- Compactness: A topological space is compact if every open cover contains a finite subcover. In $\mathbb{R}^n$, a subset is compact if and only if it is closed and bounded (Heine-Borel Theorem). The geometric realization $|G|$ of any finite graph is always compact.
flowchart LR
subgraph Discrete_Graph ["Discrete Graph Model"]
V1["V = {1, 2, 3}"]
E1["E = {(1,2), (2,3), (3,1)}"]
end
Discrete_Graph -- "Embedding Mapping" --> Topo_Space
subgraph Topo_Space ["Geometric Realization |G|"]
P1(("Point p₁ ∈ ℝ³")) -- "Continuous Arc [0,1]" --> P2(("Point p₂ ∈ ℝ³"))
P2 -- "Continuous Arc [0,1]" --> P3(("Point p₃ ∈ ℝ³"))
P3 -- "Continuous Arc [0,1]" --> P1
end
4. Hands-On Exercises & Solutions
Exercise 1 (Walk Counts): Let $A$ be the adjacency matrix of a complete graph $K_3$ (a triangle). Calculate $A^2$ and $A^3$ manually, and state how many walks of length 3 exist from node 1 back to node 1.
Exercise 2 (Laplacian Spectrum): Compute the Laplacian matrix $L$ for a star graph $K_{1,3}$ (one central node connected to three leaf nodes) and verify that $0$ is an eigenvalue.
Exercise 3 (Cycle Space over GF(2)): Let $G$ be a complete graph $K_4$ ($|V|=4, |E|=6$). Calculate the dimension of its cycle space $\mathcal{C}(K_4)$ over $\text{GF}(2)$.
Click to View Solutions
Solution 1:
For $K_3$: $A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}$.
$A^2 = \begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}$ (Walks of length 2: $1 \to 2 \to 1$ and $1 \to 3 \to 1$, total 2).
$A^3 = A^2 \cdot A = \begin{bmatrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2 \end{bmatrix}$.
The entry $(A^3)_{11} = 2$. There are 2 walks of length 3 from node 1 back to node 1 ($1 \to 2 \to 3 \to 1$ and $1 \to 3 \to 2 \to 1$).
Solution 2:
Center node 1, leaves 2, 3, 4.
$D = \text{diag}(3, 1, 1, 1)$, $A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$.
$L = D - A = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix}$.
Multiply $L$ by vector $v = [1, 1, 1, 1]^T$:
$L v = [3(1)-1-1-1, -1+1, -1+1, -1+1]^T = [0, 0, 0, 0]^T = 0 \cdot v$.
Thus $\lambda = 0$ is an eigenvalue with eigenvector $[1, 1, 1, 1]^T$.
Solution 3:
The dimension formula is $\dim(\mathcal{C}(G)) = |E| - |V| + c$.
For $K_4$: $|V| = 4$, $|E| = 6$, and connected components $c = 1$.
$\dim(\mathcal{C}(K_4)) = 6 - 4 + 1 = 3$. The cycle space is 3-dimensional.
5. Conclusion & Next Steps
We have deposited linear algebra and topology tools into our foundational toolkit: adjacency matrix powers count walks, Laplacian spectra analyze connectivity, binary vector spaces over $\text{GF}(2)$ establish cycle/cut space orthogonality, and geometric realizations give graphs topological meaning.
Next in the Series
In Part 4: What Is a Graph? Types, Families & Representations, we step into formal graph theory — studying vertices, edges, degree sequences, special graph families, and data structure implementations.