0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ As a note, it isn't always true that $A$ is similar to the companion matrix of its characteristic polynomial. Take, for example, the 0 matrix in dimension 2, which is only similar to itself; the corresponding companion matrix is nonzero. $\endgroup$ – user44191 Dec 7 '16 at 22:15
  • $\begingroup$ @user44191 In page 195 of Matrix Analysis is written " In particular, every companion matrix is non derogatory. A non derogatory matrix $A\in Mn$ need not be a companion matrix, of course, but $A$ and the companion matrix $C$ of the characteristic polynomial of $A$ have the same Jordan canonical form, so $A$ is similar to $C$." In fact , if the minimal polynomial equals with the characteristic polynomial of $A$ or in other words, $A$ be non derogatory, then $A$ is similar to the companion matrix of $p(x)$, where $p(x)$ is the characteristic polynomial of $A$. $\endgroup$ – Amin235 Dec 7 '16 at 22:27
  • $\begingroup$ @user44191 [continued] In your example, the minimal polynomial is not equal to characteristic polynomial. Thanks for your note. $\endgroup$ – Amin235 Dec 7 '16 at 22:29
  • $\begingroup$ @user44191 I edited question and add your note. Thanks again. $\endgroup$ – Amin235 Dec 7 '16 at 22:34
  • $\begingroup$ @David Handelman Thank you very much for your excllent revision of my Question. $\endgroup$ – Amin235 Dec 10 '16 at 8:44
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I appreciate for your amazing answer. I would be grateful if you explain me, is there a way for choosing the cyclic vector $v$, or should choose a random vector and after that test it's cyclic, by determinant of matrix $P$? $\endgroup$ – Amin235 Dec 8 '16 at 13:14
  • $\begingroup$ How do you get that $O(n^4)$? You are performing $n$ matrix-vector multiplications, so the cost should be $O(n^3)$. $\endgroup$ – Federico Poloni Dec 8 '16 at 22:07
  • $\begingroup$ Federico - you are correct; I was thinking of calculating $A^n$, then multiplying to get $A^n \vec{v}$, but what you say should be faster. $\endgroup$ – user44191 Dec 9 '16 at 0:27
  • $\begingroup$ Yes, it's definitely faster to compute them iteratively as $w_0 = v$, $w_{k+1}=Aw_k$ for all $k\geq 0$ (at least in the usual setting for computational costs). The whole computation requires as many floating point operations as a single matrix-matrix product. $\endgroup$ – Federico Poloni Dec 9 '16 at 9:14
  • $\begingroup$ @FedericoPoloni It is possible to introduce a method for obtaining a vector $v$ such that $\{A^i \vec{v}\}_{i = 0}^{n - 1}$ be linearly independent when minimal and characteristic polynomials of matrix $A$ is coincide. $\endgroup$ – Amin235 Dec 11 '16 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.