Companion Matrices and Recurrences
Turn a second-order recurrence into a matrix power and compare growing, oscillating and vanishing sequences.
Free theory articleTurn a second-order recurrence into a matrix power and compare growing, oscillating and vanishing sequences.
Concept & interpretation
A linear recurrence relation like xk+2 = a xk+1 + b xk can be rewritten as a matrix equation involving a state vector [xk+1, xk]T. The matrix that advances this state by one step is known as the companion matrix. By computing powers of this matrix, we can instantly jump to any term in the sequence without calculating all the intermediate values.
Match the matrix powers in the experiment
Open Companion Matrices and Recurrences. Set the parameters to test the worked example.
- Set Coefficient a = -1 and Coefficient b = 2. Notice the characteristic polynomial is λ2 + λ - 2.
- Set x0 = 1 and x1 = 3.
- Change Index n to 5. Verify that Selected xn is 23.
- Check that the C power n matrix is [[-21, 22], [11, -10]] and the State vector matches the computed [-41, 23]T.
- Change Index n to 0. Notice that C0 is the identity matrix [[1, 0], [0, 1]], and the state vector is simply the initial state [3, 1]T, which means x0 = 1.