In graph theory, the adjacency matrix of a finite simple undirected graph with n vertices is an n × n square matrix where each entry a_ij is 1 if vertices i and j are adjacent (connected by an edge) and 0 otherwise, with the main diagonal consisting of zeros to reflect the absence of self-loops.^[1] This matrix provides a compact algebraic representation of the graph's edge structure, where the labeling of rows and columns corresponds to an arbitrary but fixed ordering of the vertices.^[2] For directed graphs, the adjacency matrix is similarly defined but asymmetric, with a_ij equal to 1 if there is a directed edge from vertex i to j, allowing for one-way connections.^[1] In weighted graphs, entries a_ij represent the weight of the edge between i and j (or 0 if no edge exists), enabling analysis of graphs with varying edge strengths, such as distances or capacities.^[1] The matrix for an undirected graph is symmetric (A = A^T)^[2], reflecting the bidirectional nature of edges. By ordering the vertices such that those in each connected component are contiguous, the matrix can be arranged into a block-diagonal structure, with each block corresponding to the adjacency matrix of a connected component.^[1] Key properties of the adjacency matrix include its utility in computing graph invariants: the sum of the i-th row (or column) equals the degree of vertex i in undirected graphs, and powers of the matrix (A^k) have entries that count the number of walks of length k between vertices, facilitating path enumeration.^[1] In spectral graph theory, the eigenvalues of the adjacency matrix reveal structural insights, such as connectivity and expansion properties; for regular graphs, the largest eigenvalue relates to the degree, while smaller ones indicate bipartiteness or clustering.^[3] The adjacency matrix has broad applications beyond pure mathematics, including efficient storage and manipulation of graphs in computer science algorithms for network analysis, as well as modeling molecular structures in chemistry and communication flows in engineering.^[3] Its linear algebraic framework supports randomized algorithms and expander graph constructions in modern computing, underscoring its foundational role in bridging graph theory with applied fields.^[3]

Definition and Variations

Basic Definition

In graph theory, a graph $G$ consists of a set $V$ of vertices and a set $E$ of edges, where each edge is an unordered pair of distinct vertices from $V$. A simple undirected graph is an unweighted, undirected graph containing no loops (edges connecting a vertex to itself) or multiple edges between the same pair of vertices.^[4] The adjacency matrix $A$ of a simple undirected graph $G$ with vertex set $V = \{1, 2, \dots, n\}$ is the $n \times n$ square matrix defined by

$$A = (a_{ij})_{1 \leq i,j \leq n},$$

where $a_{ij} = 1$ if there is an edge between vertices $i$ and $j$, and $a_{ij} = 0$ otherwise.^[5] Since the graph is undirected, the adjacency matrix $A$ is symmetric, satisfying $a_{ij} = a_{ji}$ for all $i, j$.^[5] Additionally, the absence of loops in simple graphs ensures that the diagonal entries are zero, so $a_{ii} = 0$ for all $i$.^[5] To construct the adjacency matrix, label the vertices in order from 1 to $n$, then for each pair of distinct indices $i$ and $j$ with $i < j$, check if an edge exists between vertices $i$ and $j$; if so, set $a_{ij} = a_{ji} = 1$, otherwise set $a_{ij} = a_{ji} = 0$, and set all diagonal entries $a_{ii} = 0$.^[6]

Bipartite Graphs

A bipartite graph is one whose vertex set can be partitioned into two disjoint subsets $U$ and $V$ such that every edge connects a vertex in $U$ to a vertex in $V$, with no edges within $U$ or within $V$.^[7] The adjacency matrix $A$ of such a graph, assuming vertices are ordered with those in $U$ first followed by those in $V$, is a square $(|U| + |V|) \times (|U| + |V|)$ matrix featuring zero blocks on the diagonal corresponding to intra-partition connections and nonzero entries only in the off-diagonal blocks representing inter-partition edges.^[8] Since the graph is undirected and simple, $A$ is symmetric with binary entries (0 or 1), and the upper off-diagonal block is the transpose of the lower one.^[8] The submatrix in the upper off-diagonal block, denoted the biadjacency matrix $B$, is a $|U| \times |V|$ matrix where the entry $B_{i,j} = 1$ if the $i$-th vertex in $U$ is adjacent to the $j$-th vertex in $V$, and 0 otherwise; for multigraphs, entries count the edges between them.^[7] The full adjacency matrix then takes the block form

