showing any controllable system can be put in 'controller' form. I am looking at the proof of the following theorem: Let $\dot{x} =Ax + Bu$ be a controllable single input system, where $\Delta_A:= \det(\lambda I -A) = \lambda^n + a_1\lambda^{n-1} + \ldots + a_{n-1}\lambda + a_n$. Show this system is isomorphic to the system $\dot{x} = \bar{A}x + \bar{B}u$ where:
$$\bar{A} = \left(      \begin{matrix} 0 & 1 & 0& \dots & 0 & 0\\
0 &0&1 &\ldots &0&0 & \\
\vdots &\vdots &\vdots & & \vdots &\vdots &\\
0&0&0& \ldots & 0& 1\\
-a_n& -a_{n-1}& -a_{n-2}& \ldots & -a_2& -a_1
\end{matrix}\right) ,\quad\bar{b}=\left(  \begin{matrix} 0\\0\\ \vdots \\0\\0\\1 \end{matrix}\right)$$
This amounts to finding an invertible matrix $S$ such that $\bar{A}=S^{-1}AS$ and $\bar{B} = S^{-1}B$.
The proof however I really cannot follow. This theorem comes from a subject that I am taking for the second time. I distinctly remember begin quite impressed with this theorem last year when the teacher proved it with relative ease. However in the updated lecture notes we are given this year I cannot follow the proof at all. 
It starts of with defining the required matrix $S$ via $S = \left(q_1\quad q_2 \quad \ldots \quad q_n\right)$ where
\begin{eqnarray}
q_n&=&B\\
q_{n-1} &=& AB + a_{1}B\\
q_{n-1} &=& A^2B + a_{1}AB +a_{2}B\\
&\vdots&\\
q_1 &=& A^{n-1}B +a_{1}A^{n-2}B + \ldots +a_{n-1}B
\end{eqnarray}
Can anyone show me why this choice of $S$ works? Thanks a lot in advance for any help!
 A: We need to show that $S \bar{A} = AS$. First look at $S \bar{A}$ (work it out).
