The Adjacency Matrix of a Graph

Videos

No videos for today.

Reading

Today, your reading is a very brief note by me. There is no additional reading required to prepare for the warmup problems.

In this class, “matrix” just means “square array of numbers.”

The adjacency matrix of a graph $G$ with $n$ nodes is an $n\times n$ binary matrix that we often call $\mathbf{A}$. It’s entries are given by

\[ \begin{aligned} a_{ij} = \begin{cases} 1 &\quad \text{there is an edge between node $i$ and node $j$} \\ 0 &\quad \text{there is no edge between node $i$ and node $j$} \end{cases} \end{aligned} \]

$a_{ij}$ is the entry of $\mathbf{A}$ that is in the $i$th row and $j$th column.

For example, here is a graph with $n = 6$ nodes:

Here is the adjacency matrix of this graph:

\[ \begin{aligned} \mathbf{A} = \left[\begin{matrix} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 \end{matrix}\right] \end{aligned} \]

The entry of $a_{34} = 1$ (look at the third row and fourth column) means that there is an edge between node $3$ and node $4$.

An edge between $i$ and $j$ corresponds to two entries of $\mathbf{A}$: the $a_{ij}$ entry and the $a_{ji}$ entry.

Warmup

Problem 1

Let $G$ be an undirected graph with $n$ nodes, and let $\mathbf{A}$ be its adjacency matrix.

Part A

What is $\sum_{j \in V} a_{ij}$ in terms of quantities we have previously defined in this class?

Part B

Suppose that $G$ is a complete graph (i.e. a clique). What is the value of $\sum_{i \in V} \sum_{j \in V} a_{ij}$? Your answer should include no variables other than $n$.

Part C

Suppose that $G$ is a tree. What is the value of $\sum_{i \in V} \sum_{j \in V} a_{ij}$? Your answer should include no variables other than $n$.

Problem 2

Part A

A walk of length $k$ is a walk that traverses exactly $k$ edges. For example, a walk of length $1$ traverses only a single edge. $(1, 2)$ is a walk of length 1 in the example graph above. $(1, 2), (2, 3)$ is a walk of length 2, but not a walk of length 1.

How many walks of length 1 from node $4$ to node $5$ are there in the example graph shown in the reading?
How many walks of length 1 are there from node $4$ to node $2$?
What is entry $a_{45}$ in the adjacency matrix? What is entry $a_{42}$?
Make a conjecture: what information does entry $a_{ij}$ contain about the the number of walks of length $1$ from node $i$ to node $j$?

Part B

Let’s define a new number with the following formula:

\[ \begin{aligned} b_{ij} = \sum_{k = 1}^n a_{ik}a_{kj}\;. \end{aligned} \]

If you have used matrix multiplication before, $b_{ij}$ is the $ij$th entry of $\mathbf{A}^2$.

Using the example graph, compute the number of walks of length 2 from node 1 to node 2, node 1 to node 4, node 3 to node 4, and node 1 to node 5.
Using the definition, compute $b_{12}$, $b_{14}$, $b_{34}$, and $b_{15}$.
State a conjecture describing the relationship between $b_{ij}$ and the number of walks of length 2.

Part C

The counting principles of addition and multiplication both appear in the formula for the number of walks of length 2 between nodes $i$ and $j$ as given above. Explain the role of each of these principles in this formula. Why do we multiply $a_{ik}$ by $a_{kj}$? Why do we add across all possibilities $k$? In your response, please include the phrases “sequential choice” and “disjoint choice” or similar.