Adjacency matrix

In graph theory, the adjacency matrix ^[1][2] of a graph is a square matrix indexed by the vertex set, whose entries record which pairs of vertices are adjacent. Together with the incidence matrix, it is one of the standard matrix graph representations.

Definition

---

Definition 1 (Adjacency matrix)

Let $G=(V,E)$ be a graph with vertex set $V=\{v_1,\dots ,v_n\}$. An adjacency matrix of $G$ is an $n\times n$ square matrix $\mathbf{A}=(a_{ij})$, with rows and columns indexed by $V$, such that

$$a_{ij}=0\text{ if }{v}_i\text{ and }{v}_j\text{ are not adjacent},$$

and $a_{ij}\ne 0$ if $v_i$ and $v_j$ are adjacent. The concrete nonzero value depends on the class of graph under consideration.

Corollary 1 (Walk count)

For every $k\ge 1$, the $(i,j)$ entry of ${\mathbf{A}}^k$ equals the number of walks of length $k$ from $v_i$ to $v_j$ in $G$.

Proof of Corollary 1

We proceed by induction on $k$.

Base case ($k=1$): By Definition 1, $({\mathbf{A}}^1{)}_{ij}=a_{ij}$, which is nonzero exactly when $v_i$ and $v_j$ are adjacent, that is, exactly when the edge between them forms a walk of length $1$ from $v_i$ to $v_j$.

Inductive step: assume $({\mathbf{A}}^{k-1}{)}_{i\ell }$ counts the walks of length $k-1$ from $v_i$ to $v_{\ell }$, for every $\ell$. By matrix multiplication,

$$({\mathbf{A}}^k{)}_{ij}=\sum _{\ell =1}^n({\mathbf{A}}^{k-1}{)}_{i\ell }{a}_{\ell j}.$$

Every walk of length $k$ from $v_i$ to $v_j$ consists of a walk of length $k-1$ from $v_i$ to some vertex $v_{\ell }$ adjacent to $v_j$, followed by the edge from $v_{\ell }$ to $v_j$. Summing $({\mathbf{A}}^{k-1}{)}_{i\ell }$ over every $v_{\ell }$ adjacent to $v_j$ therefore counts exactly the walks of length $k$ from $v_i$ to $v_j$. $\square$

Variants

---

Each of the following variants specializes Definition 1 to a class of graphs by fixing what the nonzero entries $a_{ij}$ record.

Undirected graph

---

Definition 2 (Adjacency matrix of an undirected graph)

For a simple undirected graph $G=(V,E)$ with vertex set $V=\{v_1,v_2,\dots ,v_n\}$ and edge set $E=\{e_1,e_2,\dots ,e_m\}$, the adjacency matrix $\mathbf{A}=(a_{ij})$ is the $n\times n$ square binary matrix given by

$$a_{ij}=\{\begin{array}{ll}1& \text{if }\{v_i,v_j\}\in E\text{ and }i\ne j\\ 0& \text{otherwise}\end{array}$$

Properties

---

Lemma 1 (Symmetry)

The adjacency matrix of a simple undirected graph is symmetric.

Proof of Lemma 1

By Definition 2, $a_{ij}=1$ iff $\{v_i,v_j\}\in E$ and $i\ne j$. Since $\{v_i,v_j\}=\{v_j,v_i\}$, this condition is symmetric in $i$ and $j$, so $a_{ij}=1$ iff $a_{ji}=1$, and likewise $a_{ij}=0$ iff $a_{ji}=0$. Hence $a_{ij}=a_{ji}$ for all $i,j$, so $\mathbf{A}={\mathbf{A}}^{\mathsf{T}}$. $\square$

Examples

---

Example 1 (Cycle graph $C_4$)

For the cycle graph $C_4$ given by $G=(V,E)$ with $V=\{v_1,v_2,v_3,v_4\}$ and $E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_1\}\}$, the adjacency matrix is

$$\mathbf{A}=\left[\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]$$

By Corollary 1, the entries of ${\mathbf{A}}^2$ count walks of length $2$:

$${\mathbf{A}}^2=\left[\begin{array}{cccc}2& 0& 2& 0\\ 0& 2& 0& 2\\ 2& 0& 2& 0\\ 0& 2& 0& 2\end{array}\right]$$

For instance, $({\mathbf{A}}^2{)}_{11}=2$ counts the two walks of length $2$ from $v_1$ back to itself, $v_1,v_2,v_1$ and $v_1,v_4,v_1$, while $({\mathbf{A}}^2{)}_{12}=0$ reflects that no walk of length $2$ joins $v_1$ and $v_2$.

Directed graph

---

Definition 3 (Adjacency matrix of a directed graph)

For a directed graph $G=(V,E)$ with vertex set $V=\{v_1,\dots ,v_n\}$, the adjacency matrix $\mathbf{A}=(a_{ij})$ is the $n\times n$ square matrix given by

