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).

Reader's Guide

The adjacency matrix is a cornerstone of algebraic graph theory, enabling the application of linear algebra to graph problems. Its eigenvalues, forming the graph's spectrum, reveal properties like connectivity and regularity. For bipartite graphs, the biadjacency matrix provides a compact representation. Variations like the Seidel adjacency matrix aid in studying strongly regular graphs. The matrix's structure directly reflects graph degrees and connectivity, making it essential for algorithms in network analysis, physics, and social sciences.

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.