The Adjacency Matrix

v₁, , v_n

n n

in which a_ij = the number of arrows from v_i to v_j if G is a directed graph, and a_ij = the number of edges connecting v_i to v_j if G is an undirected graph.

Examples

4. The adjacency matrix of digraph

   

   is

   

5. The adjacency matrix of graph

   

   is

   

Let A = (a_ij) and B = (b_ij) be two n n matrices, the product of A and B, i.e. AB, is another n n matrix C=(c_ij) in which \dis c_ij = ⁿ_k=1   a_ikb_kj, i.e.

To brush up on the matrix multiplications, please consult the Preliminary Mathematics at the very beginning of these notes.

Theorem Let G be a directed or undirected graph of n vertices v₁, v₂, , v_n, and A be the adjacency matrix of G. Then for any positive integer m, the (i, j)-th entry of A^m is equal to the number of walks of length m from v_i to v_j, where i,j = 1, 2, n.

Proof Let S_m denote the statement that (i, j)^th entry of A^m is equal to the number of walks of length m from v_i to v_j. Then for m = 1, S₁ is true because the adjacency matrix A is defined that way. For the induction purpose we now assume S_k is true with k 1. Let B = (b_ij) = A^k, then b_sj = the number of walks of length k from v_s to v_j due to the induction assumption. Hence

(i,j)-th element of Ak+1	=	(i,j)-th element of AB
	=
	=	the number of walks of length k+1 from vi to vj
		(taking any vertex as the 2nd vertex)

i.e. S_k+1 is true. Hence S_m is true for all m 1, and the proof of the theorem is thus completed.

Example

6. Consider the digraph

   

   which has the adjacency matrix A below

   

   Since

   

   we see there are exactly \shade{2} walks of length 2 that start at v₃ and end at v₁. Since

   

   has only 0's in the third column, we conclude that no vertex can reach v₃ via a walk of nonzero length.