## Condition that a Matrix is Similar to the Companion Matrix of its Characteristic Polynomial

## Problem 348

Let $A$ be an $n\times n$ complex matrix.

Let $p(x)=\det(xI-A)$ be the characteristic polynomial of $A$ and write it as

\[p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,\]
where $a_i$ are real numbers.

Let $C$ be the companion matrix of the polynomial $p(x)$ given by

\[C=\begin{bmatrix}

0 & 0 & \dots & 0 &-a_0 \\

1 & 0 & \dots & 0 & -a_1 \\

0 & 1 & \dots & 0 & -a_2 \\

\vdots & & \ddots & & \vdots \\

0 & 0 & \dots & 1 & -a_{n-1}

\end{bmatrix}=

[\mathbf{e}_2, \mathbf{e}_3, \dots, \mathbf{e}_n, -\mathbf{a}],\]
where $\mathbf{e}_i$ is the unit vector in $\C^n$ whose $i$-th entry is $1$ and zero elsewhere, and the vector $\mathbf{a}$ is defined by

\[\mathbf{a}=\begin{bmatrix}

a_0 \\

a_1 \\

\vdots \\

a_{n-1}

\end{bmatrix}.\]

Then prove that the following two statements are equivalent.

- There exists a vector $\mathbf{v}\in \C^n$ such that

\[\mathbf{v}, A\mathbf{v}, A^2\mathbf{v}, \dots, A^{n-1}\mathbf{v}\] form a basis of $\C^n$. - There exists an invertible matrix $S$ such that $S^{-1}AS=C$.

(Namely, $A$ is similar to the companion matrix of its characteristic polynomial.)