Adjacency Matrix — Definition, Formula & Examples

An adjacency matrix is a square matrix used to represent a graph, where each entry indicates whether a pair of vertices is connected by an edge. A 1 (or the edge weight) appears in position

(i, j)

if there is an edge from vertex

i

to vertex

j

, and a 0 otherwise.

For a graph $G = (V, E)$ with $n = |V|$ vertices labeled $v_1, v_2, \ldots, v_n$ , the adjacency matrix $A$ is the $n \times n$ matrix where $A_{ij} = 1$ if $(v_i, v_j) \in E$ and $A_{ij} = 0$ otherwise. For an undirected graph, $A$ is symmetric ( $A_{ij} = A_{ji}$ ). For a weighted graph, $A_{ij}$ equals the weight of the edge rather than 1.

Key Formula

A_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}

Where:

$A_{ij}$ = Entry in row i, column j of the adjacency matrix
$v_i, v_j$ = Vertices i and j of the graph
$E$ = The set of edges in the graph

How It Works

Label every vertex with an index from 1 to

n

. Create an

n \times n

grid of zeros. For each edge connecting vertex

i

to vertex

j

, set

A_{ij} = 1

. If the graph is undirected, also set

A_{ji} = 1

. The diagonal entry

A_{ii}

is 1 only if vertex

i

has a self-loop. Once built, you can use matrix operations on

A

; for instance, the entry

(A^k)_{ij}

counts the number of walks of length

k

from vertex

i

to vertex

j

Worked Example

Problem: Construct the adjacency matrix for an undirected graph with vertices {1, 2, 3} and edges {(1,2), (2,3), (1,3)}.

Step 1: Start with a 3×3 zero matrix since there are 3 vertices.

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

Step 2: For each edge, set both symmetric entries to 1. Edge (1,2): set

A_{12} = A_{21} = 1

. Edge (2,3): set

A_{23} = A_{32} = 1

. Edge (1,3): set

A_{13} = A_{31} = 1

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

Step 3: Verify: each row sum equals the degree of that vertex. Every vertex connects to the other two, so each row sums to 2.

Answer: The adjacency matrix is

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

, representing the complete graph

K_3

Why It Matters

Adjacency matrices are foundational in algorithms courses for implementing graph traversals (BFS, DFS) and shortest-path algorithms. They also appear in network science, where eigenvalues of the adjacency matrix reveal structural properties like connectivity and clustering in social or biological networks.

Common Mistakes

Mistake: Using a symmetric matrix for a directed graph.

Correction: For directed graphs,

A_{ij} = 1

means an edge from

i

j

, but

A_{ji}

may be 0 if the reverse edge does not exist. Only undirected graphs guarantee

A = A^T