Linear Recurrence → Matrix Form

Companion matrix shifts window of last k values one step.

Try this in Python

k = 2
# a_n = a_{n-1} + a_{n-2} companion
C = [[1, 1], [1, 0]]
print(C)

Key takeaways

• Initial vector must align with matrix definition—off-by-one common.
• Mod polynomial features for linear rec modulo prime advanced.
• Characteristic polynomial links eigenvalues (theory).