At first, I want to explain why did I say the $n$th power of a matrix by *companion matrix*. Suppose that $A$ is a matrix
of order $d$ over an ordinary field. There are several methods to obtain a closed-form expression for the $n$th power of the matrix $A$.

**First method:**If $A$ is diagonalizable, we can obtain the $n$th power of matrix $A$ via its eigenvalues, as in this example. A problem with this method is that square matrices $A$ need not be diagonalizable.**Second method:**If $A$ is not diagonalizable, we obtain the $n$th power via its characteristic polynomial, as in this example. A problem with this method is that if the eigenvalues of matrix $A$ are not real, then solving the system of equations is too difficult.**Third method:**Suppose that the characteristic polynomial of the**non-derogatory**matrix $A$ is $$ P(X)=X^d-u_{d-1}\,X^{d-1}-u_{d-2}\, X^{d-2}-\cdots-u_1\, X-u_0\, . $$

The companion matrix with the characteristic polynomial $P(X)$, is in the following form

\begin{equation} C=\left( \begin{array}{cccccc} 0 &1 &0 &\cdots &\cdots &0 \\ 0 &0 &1 &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\ \vdots &\ddots &\ddots &\ddots &\ddots &0 \\ 0 &\cdots &\cdots &0 &0 &1 \\ u_{0} &u_{1} &\cdots &\cdots &u_{d-2} &u_{d-1} \\ \end{array} \right)_{d \times d}\, . \end{equation}

Because the non-derogatory matrix $A$ and the companion matrix $C$ of the characteristic polynomial of $A$ have the same *Jordan canonical form*
(one block $J_{ri} (\lambda_i)$ corresponding to each distinct eigenvalue $\lambda_i$), it follows that $A$ is similar to $C$. For more
details, see page 195 of the book Matrix Analysis. In fact, there is an invertible matrix $Q$ of order $d$, such that

$$ A=Q^{-1}\, C\, Q\, \Longrightarrow \, A^n=Q^{-1}\, C^n\, Q\, . $$

The $n$th power of the companion matrix can be obtained via the methods of *generalized Fibonacci sequence* or by *Combinatorial method*.
By using the fact that matrices $A$ and $C$ have the same Jordan canonical form, we conclude that

$$ \begin{array}{ccc} V_A\,J\,V_A^{-1}=A &&\\ &\Longrightarrow &V_A^{-1}\,A\,V_A=V_C^{-1}\,C\,V_C \\ V_C\,J\,V_C^{-1}=C && \end{array} $$

Thus

$$ Q=V_C\, V_A^{-1}\, \Longrightarrow \, A^n={(V_C\, V_A^{-1})}^{-1}\, C^n \, {(V_C\, V_A^{-1})} $$

If the size of $A$ is at least $10$), then *Maple* requires a long time to calculate its Jordan normal form.

*In summary:*
Let $A\in M_d$ be a non-derogatory matrix (in other words, its minimal and characteristic polynomials coincide). Denote by $P(X)$, the characteristic polynomial of $A$.

It is proved here that $A$ is similar to the companion matrix of $P(X)$:

$$ A=Q^{-1}\, C\, Q , $$ where $Q$ is an invertible matrix of size $d$. Now my question is:

Is there an

efficient algorithmfor calculating $Q$?

**Edit:**

When $A$ is a non-derogatory matrix, there are two method to find matrix $Q$. First method is based on *Jordan canonical form*. This method is complicated when the eigenvalues of matrix $A$ are not real. Second method is depend on Frobenius normal form.

The answer of this post by *user44191* is in fact the Frobenius normal form of matrix $A$. With the other words, If minimal and characteristic polynomials of matrix $A$ be the same, there is a vector $\vec{v} \in \mathbb{R}^n$ such that $\{A^i \vec{v}\}_{i = 0}^{n - 1}$ is linearly independent. The following theorem ensure that there are such cyclic vectors.

*Theorem:* Let $T$ be a linear operator on vector space $V$ of $n$ dimensional. There exists a cyclic vector for T if and only if minimal polynomial and characteristic polynomial are same.(*section 7.1 in Linear algebra by Hoffman-Kunze*)

**Second question:** Is there a method for obtaining the cyclic vectors when we have a matrix that it's minimal and characteristic polynomials coincide or should choose a random vector and test it, is cyclic or not? This is an example for my question.

I asked the second question in math.stack and on of Dear user suggested me to find solution in the section $5$ of this paper. I read this paper but method of this paper is not clear for me. Just because of this I edited my question and ask the second question.

I would greatly appreciate for any suggestions for my second question.