Consider the graph We associate to this graph the matrix A

Consider the graph We associate to this graph the matrix A = (0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0). A computer tells you that A^3 = (2 1 2 1 1 2 1 1 1 0 1 0 2 2 4 0 2 1 1 0 2 1 0 2 3 2 2 1 2 2 1 0 2 1 0 2), A^5 = (8 6 9 2 6 5 3 2 6 1 2 3 9 5 16 4 5 10 6 4 5 2 4 4 10 8 13 2 8 6 6 4 5 2 4 4) A^10 = (265 181 365 84 181 212 128 84 181 44 84 109 365 240 502 125 240 306 181 125 240 56 125 140 349 237 490 112 237 284 181 125 240 56 125 140) (a) How many paths in the graph go from the vertex to itself in three steps? (b) Give an interpretation of the entry a_i, j of the matrix A^n, using the graph. (d) Starting from the vertex, are there more paths ending at or at after 10 steps? (e) lf you start from the vertex and perform ten steps at random, with equal probability to choose any arrow, do you have more chances to end up at or at ?

Solution

a.) in A³, a₃₃=4, i.e the number of paths that vertex 3 can come to itself in 3 steps is 4.

b.) a_ij in the matrix Aⁿ is the number of paths that vertex i can go to the vertex j in n steps.

d.) After 10 steps, in the matrix A¹⁰, a_42¹⁰ =125 and a₄₄¹⁰=56, so we can say that there more paths ending at 2.

e.) Since there is equal probability to choose any arrow, the probability is more to end up vertex 2, since 125 paths are presented towards to it than to vertex 4.