Adjacency Matrix — Mathematics Knowledge System

Overview

An adjacency matrix represents a graph as an n×n matrix A, where n is the number of vertices, and entry A[i][j] indicates whether an edge exists between vertex i and vertex j. For an undirected graph, the matrix is symmetric (A[i][j] = A[j][i]); for a weighted graph, entries hold edge weights instead of just 0/1. This representation trades space (O(n²), even for sparse graphs) for speed of edge lookups (O(1)) and lets graph questions be answered with linear-algebra tools — for instance, the number of walks of length k between two vertices is given by the (i,j) entry of A^k.

Intuition

Think of the adjacency matrix as a seating chart of 'who knows whom': row i, column j has a 1 exactly when person i and person j are connected. It's the same information as drawing dots and lines, just organized into a grid a computer can index instantly — checking whether i and j are connected is a single array lookup instead of scanning a list of edges.

Formal Definition

Definition

For a graph G = (V, E) with vertices labeled 1, ..., n, the adjacency matrix A is defined entrywise as:

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

Adjacency matrix entry

A = A^{T} \quad \text{(undirected graph)}

Symmetry for undirected graphs

(A^{k})_{ij} = \text{number of walks of length } k \text{ from } i \text{ to } j

Walk-counting property

Worked Examples

Row/column 1 has a 1 only at position 2 (edge 1-2); no edge 1-3.
$A_{12} = A_{21} = 1,\ A_{13} = A_{31} = 0$
Row/column 2 has 1s at positions 1 and 3 (edges 2-1 and 2-3).
$A_{23} = A_{32} = 1$
Assemble the full symmetric matrix with zero diagonal (no self-loops).
$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$

Answer: A = [[0,1,0],[1,0,1],[0,1,0]].

Practice Problems

Difficulty 3/10

A directed graph has edges 1→2 and 2→1. What is A[1][2] and A[2][1] in its adjacency matrix?

Difficulty 4/10

A social network has 1,000,000 users but each user has on average only 200 friends (a sparse graph). Why is an adjacency matrix a poor choice here compared to an adjacency list?

Difficulty 3/10

In the adjacency matrix of a simple graph (no self-loops, no multi-edges), what values appear on the main diagonal?

Quiz

Summary

An n×n adjacency matrix A has A[i][j] = 1 iff there's an edge from i to j; it's symmetric for undirected graphs.
Matrix powers reveal walk counts: (A^k)_{ij} is the number of length-k walks from i to j.
Adjacency matrices give O(1) edge lookups but cost O(n²) space, making adjacency lists preferable for large sparse graphs.

References

WebsiteWikipedia — Adjacency matrix