An adjacency matrix is a square matrix that represents a finite graph by recording which pairs of vertices are connected by edges. Its rows and columns correspond to vertices in a specified order, and each entry indicates the presence, number, or weight of edges between the corresponding vertices. Adjacency matrices provide a fundamental connection between graph theory and linear algebra, allowing graph structure to be studied through matrix operations, eigenvalues, and computational algorithms.
Definition and conventions
Let be a graph with ordered vertex set . For a simple undirected graph—one with neither loops nor multiple edges—its adjacency matrix is defined by
Thus is an matrix with entries in . It is symmetric, and all its diagonal entries are zero.
For a directed graph, a common convention is
Under this convention, rows describe outgoing connections and columns describe incoming connections. Some authors and software systems use the opposite convention, so the interpretation must be checked when comparing representations. Reversing every edge replaces by its transpose .
Multiple edges, loops, and weights
The definition extends to other graph types:
- Multiple edges: can record the number of edges from to .
- Loops: diagonal entries record edges joining a vertex to itself.
- Weighted edges: can record an edge weight, or the sum of the weights of parallel edges.
For undirected loops, two conventions are common: each loop contributes either or to the diagonal entry. Counting it twice makes row sums equal vertex degrees when a loop contributes two to degree; counting it once is natural when matrix entries record individual edge traversals. Formulas involving degrees or powers must be interpreted according to the chosen convention.
A weighted adjacency matrix commonly uses zero to indicate the absence of an edge. If zero-weight edges are allowed, the weight matrix alone may not distinguish them from missing edges; a separate record of edge presence may be required.
Example and elementary properties
Consider the undirected path with vertices and edges and . Its adjacency matrix is
For a simple undirected graph, the degree of vertex is the sum of row :
Writing for the column vector whose entries are all , the vector of degrees is . If the graph has edges, then
because each edge contributes two symmetric entries.
For a directed graph under the row-source convention, row sums give out-degrees and column sums give in-degrees. With weighted edges, these sums instead give outgoing and incoming weighted degrees, also called strengths.
Dependence on vertex order
The matrix depends on the ordering of the vertices, but the underlying graph does not. If is a permutation matrix representing a change of order, the reordered adjacency matrix has the form
Consequently, graphs are isomorphic precisely when their adjacency matrices are related by such a simultaneous permutation of rows and columns. This is a special case of matrix similarity, so eigenvalues, the characteristic polynomial, and other similarity invariants do not depend on vertex labeling.
Matrix powers, walks, and reachability
A principal reason for using adjacency matrices is that their powers count walks. A walk is a sequence of consecutive edges in which vertices and edges may repeat. For an unweighted graph, using edge-count entries and counting each loop once,
This follows from matrix multiplication:
Each term counts walks that reach after steps and then traverse an edge to .
For the three-vertex path,
The central diagonal entry is , corresponding to the walks and . These are not simple paths: matrix powers count walks, not only routes with distinct vertices.
For a weighted adjacency matrix, is the sum, over length- walks, of the products of their edge weights.
Closed walks and subgraph counts
The trace of counts closed walks of length , including their choice of starting vertex. For a simple undirected graph,
Each triangle contributes three possible starting vertices and two traversal directions.
Boolean reachability
Using Boolean algebra instead of ordinary arithmetic—logical OR for addition and logical AND for multiplication—matrix powers indicate whether walks exist rather than how many exist.
For , the Boolean matrix
records reachability, including zero-length walks through the identity matrix . The bound suffices because whenever one vertex is reachable from another, a path without repeated vertices exists.
Spectral properties
The eigenvalues and eigenvectors of an adjacency matrix constitute its spectral information. For an undirected graph with real symmetric weights, the spectral theorem ensures that all eigenvalues are real and that an orthonormal basis of eigenvectors exists.
Several structural properties have spectral interpretations:
- If the graph is -regular, meaning that every vertex has degree , then .
- For a simple undirected graph, the largest eigenvalue is at most the maximum vertex degree.
- If a simple undirected graph is connected, its largest eigenvalue has an eigenvector with strictly positive entries, unique up to scaling.
- A simple undirected graph is bipartite if and only if its eigenvalues are symmetric about zero, including multiplicities.
If the eigenvalues are , then
Thus spectral data determine closed-walk counts. They do not, however, determine the graph uniquely: nonisomorphic graphs can have identical adjacency eigenvalues. Such graphs are called cospectral.
For directed graphs, the adjacency matrix need not be symmetric. Its eigenvalues may be complex, and it need not have a full basis of eigenvectors.
Related matrices and representations
Graph Laplacian
For an undirected graph with nonnegative edge weights, let be the diagonal matrix of weighted degrees. The graph Laplacian is
For a loopless graph,
The Laplacian is therefore positive semidefinite. The multiplicity of its zero eigenvalue equals the number of connected components. Laplacian matrices are central to graph partitioning, diffusion, and clustering.
Random-walk transition matrix
When all degrees are positive, normalizing rows gives
For an unweighted graph, is the probability that a random walk at vertex moves next to . The resulting transition matrix defines a Markov chain. Isolated vertices require a separate convention, such as making them absorbing states.
Bipartite graphs
If a bipartite graph has vertex classes of sizes and , an appropriate ordering gives
The matrix , called a biadjacency matrix, records edges between the two classes. Unlike the full adjacency matrix, it can be rectangular.
Complement graphs
For a simple undirected graph, the adjacency matrix of its complement is
where is the all-ones matrix. The subtraction of ensures that the complement has no loops.
Computational uses and limitations
Adjacency matrices support algebraic graph algorithms, network analysis, and matrix-based models in machine learning. They are particularly convenient for dense graphs, repeated edge queries, and computations that exploit optimized numerical hardware.
A full representation requires storage locations, regardless of the number of edges. In a standard random-access representation, testing whether a particular edge exists takes time, while listing all neighbors of a vertex requires scanning a row and takes time. These bounds use asymptotic notation.
For graphs with relatively few edges, an adjacency list usually stores the structure more compactly, using space. A sparse matrix representation can preserve many algebraic advantages while storing only nonzero entries, though lookup and modification costs depend on the storage format.
The algebra used with a matrix also matters. Ordinary multiplication counts walks; Boolean operations test reachability; replacing addition by minimum and multiplication by addition supports certain shortest-path computations. Treating a weighted adjacency matrix as though it were an unweighted one, or confusing walks with simple paths, can therefore produce incorrect interpretations.