Similarity to companion matrix, uniqueness Let $A \in \mathcal{M}_{n\times n}(\mathbf{R})$ and $b \in \mathbf{R}^n$ with $n\geqslant2$ be given.
Now should $(A,b)$ satisfy the Kalman rank condition
\begin{equation}
\text{rank}[b \,\, Ab \,\, \ldots \,\, A^{n-1}b] = n,
\end{equation}
or equivalently
\begin{equation}
\text{span}\{b, Ab, \ldots, A^{n-1}b\} = \mathbf{R}^n,
\end{equation}
then it is known that there exists $P \in \mathrm{GL}_n(\mathbf{R})$ such that
\begin{equation}
A = P\mathbf{A}P^{-1} \quad \text{ and } \quad b = Pe_n,
\end{equation}
where $e_n = [0, \ldots, 1]^T$ denotes the vector of the canonical basis of $\mathbf{R}^n$, whereas $\mathbf{A}$ is the companion matrix of $A$ (as defined in https://en.wikipedia.org/wiki/Companion_matrix):
\begin{equation}
\mathbf{A} = \begin{bmatrix}
0 & 1 & 0 &\ldots & 0\\
0 & 0 & 1 &\ldots & 0 \\
\vdots & & & \ddots &0\\
-a_n &\ldots &\ldots & \ldots & -a_1
\end{bmatrix},
\end{equation}
where $a_1, \ldots, a_n$ are the coefficients of the characteristic polynomial of $A$:
\begin{equation}
\chi_A(x) = x^n + a_1 x^{n-1} + \ldots + a_{n-1} x + a_n.
\end{equation}
My question is:

Is the matrix $P$ unique?

 A: Yes, this $P$ is unique. We can see that this holds as follows. First, suppose that $P = P_1$ and $P=P_2$ satisfy the required conditions; our goal is to show that $P_1 = P_2$. We note that
$$
A = P_1 \mathbf A P_1^{-1} = P_2 \mathbf A P_2^{-1} \implies \mathbf A = (P_1^{-1}P_2) \mathbf A (P_1^{-1}P_2)^{-1}\\
b = P_1e_n = P_2 e_n \implies P_1^{-1}P_2 e_n = e_n.
$$
Let $Q = P_1P_2^{-1}$; we want to use the above to show that $Q = I$ (the identity matrix) and thereby conclude that $P_1 = P_2$. Note the following:

Claim 1: If $\mathbf A$ is a companion matrix and $Q$ is any matrix such that $Q\mathbf A = \mathbf A Q$, then there exists a polynomial $f(x)$ such that $Q = f(\mathbf A)$.

This claim is proved, for instance, in Matrix Analysis by Horn and Johnson. We note that $$
\mathbf A = Q \mathbf A Q^{-1} \implies \mathbf A Q = Q \mathbf A.
$$
By Claim 1, there exists a polynomial $f$ for which $Q = f(\mathbf A)$. Moreover, we have
$$
Qe_n = e_n \implies (Q - I)e_n = 0 \implies (f(\mathbf A) - I)e_n = 0.
$$

Claim 2: $(\mathbf A, e_n)$ satisfies the Kalman rank condition.

By the Cayley-Hamilton theorem, we can write $f(\mathbf A) - I$ as $g(\mathbf A)$ for some polynomial $g$ with degree at most $n-1$. Let $g(x) = c_0 + c_1 x + \cdots + c_{n-1}x^{n-1}$. We note that
$$
g(\mathbf A) e_n = 0 \implies c_0 e_1 + c_1 \mathbf A e_n + \cdots + c_{n-1} \mathbf A^{n-1}e_n = 0 \implies\\
\pmatrix{e_n & \mathbf A e_n & \cdots & \mathbf A^{n-1} e_n} \pmatrix{c_0\\ c_1 \\ \vdots \\ c_{n-1}} = 0.
$$
By Claim 2, $\pmatrix{e_n & \mathbf A e_n & \cdots & \mathbf A^{n-1}e_n}$ has full rank. Thus, we can conclude from the above that $c_0 = c_1 = \cdots = c_{n-1} = 0$. That is, we have
$$
g(\mathbf A) = f(\mathbf A) - I = 0.
$$
That is, $Q = f(\mathbf A) = I$, which is what we wanted to show.
