Adjacency matrix

Sponsorship the way you would do it

In mathematics and computer science, a finite graph is often represented by its adjacency matrix. The adjacency matrix of a directed or undirected graph (with n vertices, say) is the n-by-n matrix whose entry in row i and column j gives the number of edges from the i-th to the j-th vertex. (An alternative way to store graphs in computers, especially graphs with few edges, is given by the incidence matrix.)

The modified adjacency matrix is generated by replacing all entries greater than 1 in the adjacency matrix by 1.

Table of contents

1 Examples
2 Properties
3 Trade-offs as a data structure

Examples

The adjacency matrix for the example graph

Properties

The adjacency matrix of undirected graphs is always symmetric, and therefore has a complete set of eigenvalues and orthogonal eigenvector basis. The eigenvalues of a graph are the Spectrum of the Graph.

Suppose two directed or undirected graphs G₁ and G₂ with adjacency matrices A₁ and A₂ are given. G₁ and G₂ are isomorphic if and only if there exists a permutation matrix P such that

PA₁P⁻¹ = A₂.

In particular, A₁ and A₂ are similar and have therefore the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs.

If A is the adjacency matrix of the directed or undirected graph G, then the matrix Aⁿ (i.e. the matrix product of n copies of A) has an interesting interpretation: the entry in row i and column j gives the number of (directed or undirected) paths of length n from vertex i to vertex j.

The matrix I−A (where I denotes the n-by-n identity matrix) is invertible if and only if there are no directed cycles in the graph G. In this case, the inverse (I−A)⁻¹ has the following interpretation: the entry in row i and column j gives the number of directed paths from vertex i to vertex j (which is always finite if there are no directed cycles). This can be understood using the geometric series for matrices:

(I−A)⁻¹ = I + A + A² + A³ + ...

corresponding to the fact that the number of paths from i to j equals the number of paths of length 0 plus the number of paths of length 1 plus the number of paths of length 2 etc.

Trade-offs as a data structure

When used as a data structure, the main competitor for the adjacency matrix is the adjacency list. Because each entry in the adjacency matrix requires only one bit, they can be represented in a very compact way, occupying only n²/8 bytes of contiguous space, where n is the number of vertices. Besides just avoiding wasted space, this compactness encourages locality of reference.

On the other hand, for a sparse graph, adjacency lists win out, because they do not use any space to represent edges which are not present. Using a naive linked list implementation on a 32-bit computer, an adjacency list for an undirected graph requires about 16e bytes of storage, where e is the number of edges.

Noting that a graph can have at most n² edges, allowing loops, we can let d = e/n² denote the density of the graph. Then, 16e > n²/8, or the adjacency list representation occupies more space, precisely when d > 1/128. Thus a graph must be sparse indeed to justify an adjacency list representation.

Besides the space tradeoff, the different data structures also facilitate different operations. It's easy to find all vertices adjacent to a given vertex in an adjacency list representation; you simply read its adjacency list. With an adjacency matrix you must instead scan over an entire row, taking O(n) time. If you, instead, want to know if two given vertices have an edge between them, this can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the vertices with the adjacency list.