Matrix Representations of Graphs

To analyze graphs mathematically and computationally, we require robust algebraic representations. While visual diagrams are intuitive for human understanding, computers process graphs using structured matrix formats that allow us to leverage linear algebra to discover graph properties.

1. Introduction to Algebraic Graph Theory

Algebraic Graph Theory is a branch of mathematics that uses algebraic methods, specifically matrix theory and linear algebra, to study the structural properties of graphs. Representing graphs as matrices allows us to:

Store graphs efficiently in computer memory.
Formulate network structural queries as matrix operations.
Employ matrix multiplication algorithms to find paths, cycles, and reachability.
Identify topological invariants using eigenvalues and eigenvectors (Spectral Graph Theory).

2. The Adjacency Matrix

The adjacency matrix (also referred to as a bit matrix or Boolean matrix) is the most common matrix representation of a graph.

Formal Definition

Let $G = (V, E)$ be a graph with $n$ vertices, where the vertices are ordered as $v_1, v_2, \dots, v_n$ . The adjacency matrix $A = [a_{ij}]$ of $G$ is an $n \times n$ matrix defined by:

a_{ij} = \begin{cases} 1 & \text{if there is an edge from } v_i \text{ to } v_j \\ 0 & \text{otherwise} \end{cases}

For weighted graphs, the value $1$ is replaced by the edge weight $w(v_i, v_j)$ , and non-existent edges are typically represented by $\infty$ or $0$ depending on the application.

Key Properties

Symmetry: For any undirected graph, the adjacency matrix is always symmetric about its main diagonal: $A = A^T \implies a_{ij} = a_{ji}$

Visual Example: Directed Graph Representation

Consider the following directed graph with 4 vertices:

text

    (1) ------> (2)
     ^         / |
     |        /  |
     |       /   |
     |      v    v
    (4) <------ (3)

The matching adjacency matrix $A$ for this graph is:

A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}

3. Path Counts and Powers of the Adjacency Matrix

A powerful property of the adjacency matrix is its relationship to paths and walks of varying lengths.

Theorem: Walks of Length $k$

Let $A$ be the adjacency matrix of a graph $G$ . The entry in row $i$ and column $j$ of the matrix $A^k$ (using standard matrix multiplication) is equal to the number of distinct walks of length $k$ from vertex to vertex .

Mathematical Proof (by Induction)

Base Case ( $k=1$ ): For $k=1$ , $A^1 = A$ . By definition, $a_{ij}$ is if there is an edge (walk of length 1) from to , and otherwise. The theorem holds.

Inductive Step: Assume the theorem holds for walks of length $k-1$ . That is, $(A^{k-1})_{ir}$ represents the number of walks of length $k-1$ from to .

We want to find the number of walks of length $k$ from $v_i$ to $v_j$ . Any walk of length $k$ from $v_i$ to consists of a walk of length from to some intermediate vertex , followed by a single edge (walk of length 1) from to .

Using the multiplication rule, the number of such walks through $v_r$ is: $(A^{k-1})_{ir} \times a_{rj}$

To find the total number of walks of length $k$ over all possible intermediate vertices $v_r$ , we sum this product over all $r$ :

$\text{Walks}_k(v_i, v_j) = \sum_{r=1}^{n} (A^{k-1})_{ir} \cdot a_{rj}$

This expression is precisely the definition of the entry in row $i$ and column $j$ of the matrix product $A^{k-1} \cdot A = A^k$ . Thus:

$(A^k)_{ij} = \sum_{r=1}^{n} (A^{k-1})_{ir} \cdot a_{rj}$

By mathematical induction, the theorem is proved.

Concrete Example

Let us compute $A^2$ for the graph defined in Section 2:

A^{2} = (\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}) (\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array})

Looking at entry $(A^2)_{1,3} = 1$ , we see there is exactly 1 walk of length 2 from vertex 1 to vertex 3 (which is $1 \to 2 \to 3$ ).

4. The Path Matrix and Reachability

While the powers of the adjacency matrix provide exact path counts, we often only want to know whether at least one path exists between two vertices. This is captured by the Path Matrix (or Reachability Matrix).

Definition

The path matrix $P = [p_{ij}]$ is an $n \times n$ Boolean matrix where:

p_{ij} = \begin{cases} 1 & \text{if there is a path of any length from } v_i \text{ to } v_j \\ 0 & \text{otherwise} \end{cases}

Computation of Path Matrix

