Companion Matrices and Recurrences
Turn a second-order recurrence into a matrix power and compare growing, oscillating and vanishing sequences.
By Riano · Published · Updated · Report a correction
Matrix Powers and Linear Recurrences
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.
The Companion Matrix
Let the state at index k be vk = [xk+1, xk]T. We want to find a matrix C such that vk+1 = C vk.
We know that vk+1 = [xk+2, xk+1]T. Using the recurrence relation, we substitute xk+2 = a xk+1 + b xk. This gives the system:
- xk+2 = a xk+1 + b xk
- xk+1 = 1 xk+1 + 0 xk
This immediately translates to the matrix form where C = [[a, b], [1, 0]]. To find the state at index n, we apply C repeatedly to the initial state v0 = [x1, x0]T, which means vn = Cn v0.
Worked example: a = -1, b = 2
Let the recurrence be xk+2 = -xk+1 + 2xk with initial values x0 = 1 and x1 = 3. The companion matrix is C = [[-1, 2], [1, 0]].
We want to find x5 and the state at n=5. We can find the terms directly:
- x0 = 1, x1 = 3
- x2 = -1(3) + 2(1) = -1
- x3 = -1(-1) + 2(3) = 7
- x4 = -1(7) + 2(-1) = -9
- x5 = -1(-9) + 2(7) = 23
- x6 = -1(23) + 2(-9) = -41
| Index k | xk | State vk = [xk+1, xk]T |
|---|---|---|
| 0 | 1 | [3, 1]T |
| 1 | 3 | [-1, 3]T |
| 2 | -1 | [7, -1]T |
| 3 | 7 | [-9, 7]T |
| 4 | -9 | [23, -9]T |
| 5 | 23 | [-41, 23]T |
At n=5, the state is [x6, x5]T = [-41, 23]T. The companion matrix C5 is [[-21, 22], [11, -10]]. Multiplying C5 by the initial state [3, 1]T gives [-21(3) + 22(1), 11(3) - 10(1)]T = [-41, 23]T, exactly matching the direct calculation.
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.
Limitations
This module is restricted to second-order linear homogeneous recurrence relations with constant integer coefficients. It does not model higher-order recurrences, non-homogeneous terms (like adding a constant or function of n at each step), or continuous-time systems.
The interface bounds coefficients a and b to integers from -2 to 3 and seeds x0 and x1 from -3 to 3, and limits the index n to a maximum of 8. This ensures that all calculations remain exactly within the JavaScript safe integer range and can be perfectly represented without floating-point rounding errors. Negative powers of C are not permitted, avoiding fractional states or the need to invert singular companion matrices.
References
NumPy: Companion matrix and polynomial coefficient ordering. Note: Riano's declared state-order convention C=[[a,b],[1,0]] is independently derived for this module's specific recurrence orientation.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Companion Matrices and Recurrences module.
Try Companion Matrices and Recurrences on Riano →