The Adjacency Matrix

Graph Theory · Axiom Academy

Learn how to represent graphs using matrices and understand their powerful mathematical properties Definition: The Adjacency Matrix The adjacency matrix is a square matrix that encodes which vertices are connected by edges. For a graph with n vertices, we create an n×n matrix where each entry tells us whether two vertices are adjacent. For a graph G with vertices V = v₁, v₂, ..., vₙ , the adjacency matrix A is an n×n matrix where: A[i,j] = 1 if there is an edge from vertex i to vertex j A[i,j] = 0 if there is no edge from vertex i to vertex j Consider a graph with 3 vertices a, b, c where edges connect a-b and b-c: Symmetric Matrices for Undirected Graphs When a graph is undirected , its adjacency matrix has a special property: it is symmetric . This means A[i,j] = A[j,i] for all i and j. For an undirected graph, if there is an edge between vertices i and j, then: This creates a symmetric matrix where entries mirror across the main diagonal. A triangle graph with vertices 1, 2, 3 has all pairs connected: Notice: The matrix is symmetric across its diagonal! Directed Graphs: Breaking Symmetry In a directed graph , edges have direction. An edge from i to j does NOT imply an edge from j to i. This breaks the symmetry of the adjacency matrix! Directed Graph Adjacency Matrix The matrix may be asymmetric because A[i,j] = 1 does not require A[j,i] = 1. Consider vertices 1, 2, 3 with directed edges 1→2 and 2→3:

This is the written version of the interactive lesson above. See the full Graph Theory course.