Variation of the "Drunken Sailor Problem" There is a famous probability problem that states: If a drunken sailor leaves the pub and had too much to drink so that they do not know how to get back, could they eventually get back with a finite amount of random steps, or is it possible that they'll get lost forever? (the answer ends up being that they'll always find their way back if the choice is always random!) This requires a bit more than what we have right now, but here is a variation. Instead of a grid, like the original problem, we'll think of a long street. We can track the sailor's possible positions at any point in time using matrix algebra. Some definitions before we can begin: Remember that the diagonal of a (square) matrix are all entries aj, i where the row coordinate is equal to the column coordinate. The super-diagonal are all the entries one position to the right of the diagonal. (Alternatively, all entries one position above the diagonal) The sub-diagonal are all entries one position to the left of the of the diagonal. (Alternatively all entries one position below the diagonal)

a) For 2x2 and 3x3 matrices, write the matrices that correspond to l's on the super-diagonal (zeroes everywhere else). Do the same for the sub-diagonal

b) Write two equivalent subscript notations for the sub and super diagonal of a matrix (e. g. ai, is the subscript notation for the diagonal)

c) The matrix that has l's on the super-diagonal and sub-diagonal is an ad- jacency matrix (symmetric, O's on diagonal and only l's as entries). Draw or explain what the graph associated looks like in any dimension.

d) If this n x n adjacency matrix is A, calculate A?.

e) Find the diagonal for A" if n is odd (Hint: It is easier to explain via the graph!) f) Interpret what aj means in the drunken sailor problem for any power of A.