$$A = \begin{pmatrix} \mathbf{0}_{|U| \times |U|} & B \\ B^T & \mathbf{0}_{|V| \times |V|} \end{pmatrix},$$

where $\mathbf{0}_{k \times l}$ denotes the $k \times l$ zero matrix.^[8] This structure succinctly encodes the bipartition and edge constraints. For the complete bipartite graph $K_{m,n}$, where every vertex in the $m$-vertex set connects to every vertex in the $n$-vertex set, the biadjacency matrix $B$ is the all-ones matrix $J_{m,n}$, making the off-diagonal blocks fully populated with 1s.^[8] Thus, the adjacency matrix is

$$A = \begin{pmatrix} \mathbf{0}_{m \times m} & J_{m,n} \\ J_{n,m} & \mathbf{0}_{n \times n} \end{pmatrix},$$

with $J_{n,m} = J_{m,n}^T$.^[8]

Directed and Weighted Graphs

In directed graphs, the adjacency matrix $A$ is defined such that its entry $A_{ij}$ is 1 if there is a directed edge (arc) from vertex $i$ to vertex $j$, and 0 otherwise.^[9] Unlike the adjacency matrix of an undirected graph, which is symmetric ($A = A^T$), the matrix for a directed graph is generally not symmetric, reflecting the potential asymmetry in edge directions ($A_{ij} \neq A_{ji}$).^[10] This representation captures the orientation of edges, making it suitable for modeling relationships with inherent directionality, such as one-way streets or dependencies in a network. For weighted graphs, the adjacency matrix extends to include edge weights, where $A_{ij} = w_{ij}$ if there is an edge from vertex $i$ to vertex $j$ with weight $w_{ij}$ (typically a real number indicating strength, cost, or capacity), and 0 otherwise.^[10] This formulation applies to both undirected and directed graphs; in the directed case, weights allow $A_{ij} \neq A_{ji}$ even if both directions exist, enabling the representation of asymmetric influences or flows. The weighted adjacency matrix thus generalizes the binary version, preserving structural information while incorporating quantitative edge attributes. Variations of the adjacency matrix accommodate specialized graph types. In signed graphs, where edges carry positive or negative signs to model agreement or conflict, $A_{ij} = +1$ for a positive edge from $i$ to $j$, $A_{ij} = -1$ for a negative edge, and 0 otherwise, with the matrix remaining non-symmetric for directed signed graphs.^[11] For multigraphs, which permit multiple edges between the same pair of vertices, $A_{ij}$ equals the number of edges from $i$ to $j$ (or between them in the undirected case), allowing the matrix to count parallel connections rather than just their presence.^[12] These adaptations maintain the core utility of the adjacency matrix while tailoring it to diverse applications in network analysis.

Examples

Undirected Simple Graphs

In undirected simple graphs, the adjacency matrix is a symmetric $ n \times n $ matrix with zeros on the main diagonal (reflecting no self-loops) and ones in the off-diagonal positions corresponding to edges between distinct vertices. The complete graph $ K_n $, where every pair of distinct vertices is connected by an edge, has an adjacency matrix consisting of zeros on the diagonal and ones everywhere else; this can be expressed as $ J - I $, where $ J $ is the all-ones matrix and $ I $ is the identity matrix.^[13] For example, the adjacency matrix of $ K_3 $ (a triangle) is

$$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.$$

The cycle graph $ C_n $, consisting of $ n $ vertices connected in a single cycle, has an adjacency matrix that is circulant, with ones at positions $ (i, i+1) $ and $ (i, i-1) $ for $ i = 1, \dots, n $ (indices modulo $ n $) and zeros elsewhere.^[14] For $ n = 4 $, the adjacency matrix of $ C_4 $ (a square) is

$$\begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}.$$

The path graph $ P_n $, a connected tree with $ n $ vertices and $ n-1 $ edges forming a linear chain, has an adjacency matrix that is tridiagonal, with ones on the subdiagonal and superdiagonal (corresponding to consecutive vertices) and zeros elsewhere.^[15] For $ n = 4 $, this yields

$$\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}.$$

Directed Graphs

