Given that $$A:=\begin{bmatrix}3 & 5 & -1 & 8\\ 1 & 2 & 4 & 9\\ 5 & -4 & 7 & 6\\2 & 4 & -3 & -1\end{bmatrix}, \;\;\;b = \pmatrix{1\\ 5 \\ -1 \\ -8},$$ I want to try and find some matrix $S$ such that $$C:=S^{-1}AS = \begin{bmatrix}0 & 1 & 0 &0\\0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ \star & \star & \star & \star\end{bmatrix}, \text{ such that } S^{-1}b = \pmatrix{0 \\ 0\\0\\1}.$$
At first glance, my thought was that $S^{-1}AS$ is the companion matrix of $A$. Hence, I made $$C = \begin{bmatrix}0 & 1 & 0 &0\\0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 714 & -108 & -11 & 11\end{bmatrix},$$ as the characteristic polynomial of $A$ is $p_A(\lambda) = \lambda^4 - 11\lambda^3 + 11\lambda^2 + 108\lambda - 714$.
I know that I could attempt to brute force the matrix $S$ by creating a system of equations through $AS = SC$, but I feel like this is more difficult of a method than I think necessary. It also doesn't account for the vector $S^{-1}b$.
My next thought was to do something along the lines of perhaps letting $S = [{\bf v}_1 \;\; {\bf v}_2 \;\; {\bf v}_3 \;\; {\bf v}_4]$, and taking ${\bf v}_4$ to be ${\bf v}_4 = b$, but I can't quite figure out how I could get any more vectors that are linearly independent to not only create an invertible matrix, but also form $C$ and satisfying $S^{-1}b = {\bf e}_4$. Can anyone provide a hint?
Try letting $c=b^T$, and let $Q = \begin{bmatrix} c \\ c A \\ c A^2 \\ c A^3 \end{bmatrix}$, and consider $Q A Q^{-1}$.
Any $c$ such that $(c,A)$ is observable will work, for example $c=e_1^T$ will work as well.