1.   (a)    i. The adjacency matrix corresponding to the labelled graph is

For an adjacency matrix M the entry (Mn)ij  is the number of paths of length n starting at vertex (i) and ending at vertex (j) in the corresponding labelled graph. Taking n = 4 in our case we nd

Therefore there are eight paths of length four starting at vertex-2 and ending at vertex-3.

ii. The same graph labelled under  is

and the new adjacency matrix is

Writing (i) = (P(i)), then P is the permutation

P(1) = 2,    P(2) = 3,    P(3) = 1.

Let U be the permutation matrix with entries Uij  = i,P(j):

We write M for the adjacency matrix of the same graph, now with vertices labelled according to .  It was shown during the Course that M = UTM U. Then

This agrees with the adjacency matrix found earlier.

(b) The i-th diagonal entry of M2 is MijMji  (sum over j implied). For each j, this is the number of edges from vertex i to vertex j, times the number of edges from vertex j

back to vertex i.

Each of these terms must be zero for (M2)ii  to be zero. We deduce that if there is an edge from vertex i to vertex j, then there is no edge from j back to i.

The only solution to this is x = 3/7, y = 2/7. Therefore the sole stationary state of the given graph is (3/7, 2/7, 2/7).

(b) Start by nding the spectrum of W. Its characteristic polynomial is  (1/6+x)(1/2  x)(1  x), so the eigenvalues of W are  1/6, 1/2 and 1, all having algebraic multi- plicity one.                                                                                                           [2] Because all eigenvalues are distinct the matrix is diagonalisable. The Jordan form J will be diagonal, with the eigenvalues as diagonal entries. Nevertheless we still need to calculate the eigenvectors in order to have the change-of-basis matrix that takes

Jn  to Wn  and so to know the large-n behaviour of the latter.

Let us nd the eigenvectors associated with eigenvalue -1/6.

As discussed during the Course, a Jordan block carrying an eigenvalue of modulus less than one converges to a zero matrix upon raising it to increasingly higher powers.

(c) It follows from the above that

Calling this limit W∞, any initial state (x,y, 1  x  y) will converge under time

evolution to the state (x,y, 1  x  y)W∞ .

In our case

(x,y, 1  x  y)W∞ = (3/7, 2/7, 2/7),

as was to be expected, (3/7, 2/7, 2/7) being the only stationary state of the given

graph.

3.   (a) Start with the transition matrix of the graph:

Let  be the probability that a random walk on the graph starts at vertex-1 and

returns to it in exactly n steps. Inspection of the graph gives

For n  3 we proceed as explained in the Course. The probabilities of the rst step to lead to vertices 2 or 3 are W12  or W13  respectively. Transitions between vertices 2 and 3 correspond to the submatrix of W which excludes row and column one. The last step, from vertices 2 or 3 back to vertex 1, has probabilities W21  or W31 respectively. Therefore, for n  3 we have

Note that this result is actually valid also for n = 2, so generally:

(b) If the sum of all  for n   1 equals one then any random walk on the graph,

which starts from vertex-1, will return to it after some number of steps.

Therefore the answer is in the armative.

(c) The expected (or average) time of rst return for a random walk on the graph is

That is, the average number of steps required for a random walk which starts at vertex-1 to return to it for the rst time is 5/2.

4.   (a) The degree formula for vertices gives 5V5 + 6V6  = 2|E|,