In directed graphs, the adjacency matrix $A$ is an $n \times n$ matrix where the entry $a_{ij} = 1$ if there is a directed edge from vertex $i$ to vertex $j$, and $0$ otherwise; unlike the undirected case, this matrix is generally asymmetric, reflecting the orientation of edges.^[16] This asymmetry captures the one-way nature of directed edges, allowing the matrix to encode precedence or flow in structures like networks or dependencies.^[17] A classic example is the directed cycle graph $C_n$, where vertices are connected in a unidirectional loop. For $n=3$ (a directed triangle), the adjacency matrix has 1s on the superdiagonal and in the bottom-left corner:

$$\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$

This matrix represents edges $1 \to 2$, $2 \to 3$, and $3 \to 1$, forming a cyclic structure. For general $n$, the matrix is a circulant permutation matrix with 1s shifted along the superdiagonal and $a_{n1} = 1$.^[18] Another illustrative case is the tournament graph, a complete directed graph on $n$ vertices where exactly one directed edge exists between every pair of distinct vertices. The adjacency matrix of a 3-vertex tournament is thus a 3x3 matrix with zeros on the diagonal and exactly one 1 in each off-diagonal pair $(i,j)$ and $(j,i)$.^[19] For the cyclic tournament (isomorphic to the directed triangle above), the matrix is

$$\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix},$$

featuring a single directed 3-cycle. In contrast, an asymmetric (transitive) tournament, where one vertex dominates the others in a linear hierarchy, has the matrix

$$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{pmatrix},$$

with edges $1 \to 2$, $1 \to 3$, and $2 \to 3$, containing no cycles.^[19] The transpose $A^T$ of a directed graph's adjacency matrix represents the graph with all edge directions reversed, swapping rows and columns to invert the orientations while preserving the underlying structure.^[16] This property is useful for analyzing reversals in flow or dependency graphs.

Trivial and Special Cases

