I posted this question on math stackexchange weeks ago, and it have not receive an answer yet after a bounty offer...




---


I've been recently playing around with the linear recurrence sequences. Consider the following recurrence equation:


$$ a\_n = c\_1a\_{n-1} + \cdots + c\_ka\_{n-k}, \quad \forall n > k $$


is equivalent to


$$\begin{pmatrix}a\_n \\ \vdots \\ a\_{n-k+1}\end{pmatrix}
= \begin{pmatrix} c\_1& c\_2& \dots& c\_{k-1}& c\_k \\ 1& 0& \dots& 0& 0\\ 0& 1& \dots& 0& 0\\ \vdots& \vdots& \ddots& 0& 0\\ 0& 0& \dots& 1& 0\end{pmatrix}\begin{pmatrix} a\_{n-1} \\ \vdots \\ a\_{n-k} \end{pmatrix} = \dots = \begin{pmatrix} c\_1& c\_2& \dots& c\_{k-1}& c\_k \\ 1& 0& \dots& 0& 0\\ 0& 1& \dots& 0& 0\\ \vdots& \vdots& \ddots& 0& 0\\ 0& 0& \dots& 1& 0\end{pmatrix}^{n-k} \begin{pmatrix} a\_k \\ \vdots \\ a\_1 \end{pmatrix}, \quad \forall n > k $$


denote the R.H.S. matrix as $M$ (without the exponent).


And I want to show such $M$, regardless of the choice of $c\_1, \dots , c\_k$ (with $c\_k \neq 0$), has only one Jordan block corresponding to each eigenvalue in its Jordan canonical form, by an alternative way.


Let $U^-1MU = \Lambda + N$ be its Jordan form with $\Lambda N = N \Lambda$. Suppose $M$ consists of $m$ different eigenvalues $\lambda\_1,\dots, \lambda\_m$ with algebraic multiplicity $\alpha\_1,\dots,\alpha\_m$; i.e. the characteristic polynomial is
$$ c\_M(x) = (x-\lambda\_1)^{\alpha\_1}\dots(x-\lambda\_m)^{\alpha\_m} $$
and the minimal polynomial reads
$$ (x-\lambda\_1)^{u\_1}\dots(x-\lambda\_m)^{u\_m}$$
then
$$\begin{pmatrix}a\_n \\ \vdots \\ a\_{n-k+1}\end{pmatrix}
=
U^{-1}\begin{pmatrix}
\lambda\_1^n& {n \choose 1}\lambda\_1^{n-1}& \dots& {n \choose \*} \lambda\_1^{n-\*}& 0& \dots& 0& \\
0& \lambda\_1^n& \dots& {n \choose {\*-1}}\lambda\_1^{n-\*+1}& 0& \dots& 0\\
\vdots& \vdots& \ddots& \vdots& \vdots& \vdots& \vdots\\
0& 0& \dots& \lambda\_1^n& 0& \dots& 0\\
0& 0& \dots& 0&\lambda\_1^n& \dots& \vdots\\
0& 0& \dots& 0& 0& \ddots& \vdots\\
0& 0& \dots& 0& 0& \dots& \lambda\_m^n\\
\end{pmatrix}
U \begin{pmatrix} a\_k \\ \vdots \\ a\_1 \end{pmatrix}, \; \forall n > k
$$
the product of three matrice R.H.S. each has all entries as a function of $n$ in the shape of $P\_1(n)\lambda\_1^n + ... + P\_m(n)\lambda\_m^n$, with each $\deg P\_i \leq u\_i-1 $(note that $u\_i \leq \alpha\_i$). Note that this equation holds as long as the first recurrence equation holds.


One may prove the following result using the fact that $M$ has only one Jordan block for each eigenvalue to derive the following fact:



> 
> When $c\_1, \dots, c\_k$ and $a\_1. \dots, a\_k$ are chosen, there must uniquely exist $Q\_1, \dots, Q\_m$ with $\deg Q\_i \leq \alpha\_i-1$ such that the equation $a\_n = Q\_1(n)\lambda\_1^n + \dots + Q\_m(n)\lambda\_m^n$ always hold, and for all $\deg Q\_i \leq \alpha\_i-1$, the sequence given by $a\_n = Q\_1(n)\lambda\_1^n + \dots + Q\_m(n)\lambda\_m^n$ should also satisfy $a\_n = c\_1a\_{n-1} + \dots + c\_ka\_{n-k}$.
> 
> 
> 


But I want to take the statement above for granted(one can verify the result by checking if the $k$ by $k$ matrix representation of the relation between coefficient of $P\_i$s and $a\_i$s is singular. And also there are other ways I know to derive this result) and prove that $M$ must only have one Jordan block for each eigenvalue(i.e. $u\_i = a\_i$).


Proof
=====


For fixed $c\_1, \dots, c\_k$, if $u\_i < \alpha\_i$ for some $i$, pick $a\_n = n^{\alpha\_i}\lambda\_i^n$. By the statement above, the recurrence relation holds, and hence (by the Jordan Form analysis) there exists $Q\_1, \dots, Q\_m$ such that $a\_n = Q\_1(n)\lambda\_1^n + \dots + Q\_m(n)\lambda\_m^n\, \; \forall n > k$ with $\deg Q\_i < u\_i$, but such expression is unique, and it does not contain the term $n^{\alpha\_i}\lambda\_i^n$, leading to a contradiction; thus there must only be one Jordan block corresponding to each $\lambda$.


Is this proof valid? I've seen other shorter proofs of it, and I would like to see if there are common concepts between this proof and the other proofs.


Short proof:
<https://math.stackexchange.com/questions/348498/jordan-basis-of-a-when-a-is-the-companion-matrix?rq=1>


Alternate proofs:
<https://math.stackexchange.com/questions/10216/the-characteristic-and-minimal-polynomial-of-a-companion-matrix>



Companion matrices must have geometric multiplicity one, linear recurrence sequence view
If $M$ had more than one Jordan block corresponding to some eigenvalue, then its minimal polynomial's degree would be smaller than $k$. This yields that *all* sequences satisfying your recurrence relation in fact satisfy a fixed smaller order linear recurrence relation (given by that minimal polynomial). But that is absurd according to the dimension argument.


