Companion Matrix - Linear Recursive Sequences

Linear Recursive Sequences

Given a linear recursive sequence with characteristic polynomial

the (transpose) companion matrix

$C^T(p)=\begin{bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1\\ -c_0 & -c_1 & -c_2 & \cdots & -c_{n-1} \end{bmatrix}$

generates the sequence, in the sense that

$C^T\begin{bmatrix}a_k\\ a_{k+1}\\ \vdots \\ a_{k+n-1} \end{bmatrix} = \begin{bmatrix}a_{k+1}\\ a_{k+2}\\ \vdots \\ a_{k+n} \end{bmatrix}.$

It increments the series by 1.

For c₀ = −1, and all other c_i=0, i.e., p(t)=tn−1, this matrix reduces to Sylvester's cyclic clock shift matrix.

The vector (1,t,t2, ... ,tn-1) is an eigenvector of this matrix for eigenvalue t, when t is a root of the above characteristic polynomial.

Read more about this topic: Companion Matrix