Since any simple path in a graph of $n$ vertices can have a maximum length of $n-1$ edges (or $n$ for cycles), we can calculate reachability by checking all walks up to length $n$ .

We define the sum matrix $B_n$ :

$B_n = A + A^2 + A^3 + \dots + A^n$

The path matrix $P$ is the Booleanization of $B_n$ . That is, we apply a logical OR operation:

$P = A \lor A^{(2)} \lor A^{(3)} \lor \dots \lor A^{(n)}$

where $A^{(k)}$ denotes the Boolean power of the adjacency matrix, computed using Boolean arithmetic ( $\land$ for multiplication, $\lor$ for addition).

5. The Incidence Matrix

The incidence matrix represents a graph by focusing on the relationship between its vertices and its edges.

Formal Definition

Let $G = (V, E)$ be an undirected graph with $n$ vertices ( $v_1, v_2, \dots, v_n$ ) and edges (). The incidence matrix is an matrix defined by:

m_{ij} = \begin{cases} 1 & \text{if vertex } v_i \text{ is incident to edge } e_j \\ 0 & \text{otherwise} \end{cases}

Visual Example: Undirected Graph

Consider this undirected graph:

text

    (1) -------- e1 -------- (2)
     |                        |
     |                        |
     e2                      e3
     |                        |
     |                        |
    (4) -------- e4 -------- (3)

The incidence matrix $M$ ( $4 \times 4$ ) is:

M = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}

Key Properties

Column Sum: Every column in an incidence matrix for an undirected graph has a sum of exactly $2$ , because each edge must connect exactly two distinct vertices (assuming no loops).
Row Sum: The sum of elements in row $i$ is equal to the degree of vertex $v_i$ .
Directed Graphs: For a directed graph, the incidence matrix represents direction by using $+1$ for the initiating vertex, and $-1$ for the terminating vertex of each edge:

6. Computational Trade-offs: Matrices vs. Lists

In computer science, representing graphs using a 2D array (Adjacency Matrix) is not always ideal. We often compare it with the Adjacency List format.

| Property | Adjacency Matrix | Adjacency List | | :--- | :--- | :--- | | Space Complexity | $\mathcal{O}(V^2)$ | $\mathcal{O}(V + E)$ | | Edge Lookup ( $u \to v$ ) | $\mathcal{O}(1)$ | | | | (requires resizing) | | | | | | | | | | | | () | () |

7. Python Implementation

Below is a complete, production-grade Python script demonstrating how to define an adjacency matrix, compute its powers to calculate walk counts, and construct the path matrix using standard scientific computing tools.

python

import numpy as np
 
class GraphRepresentations:
    def __init__(self, num_vertices: int):
        self.V = num_vertices
        # Initialize an empty adjacency matrix with zeros
        self.adj_matrix = np.zeros((self.V, self.V), dtype=int)
        
    def add_directed_edge(self, u: int, v: int):
        """Adds a directed edge from u to v (0-indexed)."""
        if 0 <= u < self.V and 0 <= v < self.V:
            self.adj_matrix[u][v] = 1
        else:
            raise IndexError("Vertex index out of bounds."

Summary

Adjacency Matrices ( $A$ ) map vertices directly to other vertices. They are symmetric for undirected graphs, and their values indicate edge existence or weight.
Powers of the Adjacency Matrix ( $A^k$ ) provide the exact count of walks of length $k$ between any two nodes.
Path Matrices use Boolean arithmetic to map transitive reachability across the entire network.
Incidence Matrices ( $M$ ) map vertices to edges, making them useful for tracking network flows, boundaries, and conservation laws.
Selecting between matrices and lists is a design decision based on graph density ( $E$ vs ) and runtime constraints.

Assessed progress

Matrix Representations of Graphs

Matrix Representations of Graphs

1. Introduction to Algebraic Graph Theory

2. The Adjacency Matrix

Formal Definition

Key Properties

Visual Example: Directed Graph Representation

3. Path Counts and Powers of the Adjacency Matrix

Theorem: Walks of Length $k$

Mathematical Proof (by Induction)

Concrete Example

4. The Path Matrix and Reachability

Definition

Computation of Path Matrix

5. The Incidence Matrix

Formal Definition

Visual Example: Undirected Graph

Key Properties

6. Computational Trade-offs: Matrices vs. Lists

7. Python Implementation

Summary

Key Concepts

Adjacency Matrix

Powers of Adjacency Matrix

Path Matrix (Reachability)

Incidence Matrix

Representation Trade-offs

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures