= Solution
For the standard basis vector $e_j$, matrix multiplication selects the $j$th column, so
$$
Me_j=c_j.
$$
Consequently
$$
(PM)e_j=P(Me_j)=Pc_j,
$$
and the columns of $PM$ are $Pc_1,\ldots,Pc_n$.
Suppose first that $v,Av,\ldots,A^{n-1}v$ are linearly independent, and define
$$
S=\begin{pmatrix}v&Av&\cdots&A^{n-1}v\end{pmatrix}.
$$
Then $S$ is invertible. The first $n-1$ columns of $AS$ are the last $n-1$ columns of $S$. By the <Cayley-Hamilton theorem>,
$$
A^nv=-a_0v-a_1Av-\cdots-a_{n-1}A^{n-1}v.
$$
This is exactly the last-column rule for the <companion matrix> $C$, so
$$
AS=SC,\qquad S^{-1}AS=C.
$$
Conversely, suppose $S^{-1}AS=C$, or $AS=SC$, and write the columns of $S$ as $s_1,\ldots,s_n$. Comparing the first $n-1$ columns gives
$$
As_j=s_{j+1}\qquad(1\leq j<n).
$$
Hence
$$
s_j=A^{j-1}s_1.
$$
Since $S$ is invertible, its columns are linearly independent. Taking $v=s_1$ therefore makes
$$
v,Av,\ldots,A^{n-1}v
$$
linearly independent. Thus $A$ is similar to $C$ exactly when it has the stated <cyclic vector>.
Back to article page
