Modular Equation Transformed as Matrix?

Question

I'm reading this paper by Marsaglia, in which he transforms the modular equation $$c_1 + c_2k + c_3 k^2 + ... + c_n k^{n-1} \equiv 0 \pmod{m}$$ into the matrix multiplication $$(c_1, c_2, ..., c_n) = (t_1, ..., t_n) \begin{pmatrix} m & 0 & 0 & 0 & ... & 0 & 0 \\ -k & 1 & 0 & 0 & ... & 0 & 0 \\ 0 & -k & 1 &0 & ... & 0 & 0 \\ \vdots \\ 0 & 0 & 0 & 0 & ... & -k & 1 \end{pmatrix}.$$ I have never seen this sort of transformation before and was wondering if someone could prove why this is the case. Expanding out the matrix multiplication hasn't lended any additional information either. Could someone please explain? Thank you.

Answer 1

Expanding out the matrix equation yields the equations $$ c_1 = m t_1 - kt_2\\ c_2 = t_2 - kt_3\\ \vdots\\ c_{n-1} = t_{n-1} - kt_n\\ c_n = t_n $$ Solving these for $t_n$ yields $$ t_n = c_n\\ t_{n-1} = kt_n + c_{n-1} = c_n k + c_{n-1}\\ t_{n-2} = kt_{n-1} + c_{n-2} = c_n k^2 + c_{n-1}k + c_{n-2}\\ \vdots \\ t_2 = kt_{3} + c_{2} = c_n k^{n-2} + c_{n-1}k^{n-3} + \cdots + c_{3}k + c_2\\ mt_1 = kt_2 + c_1 = c_n k^{n-1} + c_{n-1} k^{n-2} + \cdots + c_2 k + c_1. $$ So, his claim indeed holds: if there exists an integer solution $(t_1,\dots,t_n)$ to the linear system, then it must hold that $$ c_1 + c_2k + c_3 k^2 + ... + c_n k^{n-1} = t_1 m \equiv 0 \pmod{m}. $$ Since all these steps can be followed in reverse, we find that the system has an integer solution if and only if the modular equation has a solution.