Question

[1 1 2]

5. Let A 1 0
10
(a) (6 points) Find A². (Note that A² = A A, the product of the matrix A with itself.)
(b) (4 points) Let G be the graph with vertices V1, V2, and v3 and with A as its adjacency
matrix. Using part (a) and without actually drawing the graph G, find the number of
walks of length 2
i. from v₁ to v3
ii. from v₁ to v₁.

Answer 1

(a) Multiplying the matrix A by itself,

A2 = [[1 1 2]

[1 0 1]] x [[1 1 2]

[1 0 1]]

= [[1*1 + 1*1 + 2*1, 1*1 + 0*1 + 1*2],

[1*1 + 1*0 + 1*1, 1*0 + 0*0 + 1*0]]

= [[4, 3],

[2, 1]]

(b) i. The (1,3) entry of A2 is the number of walks of length 2 from v1 to v3. So there is 3 such walks.

ii. The (1,1) entry of A2 is the number of walks of length 2 from v1 to v1. So there are 4 such walks.