$S \bar{A} = \begin{pmatrix} -a_n q_n & -a_{n-1} q_n + q_1 & -a_{n-2} q_n + q_2 & \dots & -a_1 q_n + q_{n-1} \end{pmatrix}$
Now $AS = \begin{pmatrix} A q_1 & A q_2 & \dots & A q_n \end{pmatrix}$. Let us look at each column seperately.
$A q_1 = A^n B + a_1 A^{n-1} B + \dots + a_{n-1} A B = -a_n B = -a_n q_n$.
It follows from the Cayley-Hamilton theorem, because $\Delta_A$ is the characteristic polynomial of $A$. Others will just follow from the definitions
$\begin{align}
A q_2 &= A^{n-1} B + a_1 A^{n-2} B + \dots + a_{n-2} A B = -a_{n-1} B + q_1 = -a_{n-1} q_n + q_1 \\
A q_3 &= A^{n-2} B + a_1 A^{n-3} B + \dots + a_{n-3} A B = -a_{n-2} B + q_2 = -a_{n-2} q_n + q_2 \\
&\vdots \\
A q_{n-1} &= A^2 B + a_1 AB = -a_2 B + q_{n-2} = -a_2 q_n + q_{n-2} \\
A q_n &= AB = -a_1 B + q_{n-1} = -a_1 q_n + q_{n-1} \\
\end{align}$
Hence, $S \bar{A} = AS$. Also, see that $S \bar{B} = q_n = B$.
Edit: Also note that $q_i$ are linearly dependant (ie. $S$ does not have an inverse) if the system is not controllable.
A: Here is another view (inspired by Luenberger's 1967 paper http://www.stanford.edu/dept/MSandE/cgi-bin/people/faculty/luenberger/pdfs/cfflms.pdf, this is a slightly different solution for a slightly simpler problem):
(Note that even Luenberger wrote that this "is somewhat more difficult to derive".)
Let $P = \begin{bmatrix} b & Ab & \cdots & A^{n-1} b \end{bmatrix}$. Since the system is cc., $P$ is invertible.
It is straightforward to show that using the basis $P$, the system $(A,b)$ has the form
$\left( \begin{bmatrix}
0 & 0 & 0& \dots & 0 & -a_n\\
1 &0&0 &\ldots &0& -a_{n-1} & \\
\vdots &\vdots &\vdots & & \vdots &\vdots &\\
0&0&0& \ldots & 0& -a_2 \\
0& 0& 0& 0 & 1& -a_1
\end{bmatrix}, e_1 \right)$,
where $e_k$ is all zeros except for a one in the $k$th position.
This is close, but we need the transpose instead, and the '$b$' matrix needs to be $e_n$ instead.
The key claim is that the system $(A^T, P^{-T} e_n)$ is cc. Let
$W^T = \begin{bmatrix} e_n^T P^{-1} \\ \vdots \\ e_n^T P^{-1} A^{n-1} \end{bmatrix}$ (the transpose of the usual). We need to show that $W$ is invertible. Note that $e_n^T P^{-1} A^{i-1}A^{j-1}b  = e_n^T P^{-1} P e_{i+j-1} = \delta_{n,i+j-1}$ for $i,j$ such that $2 \le i+j \le n$. Hence $W^TP =\begin{bmatrix}
0 & 0 & 0& \dots & 0 & 1 \\
0 &0&0 &\ldots &1& * & \\
\vdots &\vdots &\vdots & & \vdots &\vdots &\\
0&1& * & \ldots & * & * \\
1& *& *& \ldots & *& *
\end{bmatrix}$, where the $*$ entries do not matter in the context of showing that $W$ is invertible. Since $P$ and the right hand side are invertible, it follows that $W^T$ is invertible and hence $(A^T, P^{-T} e_n)$ is cc. Note that this computation also shows that $W^T P e_1 = e_n$.
Now we note that in the basis $W$, the matrix $W^{-1}A^TW$ has the form given above, hence the matrix $W^T A W^{-T}$ has the desired form. Furthermore, $W^Tb = W^T P e_1 = e_n$, as desired.
A: The two representations $(A, \mathbf{b})$ and $(\bar{A}, \bar{\mathbf{b}})$ are isomorphic iff there is a bijection $\Phi:\mathbb{R^n} \rightarrow \mathbb{R^n}$ from the original states $\mathbf{x}(t)$ to the states $\mathbf{z}(t)$ in normal form: $\Phi(\mathbf{x}(t)) = W\mathbf{x}(t) = \mathbf{z}(t)$ where $W \in \mathbb{R}^{n \times n}$.
The linear transformation yields the following set of equations (argument $t$ omitted for sake of readability):
$$
\begin{align}
\mathbf{w}_1^T\mathbf{x} = z_1 \\
\mathbf{w}_1^T\dot{\mathbf{x}} = \mathbf{w}_1^T (A\mathbf{x} + \mathbf{b}u) = \mathbf{w}_1^TA\mathbf{x} + \underbrace{\mathbf{w}_1^T\mathbf{b}}_{=0}u
= \dot{z}_1 = z_2 \\
\mathbf{w}_1^TA\dot{\mathbf{x}} = \mathbf{w}_1^TA (A\mathbf{x} + \mathbf{b}u)
= \mathbf{w}_1^TA^2\mathbf{x} 
+ \overbrace{\underbrace{\mathbf{w}_1^TA}_{\mathbf{w}_2^T}\mathbf{b}}^{=0}u
= \dot{z}_2 = z_3 \\
\vdots \\
\mathbf{w}_1^TA^{n-1}\mathbf{x} = z_n.
\end{align}
$$
Matrixwise this reads
$$
\underbrace{
\left[
\begin{array}{c}
\mathbf{w}_1^T \\
\mathbf{w}_1^TA \\
\mathbf{w}_1^TA^2 \\
\vdots \\
\mathbf{w}_1^TA^{n-1}
\end{array}
\right]}_{=W}\mathbf{x} = \mathbf{z}.
$$
Where the conditional equation for $\mathbf{w}_1^T$ is
$$ 
\left[
\mathbf{w}_1^T\mathbf{b}, 
\mathbf{w}_2^T\mathbf{b},
...,
\mathbf{w}_n^T\mathbf{b}
\right] = 
\left[
\mathbf{w}_1^T\mathbf{b}, 
\mathbf{w}_1^TA\mathbf{b},
...,
\mathbf{w}_1^TA^{n-1}\mathbf{b}
\right],
$$
which, from $\bar{\mathbf{b}} = [0 ... 0 \: 1]^T$, returns 
$$ [0 ... 0 \: 1] = \mathbf{w}_1^T \underbrace{[\mathbf{b} \: A\mathbf{b} \: ... \: A^{n-1}\mathbf{b}]}_{=:S(A, \mathbf{b})}. $$
If $S(A, \mathbf{b})$ is invertible
$$\mathbf{w}_1^T = [0 ... 0 \: 1] \: S^{-1}(A, \mathbf{b}), $$
which is a unique solution and a necessary condition for $W$ to be invertible and $\Phi$ to be 1-1 and onto.
