Adjacency matrices; walks; transition matrices practice questions.

A is the adjacency matrix of a graph. Determine what the entry in row i, column j of A³ represents.

• Walks of length 3 from i to j
• The degree of vertex i
• The shortest path from i to j
• The number of edges between i and j

Answer: Walks of length 3 from i to j

The (i, j) entry of Aⁿ counts the number of distinct walks of length n from vertex i to vertex j.

State a property that the adjacency matrix of an undirected graph with no loops must always have.

• Symmetric with zero diagonal
• It is upper triangular
• Every entry equals 1
• Its determinant is always zero

Answer: Symmetric with zero diagonal

For an undirected loop-free graph, A(i,j) = A(j,i) (symmetric) and A(i,i) = 0 since there are no loops on the diagonal.

A graph has adjacency matrix rows summing to 3, 2, 4 and 3 for its four vertices. Determine the total number of edges (undirected, no loops).

• 6
• 12
• 3
• 8

Answer: 6

A row sum equals the degree of that vertex. Sum of degrees = 3 + 2 + 4 + 3 = 12, so edges = 12 ÷ 2 = 6.

A transition matrix T for a Markov chain is given with columns representing current states. State which condition every column of T must satisfy.

• Each column sums to 1
• Each column sums to 0
• Each entry is greater than 1
• The diagonal entries are all 0

Answer: Each column sums to 1

In a column-based (stochastic) transition matrix every column represents the probabilities of moving from one state to all states, so each column must sum to 1.

A Markov chain has transition matrix T (columns = current state) with T = [[0.8, 0.3], [0.2, 0.7]] and initial state vector s₀ = [100, 0]ᵀ. Calculate the number in state 1 after one step.

• 80
• 20
• 30
• 110

Answer: 80

s₁ = T s₀; the first component = 0.8 × 100 + 0.3 × 0 = 80.

A regular Markov chain has transition matrix T = [[0.6, 0.5], [0.4, 0.5]] (columns = current state). Determine its steady-state (equilibrium) proportion in state 1.

• 5/9
• 4/9
• 1/2
• 6/11

Answer: 5/9

Solving 0.6x + 0.5y = x with x + y = 1 gives 0.4x = 0.5y, so x = 5/9 and y = 4/9.