Definition:Adjacency Matrix
Definition
An adjacency matrix is a matrix which describes a graph by representing which vertices are adjacent to which other vertices.
If $G$ is a graph of order $n$, then its adjacency matrix is a square matrix of order $n$, where each row and column corresponds to a vertex of $G$.
The element $a_{i j}$ of such a matrix specifies the number of edges from vertex $i$ to vertex $j$.
An adjacency matrix for a simple graph and a loop-digraph is a logical matrix, that is, one whose elements are all either $0$ or $1$.
An 'adjacency matrix for an undirected graph is symmetrical about the main diagonal.
This is because if vertex $i$ is adjacent to vertex $j$, then $j$ is adjacent to $i$.
An adjacency matrix for a weighted graph or network contains the weights of the edges.
Also known as
An adjacency matrix is also known as a vertex matrix.
Examples
Simple Graph
The elements of the adjacency matrix of a simple graph are $0$ and $1$, and the diagonal elements are all zero:
$\qquad \begin{pmatrix}
0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}$
Multigraph
The elements of the adjacency matrix of a multigraph are integers, and the diagonal elements are all zero:
$\qquad \begin{pmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 2 & 1 & 0 & 0 \\
0 & 2 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 3 \\
0 & 0 & 0 & 0 & 3 & 0 \\
\end{pmatrix}$
Digraph
The adjacency matrix for a directed graph is no longer symmetrical about the main diagonal:
$\qquad \begin{pmatrix}
0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
\end{pmatrix}$
Loop-Graph
The elements on the main diagonal of the adjacency matrix for a loop-graph are not all non-zero:
$\qquad \begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 2 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 2 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 \\
\end{pmatrix}$
Loop-Multigraph
The elements of the adjacency matrix of a loop-multigraph are integers, and this time some of the diagonal elements are non-zero:
$\qquad \begin{pmatrix}
0 & 2 & 0 & 0 & 0 & 0 \\
2 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 2 & 1 & 0 & 0 \\
0 & 1 & 1 & 2 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 3 \\
0 & 0 & 0 & 1 & 3 & 0 \\
\end{pmatrix}$
Loop-Digraph
The adjacency matrix for a loop-digraph is not only not symmetrical about the main diagonal, it also has non-zero elements on that main diagonal:
$\qquad \begin{pmatrix}
1 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 \\
\end{pmatrix}$
Network
The adjacency matrix for a general network can have any numbers in any of its elements:
$\qquad \begin{pmatrix}
0 & 1.2 & 0 & 0.5 \\
0 & 0 & 0 & 3.4 \\
0 & 0 & 0 & 0 \\
4.1 & 0 & 10.1 & 0 \\
\end{pmatrix}$
Also see
- Results about adjacency matrices can be found here.
Sources
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): adjacency matrix
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): adjacency matrix
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): adjacency matrix
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): adjacency matrix