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
