Mathematics
The Adjacency Matrix and Graph Connectivity
Quick fact
If you square the adjacency matrix of a graph, the entry in row i and column j tells you exactly how many walks of length 2 exist from vertex i to vertex j.
Why this is interesting
Think of a network of friends. How can a single matrix hold the secret to who is connected to whom, and even how many ways you can reach someone in exactly two steps?
Read the full explanation
Understanding The Adjacency Matrix and Graph Connectivity
Imagine a graph as a set of dots (vertices) connected by lines (edges). An adjacency matrix is a square table where each row and column represents a vertex. If there is an edge between vertex i and vertex j, the entry A[i][j] is 1; otherwise it's 0. For example, a triangle graph with vertices A, B, C has edges (A,B), (B,C), (C,A). Its adjacency matrix is: A B C A 0 1 1 B 1 0 1 C 1 1 0 This matrix is symmetric because edges are undirected. Now, what happens when we multiply this matrix by itself? The entry (i,j) of A^2 is the sum of A[i][k] A[k][j] over all k. This sum counts how many ways you can go from i to k (if the edge exists) and then from k to j. That is exactly a walk of length 2! So A^2[i][j] gives the number of 2-step walks between i and j. In our triangle example, A^2 has 1s on the diagonal (a 2-step walk from A to A via B or C) and 2s off-diagonal (two ways to go from A to B in two steps). This idea extends to higher powers: A^k counts walks of length exactly k. This provides a powerful algebraic way to analyze connectivity without drawing the graph.
A deeper explanation
The adjacency matrix encodes the graph's structure, and matrix multiplication naturally combines sequences of edges. Each entry of A^k sums over all intermediate vertices, effectively enumerating all possible k-step walks. This is a direct application of the transitive nature of connectivity: if you can reach vertex k from i in one step and j from k in one more step, you have a 2-step walk. Repeating this builds longer walks. Connectivity is about whether you can get from any vertex to any other via some path. For an undirected graph with n vertices, consider the matrix (I + A)^(n-1), where I is the identity matrix. This matrix has a positive entry at (i,j) if and only if there is a path of length at most n-1 between i and j. Hence, its zero pattern reveals the connected components of the graph: vertices i and j are in the same component exactly when (I + A)^(n-1)[i][j] 0. This is because the longest possible simple path in a graph with n vertices has length n-1, so any reachable pair has a walk of length ≤ n-1. This algebraic characterization of connectivity is not just theoretical. It underpins algorithms for checking connectivity, and it leads to spectral graph theory, where eigenvalues of the adjacency matrix relate to graph properties like expansion and clustering. However, for large graphs, matrix multiplication can be expensive, which is why algorithms like Breadth-First Search (BFS) are often preferred in practice. Yet, the adjacency matrix remains a fundamental tool for mathematical analysis.