The trivial graph, consisting of a single isolated vertex with no edges, has an adjacency matrix that is the 1×1 zero matrix $[0]$. This follows directly from the standard definition, where the absence of any edges results in no off-diagonal entries, and the diagonal is zero since simple graphs prohibit self-loops. For the empty graph, or edgeless graph, with $n$ isolated vertices and no edges connecting any pair, the adjacency matrix is the $n \times n$ zero matrix, where every entry $a_{ij} = 0$ for all $i, j$. This structure reflects the complete lack of adjacencies, making the matrix entirely sparse with no 1s anywhere.^[20] In disconnected graphs, which consist of multiple connected components, the adjacency matrix can be arranged—by appropriately ordering the vertices—to take a block-diagonal form. Specifically, if the graph has $p$ components with sizes $n_1, n_2, \dots, n_p$, the matrix $A$ is a block-diagonal matrix with $p$ square blocks along the diagonal, each block being the adjacency matrix of one component, and all off-block entries zero. This permutation highlights the independence of the components.^[1] Although simple undirected graphs typically exclude self-loops, allowing loops in more general graph models modifies the adjacency matrix such that the diagonal entry $a_{ii} = 1$ (or the loop's weight) if vertex $i$ has a self-loop, deviating from the zero diagonal of loop-free graphs. This convention enables representation of reflexive edges in applications like multigraphs or directed graphs with possible feedback.^[5]

Mathematical Properties

Spectral Properties

The spectrum of a graph is defined as the multiset of eigenvalues of its adjacency matrix $A$. For an undirected simple graph without loops, $A$ is a real symmetric matrix, so its eigenvalues are real numbers and it admits an orthogonal basis of eigenvectors.^[21] The eigenvalues $\lambda_1, \lambda_2, \dots, \lambda_n$ (ordered such that $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$) satisfy the characteristic equation $\det(A - \lambda I) = 0$, where $I$ is the identity matrix. Since $A$ has zero diagonal entries (no loops), its trace is zero, implying that the sum of the eigenvalues equals zero: $\sum_{i=1}^n \lambda_i = 0$.^[21] The largest eigenvalue $\lambda_1$, known as the spectral radius $\rho(A)$, provides key insights into graph structure. For any graph, $\rho(A) \leq \Delta$, where $\Delta$ is the maximum vertex degree, with equality if and only if the graph is regular.^[22] For a connected graph, the Perron–Frobenius theorem applies to the nonnegative irreducible matrix $A$, ensuring that $\rho(A)$ is a simple eigenvalue with a positive eigenvector (the Perron vector), and $\rho(A) > |\lambda_i|$ for all other eigenvalues $\lambda_i$.^[23] In a $k$-regular graph, $\lambda_1 = k$ with multiplicity equal to the number of connected components.^[21] A representative example is the complete graph $K_n$ on $n$ vertices, whose adjacency matrix has eigenvalues $n-1$ (with multiplicity 1, corresponding to the all-ones eigenvector) and $-1$ (with multiplicity $n-1$).^[21] This spectrum reflects the high connectivity, with the spectral radius $n-1$ matching the regular degree.

Isomorphism and Graph Invariants

The adjacency matrix provides a fundamental tool for determining graph isomorphism. Two graphs $G$ and $H$ with adjacency matrices $A$ and $B$, respectively, are isomorphic if and only if there exists a permutation matrix $P$ such that $B = P^{-1} A P$.^[24] For undirected graphs, where $A$ and $B$ are symmetric, this relation simplifies to $B = P^T A P$, reflecting the orthogonal nature of permutation matrices.^[24] This permutation similarity captures the structural equivalence of the graphs under vertex relabeling, as the matrix entries correspond directly to edge incidences. However, the adjacency matrix itself is not a complete graph invariant due to its dependence on vertex labeling. Isomorphic graphs share the same adjacency matrix up to such a similarity transformation, but distinct labelings of the same graph yield different matrices without applying the permutation.^[5] Consequently, direct matrix equality does not imply isomorphism; instead, one must verify the existence of the transforming permutation, which underpins the computational challenge of the graph isomorphism problem.^[25] Several properties of the adjacency matrix serve as graph invariants. The total number of 1's in $A$ equals twice the number of edges in an undirected simple graph without loops, providing a basic measure of graph density.^[24] The row sums of $A$ correspond to the degrees of the vertices, yielding the degree sequence as an invariant multiset.^[24] More sophisticated invariants include the permanent of $A$, which counts the number of permutation matrices subordinate to $A$ and remains unchanged under permutation similarity, useful for enumerating perfect matchings in bipartite cases.^[26] Immanants, generalizations of the permanent and determinant via irreducible characters of the symmetric group, offer further invariants that capture cycle index symmetries and have applications in distinguishing non-isomorphic graphs.^[26] The spectrum of $A$—its multiset of eigenvalues—is another key invariant preserved under similarity.^[24]

Matrix Powers and Walk Counting

One of the key applications of the adjacency matrix in graph theory lies in its powers, which provide a means to count walks between vertices. Specifically, if $A$ is the adjacency matrix of a graph $G$, then the $(i,j)$-entry of $A^k$, denoted $(A^k)_{ij}$, equals the number of walks of length $k$ from vertex $i$ to vertex $j$ in $G$. This result follows from the structure of matrix multiplication, where each term in the product corresponds to extending a walk by one edge at a time. In undirected graphs, these walks may revisit vertices and edges, and the count $(A^k)_{ii}$ for $i = j$ gives the number of closed walks of length $k$ based at vertex $i$. Such closed walks offer insights into the graph's local connectivity and periodic structures around $i$. Moreover, the existence of a positive entry in some power $A^k$ (for $k \leq n-1$, where $n$ is the number of vertices) indicates the presence of a walk between $i$ and $j$, which in connected undirected graphs implies overall connectivity via the union of such powers. For directed graphs, the theorem extends analogously, but the walks must respect edge directions, enabling the enumeration of directed paths and circuits. The adjacency matrix for digraphs is typically not symmetric, yet the power $A^k$ still captures the number of directed walks of length $k$ from $i$ to $j$. A concrete illustration occurs for $k=2$: the diagonal entries of $A^2$ equal the degrees of the vertices in undirected graphs, since $(A^2)_{ii} = \sum_{l} A_{il} A_{li} = \sum_{l \sim i} 1 = \deg(i)$.^[27] More generally, the trace $\operatorname{tr}(A^k) = \sum_{i} (A^k)_{ii}$ equals the total number of closed walks of length $k$ across all vertices, a quantity that relates to cycle enumeration in broader combinatorial contexts by summing contributions from all possible closed structures. To see this in action, consider the path graph $P_3$ on vertices $\{1,2,3\}$ with edges $1-2$ and $2-3$. Its adjacency matrix is

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

The second power is

$$A^2 = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix},$$

