Editing Companion matrix (section)

==Linear recursive sequences==
A [[linear recursive sequence]] defined by <math>a_{k+n} = - c_0 a_k - c_1 a_{k+1} \cdots - c_{n-1} a_{k+n-1}</math> for <math>k \geq 0</math> has the characteristic polynomial <math>p(x)=c_0 + c_1 x + \cdots + c_{n-1}x^{n-1} + x^n  </math>, whose transpose companion matrix <math> C(p)^T </math> generates the sequence:
<math display="block">\begin{bmatrix}a_{k+1}\\
a_{k+2}\\
\vdots \\
a_{k+n-1}\\
a_{k+n}
\end{bmatrix}
=
\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}
\begin{bmatrix}a_k\\
a_{k+1}\\
\vdots \\
a_{k+n-2}\\
a_{k+n-1}
\end{bmatrix}
.</math>
The vector <math>v=(1,\lambda,\lambda^2,\ldots,\lambda^{n-1})</math> is an eigenvector of this matrix, where the eigenvalue <math>\lambda</math> is a root of <math>p(x)</math>. Setting the initial values of the sequence equal to this vector produces a geometric sequence <math>a_k = \lambda^k</math> which satisfies the recurrence. In the case of ''n'' distinct eigenvalues, an arbitrary solution <math>a_k </math> can be written as a linear combination of such geometric solutions, and the eigenvalues of largest complex norm give an [[asymptotic approximation]].