Other meanings of Adjacency Matrix
Graph theory
An adjacency matrix is a square matrix representing vertex adjacency in a graph or network. Its rows and columns correspond to vertices, and each entry records whether, or how strongly, two vertices are connected. This representation translates a graph into linear algebra, making matrix multiplication, eigenvalue analysis, and numerical computation available for studying connectivity, walks, ranking, and network structure.
An adjacency matrix records which pairs of vertices are adjacent. For a graph with vertices v1, …, vn, the matrix A has entry aij equal to 1 when an edge joins vi and vj, and 0 otherwise, in the usual simple-graph convention. The matrix is necessarily square because the same vertex set labels both axes.
For an undirected graph, A is symmetric: aij = aji. A loop appears on the main diagonal, although conventions differ about whether its entry is 1 or 2 when degree is being represented. Directed graphs generally produce nonsymmetric matrices, with the orientation determining whether rows describe outgoing or incoming edges. Weighted graphs replace binary entries with edge weights, and parallel edges may be represented by their multiplicity or combined weight.
Matrix powers turn adjacency into information about walks. The entry in position (i, j) of Ak equals the number of walks of length k from vertex i to vertex j for an unweighted graph. Consequently, nonzero entries of suitable powers reveal reachability, while diagonal entries count closed walks of specified lengths. The row sum of an ordinary simple undirected adjacency matrix is the degree of the corresponding vertex.
Permuting the vertex labels simultaneously permutes rows and columns but does not change the underlying graph. Thus two matrices can look different while representing the same graph under different orderings. Matrix multiplication also makes common-neighbor counts accessible: the entry of A2 at (i, j) counts two-step walks between the vertices. These quantities support motif detection, clustering measures, and network algorithms.
The eigenvalues and eigenvectors of an adjacency matrix summarize global graph structure. For an undirected graph, the matrix is real and symmetric, so its eigenvalues are real and it has an orthogonal eigenvector basis; the largest eigenvalue is closely related to degree concentration and connectivity patterns.1 Spectral graph theory uses these values to study regularity, expansion, graph partitioning, and dynamical processes on networks.
Dense storage requires space proportional to n2, which is wasteful for a sparse graph with relatively few edges. Software therefore commonly stores sparse adjacency matrices as lists or compressed arrays, retaining only nonzero entries.2 Libraries such as NetworkX provide conversions between graph objects and dense or sparse matrix formats, while scientific-computing systems support matrix-vector products without materializing every zero.
Adjacency matrices encode more than simple yes-or-no relationships. In a multigraph, entries can count parallel edges; in a weighted network, they can carry strengths, distances, probabilities, or signed interactions. For a directed graph, the matrix need not be symmetric, and reversing every edge transposes it. A bipartite graph has, after suitable vertex ordering, a block form whose diagonal blocks are zero and whose off-diagonal blocks describe cross-partition connections.
The matrix also connects graph theory with other constructions. The graph Laplacian is obtained from the degree matrix minus the adjacency matrix, and its zero-eigenvalue multiplicity reveals the number of connected components.3 Adjacency matrices are not unique descriptions: relabeling vertices changes the array, while graph isomorphism asks whether one matrix can be transformed into another by a simultaneous row-and-column permutation.
Conventions for loops, edge weights, and row-versus-column orientation vary by mathematical or software context; the matrix definition should always be read together with those conventions.
Help improve the encyclopedia. Reports go straight to the site manager.