where $(A^2)_{13} = 1$ counts the single walk $1 \to 2 \to 3$ of length 2, and $(A^2)_{22} = 2$ counts the closed walks $2 \to 1 \to 2$ and $2 \to 3 \to 2$. The off-diagonal entries like $(A^2)_{11} = 1$ and $(A^2)_{13} = 1$ highlight connections to neighbors of neighbors, illustrating how $A^2$ reveals the graph's two-step reachability.^[27]

Computational Aspects

Storage and Data Structures

The adjacency matrix is typically stored in a dense representation as a full $n \times n$ array, where $n$ is the number of vertices, requiring $O(n^2)$ space regardless of the number of edges.^[28] This approach is suitable for dense graphs, where the edge count approaches $n^2$, as it avoids wasting space on absent edges and enables constant-time access to any potential edge via direct indexing.^[28] For sparse graphs, where the number of edges is significantly less than $n^2$, compressed formats like the compressed sparse row (CSR) or compressed sparse column (CSC) are used to store only the non-zero entries along with their row and column indices.^[29] In CSR, for instance, the non-zero values are kept in a single array, with auxiliary arrays tracking the starting positions of each row and the column indices of the non-zeros, achieving space proportional to the number of edges plus vertices.^[29] Similarly, CSC transposes this structure for column-major access.^[29] In unweighted graphs, the adjacency matrix can be implemented as a bit matrix, packing each entry into a single bit to reduce space to approximately $O(n^2 / 8)$ bytes, assuming byte-aligned storage.^[30] This bit-packing is efficient for binary presence/absence indicators but requires bitwise operations for access, which may introduce minor overhead compared to full integer arrays.^[30] These storage choices involve trade-offs in access time and flexibility: dense representations offer $O(1)$ edge queries but fixed high space usage, while sparse formats like CSR or CSC provide better space efficiency for low-edge-density graphs at the cost of slower insertions, which may require reallocating index arrays.^[28] For weighted graphs, entries must store floating-point or integer weights rather than bits or simple indicators, increasing per-entry space needs to 4 or 8 bytes typically.^[31]

Algorithms and Operations

The multiplication of two adjacency matrices $A$ and $B$, where $A$ is the adjacency matrix of graph $G_1$ and $B$ of graph $G_2$, yields the adjacency matrix of the matrix product graph, a construction that combines the structures of $G_1$ and $G_2$ by connecting vertices based on paths through intermediate nodes.^[32] This operation, defined over the reals or integers, counts the number of walks of length 2 between vertices in the product graph, with applications in graph factorization and relational composition.^[32] In the context of reachability, matrix multiplication under the boolean semiring (replacing addition with logical OR and multiplication with AND) computes transitive closures, enabling detection of paths between nodes.^[33] The standard algorithm for $n \times n$ matrix multiplication has $O(n^3)$ time complexity, but Strassen's algorithm reduces this to $O(n^{\log_2 7}) \approx O(n^{2.807})$ by recursively partitioning matrices into 2x2 blocks and performing seven multiplications instead of eight. Addition of adjacency matrices corresponds to the direct sum for the disjoint union of graphs, forming a block-diagonal matrix where the blocks are the individual adjacency matrices, preserving the disconnected components without inter-graph edges.^[34] This operation maintains the sparsity and structure of the components, with the resulting matrix size equal to the sum of the original dimensions.^[35] For directed graphs, the transpose of the adjacency matrix $A^T$ reverses all edge directions, transforming outgoing edges into incoming ones and vice versa, which is equivalent to the adjacency matrix of the transpose graph.^[36] This reversal is computationally efficient at $O(n^2)$ time for dense matrices but can leverage sparsity for faster execution.^[36] Key algorithms utilizing adjacency matrices include the Floyd-Warshall algorithm for all-pairs shortest paths, which iteratively updates a distance matrix initialized from the adjacency matrix (or infinity where no edges exist) using dynamic programming to consider intermediate vertices, achieving $O(n^3)$ time. Gaussian elimination applied to the adjacency matrix solves linear systems $A \mathbf{x} = \mathbf{b}$ over fields like the reals or GF(2), useful in graph algorithms such as computing matchings or analyzing connectivity, with complexity $O(n^3)$ in the dense case but reducible via sparsity patterns.^[37] Matrix-vector multiplication $A \mathbf{v}$, fundamental for iterative methods like power iteration on graphs, has $O(n^2)$ complexity for dense adjacency matrices but improves to $O(|E|)$ when exploiting sparsity, as only non-zero entries contribute to the result.^[38]