$$a_{ij}=\{\begin{array}{ll}1& \text{if }(v_i,v_j)\in E\\ 0& \text{otherwise}\end{array}$$

Properties

---

Lemma 2 (Asymmetry)

The adjacency matrix of a directed graph need not be symmetric.

Proof of Lemma 2

By Definition 3, $a_{ij}=1$ iff $(v_i,v_j)\in E$, while $a_{ji}=1$ iff $(v_j,v_i)\in E$. A directed edge $(v_i,v_j)\in E$ does not require the reverse edge $(v_j,v_i)\in E$, so it is possible to have $a_{ij}=1$ while $a_{ji}=0$. Hence $\mathbf{A}\ne {\mathbf{A}}^{\mathsf{T}}$ in general. $\square$

Examples

---

Example 2 (Directed cycle graph)

For $G=(V,E)$ with $V=\{v_1,v_2,v_3\}$ and $E=\{(v_1,v_2),(v_2,v_3),(v_3,v_1)\}$, the adjacency matrix is

$$\mathbf{A}=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]$$

which is not symmetric, in agreement with Lemma 2. By Corollary 1, the entries of ${\mathbf{A}}^2$ count walks of length $2$:

$${\mathbf{A}}^2=\left[\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]$$

For instance, $({\mathbf{A}}^2{)}_{13}=1$ counts the unique walk of length $2$ from $v_1$ to $v_3$, namely $v_1,v_2,v_3$, while $({\mathbf{A}}^2{)}_{11}=0$ reflects that there is no walk of length $2$ from $v_1$ back to itself.

Bipartite graph

---

Definition 4 (Adjacency matrix of a bipartite graph)

Let $G=(U,V,E)$ be a bipartite graph with vertex set $U\cup V$ such that $U\cap V=\varnothing$, where $U=\{u_1,\dots ,u_m\}$ and $V=\{v_1,\dots ,v_n\}$, so $|U|+|V|=m+n$. Let $w_1,\dots ,w_{m+n}$ be the vertices of $G$ listed with $U$ first and $V$ second, so $w_i=u_i$ for $1\le i\le m$ and $w_{m+i}=v_i$ for $1\le i\le n$. The adjacency matrix of $G$ is the $(m+n)\times (m+n)$ square matrix $\mathbf{A}=(a_{ij})$, with rows and columns indexed by $w_1,\dots ,w_{m+n}$, given by

$$a_{ij}=\{\begin{array}{ll}1& \text{if }\{w_i,w_j\}\in E\\ 0& \text{otherwise}\end{array}$$

Properties

---

The bipartite vertex ordering forces the top-left and bottom-right blocks of $\mathbf{A}$ to vanish, since no edge joins two vertices within $U$ or within $V$.

Lemma 3 (Bipartite block structure)

With rows and columns ordered as $U$ followed by $V$, the adjacency matrix of a bipartite graph $G=(U,V,E)$ has the block form

$$\mathbf{A}=\left[\begin{array}{cc}{0}_{m\times m}& \mathbf{B}\\ {\mathbf{B}}^{\mathsf{T}}& 0_{n\times n}\end{array}\right]$$

where $\mathbf{B}=(b_{kl})$ is the $m\times n$ matrix with $b_{kl}=1$ if $\{u_k,v_l\}\in E$ and $b_{kl}=0$ otherwise.

Proof of Lemma 3

By definition of a bipartite graph, no edge joins two vertices of $U$ or two vertices of $V$. By Definition 4, this means $a_{ij}=0$ whenever $i,j\le m$ or $i,j>m$, so the top-left $m\times m$ and bottom-right $n\times n$ blocks of $\mathbf{A}$ are zero. For $i\le m<j$, $a_{ij}=1$ iff $\{u_i,v_{j-m}\}\in E$, which is exactly the entry $b_{i,j-m}$, so the top-right block equals $\mathbf{B}$. By Lemma 1, $\mathbf{A}$ is symmetric, so the bottom-left block equals ${\mathbf{B}}^{\mathsf{T}}$. $\square$

Examples

---

Example 3 (Complete bipartite graph $K_{2,3}$)

For the complete bipartite graph $K_{2,3}$ with $U=\{u_1,u_2\}$, $V=\{v_1,v_2,v_3\}$, and $E=\{\{u_1,v_1\},\{u_1,v_2\},\{u_1,v_3\},\{u_2,v_1\},\{u_2,v_2\},\{u_2,v_3\}\}$, ordering rows and columns as $u_1,u_2,v_1,v_2,v_3$, the adjacency matrix is

$$\mathbf{A}=\left[\begin{array}{ccccc}0& 0& 1& 1& 1\\ 0& 0& 1& 1& 1\\ 1& 1& 0& 0& 0\\ 1& 1& 0& 0& 0\\ 1& 1& 0& 0& 0\end{array}\right]$$

References

1. [1]

   “Adjacency matrix”, Wikipedia, Available: https://en.wikipedia.org/wiki/Adjacency_matrix, Accessed: 2026-07-15 ↩

2. [2]

   “Adjacency Matrix”, Wolfram MathWorld, Available: https://mathworld.wolfram.com/AdjacencyMatrix.html, Accessed: 2026-07-15 ↩