Adjacency matrix

Lore & Background

For a simple graph with vertex set U = {u1, ..., un}, the adjacency matrix is an n × n matrix A where Aij is 1 if there is an edge from ui to uj, and 0 otherwise. Diagonal elements are 0 for simple graphs. For undirected graphs, the matrix is symmetric. The concept extends to multigraphs and graphs with loops by storing edge counts or weights, with conventions varying for loops (counted once or twice). In undirected graphs, loops are often counted twice, adding 2 to the diagonal, which allows the degree of a vertex to be found by summing the row or column. Directed graph adjacency matrices can be asymmetric, and two conventions exist: a nonzero entry may indicate an edge from row to column or from column to row, affecting how in-degree and out-degree are computed. The adjacency matrix of a complete graph has all ones except zeros on the diagonal, while an empty graph yields a zero matrix. For bipartite graphs with parts of sizes p and q, the matrix can be written in block form with a p × q submatrix called the biadjacency matrix, which uniquely represents the graph. Variations include the Seidel adjacency matrix, a (-1, 0, 1)-matrix used for strongly regular graphs, and the distance matrix, which gives the length of the shortest path between vertices. The eigenvalues and eigenvectors of an adjacency matrix are studied in spectral graph theory; for an undirected simple graph, the matrix is symmetric, yielding real eigenvalues. The largest eigenvalue is bounded by the maximum degree, and for regular graphs it equals that degree, with multiplicity equal to the number of connected components. For bipartite graphs, if λ is an eigenvalue, so is -λ. The difference between the largest and second-largest eigenvalues is the spectral gap, related to graph expansion.

Reader's Guide

The adjacency matrix is a central object in algebraic graph theory, where it bridges graph structure and linear algebra. Its eigenvalues, collectively called the graph's spectrum, are studied in spectral graph theory and reveal properties such as connectivity and regularity; for instance, the largest eigenvalue is bounded above by the maximum degree of the graph, a fact derivable from the Perron–Frobenius theorem. For a regular graph, this largest eigenvalue equals the degree, and its multiplicity indicates the number of connected components. In bipartite graphs, each eigenvalue has a corresponding opposite eigenvalue. The difference between the largest and second-largest eigenvalues, known as the spectral gap, relates to the graph's expansion properties. The adjacency matrix is distinct from the incidence matrix, which records vertex–edge incidences, and the degree matrix, which stores vertex degrees. For bipartite graphs, a smaller biadjacency matrix can represent the graph, discarding redundant zero blocks. Variations include the Seidel adjacency matrix, a (−1, 0, 1)-matrix used for strongly regular graphs and two-graphs, and the distance matrix, which records the shortest path length between vertices. In directed graphs, the matrix can be asymmetric, with conventions differing between fields: graph theory and social network analysis often place a nonzero entry for an edge from row to column, while dynamical systems and physics may use the opposite convention. This matrix directly encodes vertex degrees: for undirected graphs, row or column sums give the degree; for directed graphs, row and column sums yield out-degree and in-degree, respectively, depending on the convention. The adjacency matrix of a complete graph has all ones except zeros on the diagonal, while that of an empty graph is a zero matrix.

Did You Know?

• The adjacency matrix of an undirected simple graph is symmetric and has a complete set of real eigenvalues.
• For a d-regular graph, d is the first eigenvalue of the adjacency matrix for the vector of all ones.
• The biadjacency matrix of a bipartite graph is an r × s 0–1 matrix that uniquely represents the graph.
• The Seidel adjacency matrix is a (−1, 1, 0)-adjacency matrix used in studying strongly regular graphs.

Foundational Structure and Entry Organization

A matrix, at its core, is a rectangular arrangement of numbers or other mathematical objects, with individual items called entries or elements laid out in horizontal rows and vertical columns. This basic structural idea underpins virtually every application of the concept. The entries themselves can belong to a field F, giving rise to real matrices (entries drawn from the real numbers) or complex matrices (entries drawn from the complex numbers), though more general entry types also exist in specialized contexts. The horizontal sequences of entries form rows, while the vertical sequences form columns, and together these two axes define the entire layout. A simple example might be a three-by-two real matrix holding values such as −1.3, 0.6, 20.4, 5.5, 9.7, and −6.2, arranged in three horizontal lines of two entries each. The standard operations of addition and multiplication apply to these arrays, making them far more than static tables of numbers—they are active algebraic objects that can be combined, transformed, and decomposed within a consistent rule set.

Dimensions, Classification, and Special Cases

The size of any matrix is fully determined by how many rows and columns it contains, expressed as an m-by-n dimension where both m and n are positive integers with no upper bound. This single classification scheme gives rise to several important special cases. A matrix possessing only one row is termed a row matrix or row vector, while one with a single column is called a column matrix or column vector. When the row count equals the column count, the result is a square matrix, which occupies a particularly privileged position in matrix theory. Beyond the finite, an infinite matrix is one that extends without bound in at least one direction, and in certain computational settings such as computer algebra systems, an empty matrix—possessing no rows or no columns—also finds a useful role. The two-by-three matrix, for instance, has exactly two horizontal rows and three vertical columns, and its dimension label 2 × 3 immediately communicates its shape to any reader familiar with the notation.

Algebraic Power: Determinants, Eigenvalues, and Matrix Theory

Square matrices, where the number of rows matches the number of columns, carry a special algebraic richness that rectangular matrices do not. The determinant is a single scalar number extracted from a square matrix, and it serves as a cornerstone of the theory: a square matrix is invertible precisely when its determinant is nonzero. Equally fundamental, the eigenvalues of a square matrix A emerge as the roots of the polynomial det(λI − A), known as the characteristic polynomial, linking the matrix to polynomial algebra in a deep way. These properties anchor an entire branch called matrix theory, which originally grew out of linear algebra but has since expanded to encompass questions from graph theory, combinatorics, abstract algebra, and statistics. In linear algebra specifically, matrices function as concrete representations of linear maps, providing a computational handle on abstract transformations. The interplay between determinants, eigenvalues, and invertibility makes square matrices the natural setting for much of the most elegant and practically useful results in the field.

Applications Across Geometry, Computation, and Science

The utility of matrices extends far beyond pure algebra. In geometry, they serve as the standard tool for encoding transformations such as rotations and for changing coordinate systems, turning spatial reasoning into systematic array manipulation. In numerical analysis, a vast array of computational problems are reduced to matrix computations, and this reduction frequently involves matrices of enormous dimension, pushing both theoretical understanding and algorithmic design to their limits. Because of these two pillars—geometric transformation and numerical computation—matrices appear in most areas of mathematics and in scientific disciplines either directly or indirectly. Whether one is solving systems of equations, modeling physical systems, or processing data, the rectangular array of entries provides a universal language. The fact that the same structural object can represent a linear map, a geometric rotation, or a huge computational workload underscores why the matrix has become one of the most versatile and widely used constructs in all of modern mathematics and applied science.