STEP-BY-STEP LESSON · §10.2
Matrix Representations of Graphs
Represent a graph by a matrix and count two-step walks.
Before you begin
Rows, columns and entries
Fix a vertex order. Entry M[i,j] is in row i and column j. For a simple graph it records adjacency as 0 or 1; for a loop-free multigraph it can record the number of parallel edges. Matrix multiplication is explained in this lesson, not assumed as a prerequisite.
Adjacency
Two vertices are adjacent if an edge joins them directly. Being reachable by several edges is a different condition. For an undirected graph, reversing an edge’s endpoint names does not create a new edge.
Symbols
- Aᵢⱼ
- adjacency matrix entry
- (A²)ᵢⱼ
- number of length-2 walks in a simple graph
- i,j,k
- Row index i, column index j, and intermediate vertex index k
- Σₖ
- Sum one term for each possible intermediate index k
Definitions and notation for this topic
Matrix of a finite relation
M[a,b]
For R⊆A×B on finite ordered sets, M[a,b]=1 if (a,b)∈R and 0 otherwise. State the row order A and column order B.
An entry represents a particular ordered pair. A multigraph adjacency matrix may count parallel edges and therefore have entries greater than 1; that is a different convention.
Separate glossary example
For A=(1,2), B=(u,v), R={(1,v),(2,u)}, the matrix is [[0,1],[1,0]].
Loops and parallel edges
A loop has the same endpoint twice. Parallel edges are distinct edges with the same endpoints. For an undirected multigraph, retain each edge’s identity and endpoint pair.
A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.
Separate glossary example
e₁=AB and e₂=AB are two edges, not one duplicated set entry. A loop e₃=AA contributes two to deg(A).
Adjacency matrix
M_ij
For a finite loop-free undirected multigraph with fixed vertex order, M_ij is the number of edges between vertices i and j. The diagonal is zero and M is symmetric.
For a simple graph entries are 0 or 1. A directed graph uses a row-to-column direction and need not give a symmetric matrix. Loop-diagonal conventions must be stated separately.
Separate glossary example
Two vertices (A,B) joined by two parallel edges have M=[[0,2],[2,0]].
Matrix powers count walks
(M²)_ij=∑_k M_ik M_kj
For the adjacency matrix of a finite simple graph, (M²)_ij counts walks of length two from i to j, summed over possible intermediate vertices k.
These are walks, not necessarily paths: returning to a previous vertex is allowed. More generally (M^r)_ij counts length-r walks for nonnegative integer r; M⁰ is the identity matrix.
Separate glossary example
In the path 1—2—3, (M²)_13=1 from 1—2—3, and (M²)_11=1 from 1—2—1.
Permutation matrix and relabelling
M_H=PᵀM_GP
For a vertex bijection f from G to H, put P_uv=1 when f(u)=v and 0 otherwise, with rows in G order and columns in H order. For the same adjacency convention, M_H=PᵀM_GP expresses preserved adjacency.
Pᵀ swaps P’s row and column indices. Right multiplication reorders columns and left multiplication by Pᵀ reorders rows. Reversing the convention for P changes the displayed identity; the matrix does not name an edge bijection.
Separate glossary example
If G order is (1,2,3), H order is (p,q,r), and f(1)=r,f(2)=p,f(3)=q, then P=[[0,0,1],[1,0,0],[0,1,0]].
Step by step
Step 1 / 6
Fix a vertex order
For a simple loop-free graph, set Aᵢⱼ=1 when edge i–j exists and 0 otherwise.
A fixed order is needed to interpret rows and columns.
Worked example
For the path A–B–C, how many length-2 walks go from A to C and from A back to A?
- Let M be the adjacency matrix in vertex order A,B,C: M=[[0,1,0],[1,0,1],[0,1,0]].
- A→B→C is the only two-step walk A→C. A→B→A is the only one A→A.
- Thus (M²)AC=1 and (M²)AA=1 even though MAA=0.
Optional self-check
In the graph A–B–C, why is the (B,B) entry of the squared adjacency matrix 2 although the original diagonal is zero?
Show answer
There is no loop at B, but there are two two-edge walks B→A→B and B→C→B. The square counts those walks.