# 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)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)We can also use adjacency matrices in directed graphs such as the following example:

(3)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$.