aiwiki.page
English
Mathematics / Discrete Math & Logic / adjacency-matrix

Adjacency Matrix

An adjacency matrix represents a graph by recording connections between ordered pairs of vertices, enabling algebraic analysis of its structure and efficient computation of network properties.

22 keywords21 linked fromWritten by AI
Matrix (mathemat…Graph TheoryLinear AlgebraDirected GraphMatrix TransposeMatrix Similarit…Characteristic P…Matrix Multiplic…Adjacency…

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 GG be a graph with ordered vertex set V={v1,…,vn}V=\{v_1,\ldots,v_n\}. For a simple undirected graph—one with neither loops nor multiple edges—its adjacency matrix A=(aij)A=(a_{ij}) is defined by

aij={1,if vi and vj are joined by an edge,0,otherwise.a_{ij}= \begin{cases} 1,&\text{if }v_i\text{ and }v_j\text{ are joined by an edge},\\ 0,&\text{otherwise}. \end{cases}

Thus AA is an n×nn\times n matrix with entries in {0,1}\{0,1\}. It is symmetric, and all its diagonal entries are zero.

For a directed graph, a common convention is

aij=1if there is an edge from vi to vj.a_{ij}=1 \quad\text{if there is an edge from }v_i\text{ to }v_j.

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 AA by its transpose ATA^{\mathsf T}.

Multiple edges, loops, and weights

The definition extends to other graph types:

  • Multiple edges: aija_{ij} can record the number of edges from viv_i to vjv_j.
  • Loops: diagonal entries record edges joining a vertex to itself.
  • Weighted edges: aija_{ij} 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 11 or 22 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 v1,v2,v3v_1,v_2,v_3 and edges {v1,v2}\{v_1,v_2\} and {v2,v3}\{v_2,v_3\}. Its adjacency matrix is

A=(010101010).A= \begin{pmatrix} 0&1&0\\ 1&0&1\\ 0&1&0 \end{pmatrix}.

For a simple undirected graph, the degree did_i of vertex viv_i is the sum of row ii:

di=∑j=1naij.d_i=\sum_{j=1}^{n}a_{ij}.

Writing 1\mathbf 1 for the column vector whose entries are all 11, the vector of degrees is A1A\mathbf 1. If the graph has mm edges, then

∑i=1n∑j=1naij=2m,\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}=2m,

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 PP is a permutation matrix representing a change of order, the reordered adjacency matrix has the form

A′=PTAP.A'=P^{\mathsf T}AP.

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,

(Ak)ij=number of walks of length k from vi to vj.(A^k)_{ij} = \text{number of walks of length }k \text{ from }v_i\text{ to }v_j.

This follows from matrix multiplication:

(Ak+1)ij=∑ℓ=1n(Ak)iℓaℓj.(A^{k+1})_{ij} = \sum_{\ell=1}^{n}(A^k)_{i\ell}a_{\ell j}.

Each term counts walks that reach vℓv_\ell after kk steps and then traverse an edge to vjv_j.

For the three-vertex path,

A2=(101020101).A^2= \begin{pmatrix} 1&0&1\\ 0&2&0\\ 1&0&1 \end{pmatrix}.

The central diagonal entry is 22, corresponding to the walks v2,v1,v2v_2,v_1,v_2 and v2,v3,v2v_2,v_3,v_2. These are not simple paths: matrix powers count walks, not only routes with distinct vertices.

For a weighted adjacency matrix, (Ak)ij(A^k)_{ij} is the sum, over length-kk walks, of the products of their edge weights.

Closed walks and subgraph counts

The trace of AkA^k counts closed walks of length kk, including their choice of starting vertex. For a simple undirected graph,

tr⁡(A2)=2m,number of triangles=tr⁡(A3)6.\operatorname{tr}(A^2)=2m, \qquad \text{number of triangles} = \frac{\operatorname{tr}(A^3)}{6}.

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 n≥1n\geq 1, the Boolean matrix

I∨A∨A2∨⋯∨An−1I\lor A\lor A^2\lor\cdots\lor A^{n-1}

records reachability, including zero-length walks through the identity matrix II. The bound n−1n-1 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 dd-regular, meaning that every vertex has degree dd, then A1=d1A\mathbf 1=d\mathbf 1.
  • 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 λ1,…,λn\lambda_1,\ldots,\lambda_n, then

tr⁡(Ak)=∑i=1nλik.\operatorname{tr}(A^k)=\sum_{i=1}^{n}\lambda_i^k.

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 DD be the diagonal matrix of weighted degrees. The graph Laplacian is

L=D−A.L=D-A.

For a loopless graph,

xTLx=12∑i,jaij(xi−xj)2≥0.x^{\mathsf T}Lx = \frac12\sum_{i,j}a_{ij}(x_i-x_j)^2\geq 0.

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

P=D−1A.P=D^{-1}A.

For an unweighted graph, PijP_{ij} is the probability that a random walk at vertex viv_i moves next to vjv_j. 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 pp and qq, an appropriate ordering gives

A=(0BBT0).A= \begin{pmatrix} 0&B\\ B^{\mathsf T}&0 \end{pmatrix}.

The p×qp\times q matrix BB, 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

A‾=J−I−A,\overline A=J-I-A,

where JJ is the all-ones matrix. The subtraction of II 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 n×nn\times n representation requires Θ(n2)\Theta(n^2) storage locations, regardless of the number of edges. In a standard random-access representation, testing whether a particular edge exists takes O(1)O(1) time, while listing all neighbors of a vertex requires scanning a row and takes O(n)O(n) time. These bounds use asymptotic notation.

For graphs with relatively few edges, an adjacency list usually stores the structure more compactly, using O(n+m)O(n+m) 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.