Adjacency Matrices

Adjacency Matrix of a Graph

Definition: For a graph $G$ on vertices $x_1$, $x_2$, …, $x_n$, the Adjacency Matrix of $G$ denoted by $A(G)$ is the $n \times n$ matrix whose $(i, j)^{\mathrm{th}}$ entries correspond to the number of edges from $x_i$ to $x_j$.

Let's first construct the adjacency matrix for the following simple graph:

First, let's make a table where we put a "$1$" if we can get from some vertex $i$ to another vertex $j$. For example, we can get from vertex $b$ to vertex $c$, so we will put a $1$ in the second row and third column.

	Vertex $a$	Vertex $b$	Vertex $c$	Vertex $d$	Vertex $e$
Vertex $a$	$0$	$1$	$1$	$0$	$1$
Vertex $b$	$1$	$0$	$1$	$0$	$0$
Vertex $c$	$1$	$1$	$0$	$1$	$1$
Vertex $d$	$0$	$0$	$1$	$0$	$0$
Vertex $e$	$1$	$0$	$1$	$0$	$0$

The adjacency matrix for this graph will simply be the table above converted into matrix form, or rather:

(1)

\begin{align} A(G) = \begin{bmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align}

We can also product adjacency matrices for graphs with multiple edges and loops. Let's look at the following graph for example:

The adjacency matrix for the graph is as follows:

(2)

\begin{align} A(G) = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 3 \\ 0 & 4 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 2 & 0 & 0 & 1 \\ 3 & 0 & 1 & 1 & 1 & 0 \\ \end{bmatrix} \end{align}

We can also use adjacency matrices in directed graphs such as the following example:

(3)

\begin{align} A(G) = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \end{align}

We will now state the properties of adjacency matrices in the following propositions.

Proposition 1: If the adjacency matrix $A(G)$ is not of a digraph, then $A(G)$ is symmetric (symmetric around the main diagonal), that is $A(G) = A^{T}(G)$ (the adjacency matrix of $G$ is the same as the adjacency matrix of $G$ transposed). Alternatively one can say $a_{ij} = a_{ji}$ $\forall \: i, j$.

This property holds since one can traverse some vertex $x_1$ to $x_2$ and $x_2$ to $x_1$ without any problem. Because of this, $a_{ij} = a_{ji}$ $\forall \: i, j$, or rather, $A(G) = A^T(G)$.

Note that directed graphs can also have their adjacency matrices symmetric. However, if $A(G) ≠ A^T(G)$, then the graph must be a digraph.

Proposition 2: If the adjacency matrix $A(G)$ of a graph $G$ has no loops, then all entries on the main diagonal of $A(G)$ are zeroes. Hence $a_{ij} = 0$ whenever $i = j$ $\forall \: i, j$.

All entries on the main diagonal are defined as $a_{ij}$ where $i = j$. Hence all entries on the main diagonal correspond to edges going from some vertex $x_i$ to $x_i$ or $x_j$ to $x_j$ which are loops.

Proposition 3: If $A(G)$ is the $n \times n$ adjacency matrix of a graph $G$ that is not a digraph and $x_j$ and $x_i$ are vertices such that $x_j, x_i \in V(G)$ then: $\sum_{k = 1}^{n} a_{kj} = a_{1j} + a_{2j} + ... + a_{nj} = \deg (x_j)$ (the sum of all entries in column $j$ is equal to the degree of vertex $x_j$). Additionally $\sum_{k = 1}^{n} a_{ik} = a_{i1} + a_{i2} + ... + a_{in} = \deg (x_i)$ (the sum of all entries in row $i$ is equal to the degree of vertex $x_i$).

Each entry in column $j$ corresponds to the number times a vertex $x_k$ for $1 \leq k \leq n$ is adjacent to vertex $x_j$. So then $\sum_{k = 1}^{n} a_{kj} = a_{1j} + a_{2j} + ... + a_{nj}$ is going to equal to the degree of the vertex $x_j$.

Since $A(G) = A^T(G)$, then the same property holds for the sum of the entries in a row $i$, that is $\sum_{k = 1}^{n} a_{ik} = a_{i1} + a_{i2} + ... + a_{in} = \deg (x_i)$.

Proposition 4: If $A(G)$ is the $n \times n$ adjacency matrix of a digraph $G$, and $x_j$ and $x_i$ are vertices such that $x_j, x_i \in V(G)$, then $\sum_{k = 1}^{n} a_{kj} = a_{1j} + a_{2j} + ... + a_{nj} = \deg^- (x_j)$ (the sum of all entries in column $j$ is equal to the in-degree of vertex $x_j$) and $\sum_{k = 1}^{n} a_{ik} = a_{i1} + a_{i2} + ... + a_{in} = \deg^+ (x_i)$ (the sum of all entries in row $i$ is equal to the out-degree of a vertex $x_i$.

Each entry in column $j$ corresponds to the number of arcs going from $x_n$ to $x_j$ so the sum of all entries in column $j$ corresponds to the in-degree of a vertex $x_j$. Similarly, each entry in row $i$ corresponds to the number of arcs from $x_i$ to $x_n$ so the sum of all entries in row $i$ corresponds to the out-degree of a vertex $x_i$.

Proposition 5: If the adjacency matrix $A(G)$ of a graph $G$ does not contain multiple edges, then $\forall \: i, j$, $a_{ij} = 0$ or $a_{ij} = 1$. If the adjacency matrix $A(G)$ of a graph contains multiple edges, then there exist $a_{ij} > 1$ for some $a_{ij}$.

If a graph does not contain multiple edges, then there can at most be $1$ edge from a vertex $x_k$ to $x_l$. Hence the entry $a_{kl} = 0$ or $a_{kl} = 1$.