The $n$th power of a matrix by Companion matrix

Question

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 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. 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.

Answer 1

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? . 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.