At first, I want to explain why did I say the $n$th power of a matrix by [*companion matrix*](https://en.wikipedia.org/wiki/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](https://i.stack.imgur.com/Bj3Yr.jpg). 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](https://i.stack.imgur.com/6vr2E.jpg). 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*](https://en.wikipedia.org/wiki/Jordan_normal_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](http://rads.stackoverflow.com/amzn/click/0521548233). 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*](http://www.fq.math.ca/Scanned/22-3/er.pdf) or by [*Combinatorial method*](http://www.sciencedirect.com/science/article/pii/0024379595901639). 
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](http://rads.stackoverflow.com/amzn/click/0521548233) 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 algorithm* for 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*](https://en.wikipedia.org/wiki/Jordan_normal_form). This method is complicated when the eigenvalues of matrix $A$ are not real. Second method is depend on [Frobenius normal form](https://en.wikipedia.org/wiki/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](https://i.stack.imgur.com/KlHGY.jpg) is an example for my question.


I asked the second question in [math.stack](https://math.stackexchange.com/questions/2053818/finding-cyclic-vectors-for-a-special-matrix) and on of Dear user suggested me to find solution in the section $5$ of [this paper](http://www.lix.polytechnique.fr/~augot/LAA_96.pdf). 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. 



The $n$th power of a matrix by Companion matrix
Note: for the notation I'm used to, the 1s for $C$ are subdiagonal, as in Wikipedia, not superdiagonal, as in your question.


Under the assumption that $A$ is conjugate to a companion matrix:


If you are willing to accept a probabilistic answer, then there is a very efficient algorithm. Choose $\vec{v} \in \mathbb{R}^n$ randomly, under some reasonable random distribution (mainly: that it doesn't have its support only in a subvariety of $\mathbb{R}^n$). Then let $P$ be the array that consists of $\vec{v}, A\vec{v}, A^2 \vec{v}, ..., A^{n - 1} \vec{v}$. Let $Q = P^{-1}$. Then I claim that $A = Q^{-1} C Q$. 


The above claim is equivalent to the following claim: that *almost every* vector $\vec{v}$ is cyclic, that is, that $\{A^i \vec{v}\}\_{i = 0}^{n - 1}$ is linearly independent (formally: that the set of noncyclic vectors is a subvariety of codimension 1). 


Proof that $A = Q^{-1} C Q$: 


If $\{A^i \vec{v}\}\_{i = 0}^{n - 1}$ is linearly independent, then it is a basis of $\mathbb{R}^n$. Therefore, we only need to prove that $A (A^i \vec{v}) = Q^{-1} C Q A^i \vec{v}$ for $0 \leq i \leq n - 1$. But by the definition of $Q$, we have that $Q A^i \vec{v} = \vec{e}\_i$, the $i$th standard basis element. For $i \neq n - 1$, we have that $C \vec{e}\_i = \vec{e}\_{i + 1}$; for $i = n - 1$, w have $C \vec{e}\_{n - 1} = \sum\_{j = 0}^{n - 1} -u\_j \vec{e}\_j$.Then for $i \neq n - 1$, we have:


$Q^{-1} C Q A^i \vec{v} = Q^{-1} C \vec{e}\_i = Q^{-1} \vec{e}\_{i + 1} = A^{i + 1} \vec{v} = A A^i \vec{v}$


and for $i = n - 1$, we have


$Q^{-1} C Q A^{n - 1} \vec{v} = Q^{-1} C \vec{e}\_{n - 1} = Q^{-1} \sum\_{j = 0}^{n - 1} -u\_j \vec{e}\_j = \sum\_{j = 0}^{n - 1} -u\_j A^j \vec{v}$. But by the fact that $\chi\_A(x) = x^n + \sum\_{j = 0}^{n - 1} u\_j x^j$, and the fact that $\chi\_A(A) = 0$, we have that $\sum\_{j = 0}^{n - 1} -u\_j A^j = A^n$. Therefore, $Q^{-1} C Q A^{n - 1} \vec{v} = A^n \vec{v} = A A^{n - 1} \vec{v}$.


Therefore, we've shown that all the basis elements go where they should; therefore, we have that $A = Q^{-1} C Q$. 


Proof that almost every vector is cyclic: The assumption that $A$ is conjugate to a companion matrix is equivalent to the assumption that there is some cyclic vector, as the companion matrix has cyclic vector $\vec{e}\_1$. The set of non-cyclic vectors is determined by the equation $det(P\_\vec{v}) = 0$. As there is some cyclic vector, we have that $det(P\_\vec{v})$ is nonzero somewhere, so the set where it is 0 is not the entire space, and therefore is a subvariety of codimension 1.


**Corrected according to comment**: This determines such a $Q$ in $O(n^3)$ time as applying a matrix to a vector takes $O(n^2)$ and we do this $n$ times, then invert, which takes less than $O(n^3)$. This is as fast as the corresponding method for Jordan normal form according to [What is the best algorithm to find the smallest nonzero Eigenvalue of a symmetric matrix?](https://mathoverflow.net/questions/24287/what-is-the-best-algorithm-to-find-the-smallest-nonzero-eigenvalue-of-a-symmetric/24294#24294) . It has the advantage of working in any field without having to go through any field extensions - which you seemed to indicate was a problem when talking about complex numbers. 


