Explicit formula of exponential of companion matrix

Question

Let $$A=\begin{bmatrix} a_k & a_{k-1} & a_{k-2} & \cdots & a_2 & a_1 \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots &\\0 & 0 & 0 & \cdots & 1 & 0\end{bmatrix}$$ be a $k \times k$ matrix of {$a_k$} on a commutative ring. Find the explicit expression of the last row of $A^n$ in terms of {$a_k$}, where $k\le n$.

Answer 1

Rather a lengthy comment but I want to point out this MO question and these two articles pointed out there

• The combinatorial power of the companion matrix
• SUMS OF FIBONACCI NUMBERS BY MATRIX METHODS

I hope they will be useful.

Answer 2

In theory, it's easy. Let $n$ be an explicit integer. You divide $x^n$ by $p(x)=x^k-a_kx^{k-1}-\cdots$ and you keep the remainder which is in the form $r=u_1x^{k-1}+u_2x^{k-2}+\cdots$. We can do that because the polynomials are unitary. The required row is $[u_1,u_2,\cdots]$.

Practically, the calculation is quasi unfeasible if you keep the parameters $(a_i)$ as they are. On the contrary, it works very well if you give explicit values to the $(a_i)$ and if you use a computer (of course you have to program the $2$ operations of the ring).