[proofplan] We first prove reachability and compute the characteristic polynomial for the companion pair by reading the action of $A_c$ on the standard basis. For the general reachable pair, we compare the recursively defined vectors $t_j$ with the usual reachability list $B,AB,\dots,A^{n-1}B$ and show that the change of generators is triangular with diagonal entries $1$. This proves that $T$ is a basis matrix. Finally, the recursion gives all columns of $AT$ except the first, and the first column follows from the Cayley-Hamilton identity applied to $B$. [/proofplan] [step:Show that the companion pair is reachable] Let $e_1,\ldots,e_n\in\mathbb{R}^n$ denote the standard basis. Let $a_0,a_1,\ldots,a_{n-1}\in\mathbb{R}$ be the coefficients of $p$, so $p(s)=s^n+\sum_{r=0}^{n-1}a_rs^r$. Let $A_c\in\mathbb{R}^{n\times n}$ be the companion matrix with $(A_c)_{i,i+1}=1$ for $1\le i<n$, $(A_c)_{n,j}=-a_{j-1}$ for $1\le j\le n$, and all other entries zero, and let $B_c:=e_n\in\mathbb{R}^n$. For $0\le k\le n-1$, define $v_k:=A_c^kB_c\in\mathbb{R}^n$. Since $B_c=e_n$, we have $v_0=e_n$. The defining entries of $A_c$ give, for $2\le j\le n$, \begin{align*} A_ce_j=e_{j-1}-a_{j-1}e_n. \end{align*} By induction on $k$, it follows that for each $0\le k\le n-1$, the vector $v_k$ belongs to the affine subspace $e_{n-k}+\operatorname{span}\{e_{n-k+1},\dots,e_n\}$. Thus, relative to the ordered basis $e_n,e_{n-1},\dots,e_1$, the reachability matrix with columns $B_c,A_cB_c,\dots,A_c^{n-1}B_c$ is triangular with all diagonal entries equal to $1$. Its determinant is therefore $1$, so it is invertible. Hence $(A_c,B_c)$ is reachable. [/step] [step:Compute the characteristic polynomial of the companion matrix] Let \begin{align*} q_n(s):=\det(sI_n-A_c) \end{align*} denote the characteristic polynomial of $A_c$. We prove by induction on $n$ that \begin{align*} q_n(s)=s^n+\sum_{r=0}^{n-1}a_rs^r. \end{align*} For $n=1$, the matrix $A_c$ has single entry $-a_0$, hence \begin{align*} q_1(s)=s+a_0. \end{align*} Assume the formula holds in dimension $n-1$. Expanding $\det(sI_n-A_c)$ along the first column gives two nonzero contributions: the entry $s$ in position $(1,1)$ and the entry $a_0$ in position $(n,1)$. The minor obtained from the entry $s$ is the companion determinant for the coefficient list indexed by $1\le r\le n-1$, so by the induction hypothesis it equals \begin{align*} s^{n-1}+\sum_{r=1}^{n-1}a_rs^{r-1}. \end{align*} The minor obtained from the entry $a_0$ is upper triangular with all diagonal entries equal to $-1$, so its determinant is $(-1)^{n-1}$. Including the cofactor sign $(-1)^{n+1}$, this contribution is $a_0$. Therefore \begin{align*} q_n(s)=s\left(s^{n-1}+\sum_{r=1}^{n-1}a_rs^{r-1}\right)+a_0=s^n+\sum_{r=0}^{n-1}a_rs^r. \end{align*} Hence $q_n(s)=p(s)$. [/step] [step:Show that the recursively defined vectors form a basis] For $1\le j\le n$, define \begin{align*} u_j:=A^{n-j}B. \end{align*} Since $(A,B)$ is reachable, the vectors $u_1,\dots,u_n$ form a basis of $\mathbb{R}^n$: they are the usual reachability list $A^{n-1}B,\dots,AB,B$ written in reverse order. We claim that, for each $1\le j\le n$, \begin{align*} t_j=u_j+\operatorname{span}\{u_{j+1},\dots,u_n\}. \end{align*} For $j=n$, this is $t_n=B=u_n$. If the assertion holds for $j+1$, then \begin{align*} t_j=At_{j+1}+a_jB. \end{align*} The leading term $A u_{j+1}$ equals $u_j$, while applying $A$ to the remaining terms produces only vectors among $u_{j+1},\dots,u_{n-1}$, and $a_jB=a_ju_n$. Thus the assertion holds for $j$. Consequently, the change-of-basis matrix from $u_1,\dots,u_n$ to $t_1,\dots,t_n$ is triangular with all diagonal entries equal to $1$. It is invertible, so $t_1,\dots,t_n$ is a basis of $\mathbb{R}^n$. Hence $T$ is invertible. [guided] The goal of this step is to prove that the columns of $T$ really form a basis. Here $A\in\mathbb{R}^{n\times n}$ and $B\in\mathbb{R}^n$. Reachability means that the $n$ vectors $A^kB$ for $0\le k\le n-1$ span $\mathbb{R}^n$. We compare the new vectors $t_j$ to that known basis. Define, for $1\le j\le n$, \begin{align*} u_j:=A^{n-j}B. \end{align*} Thus $u_1=A^{n-1}B$, $u_2=A^{n-2}B$, and $u_n=B$. The list $u_1,\dots,u_n$ is just the usual reachability list in reverse order. Since $(A,B)$ is reachable, these $n$ vectors form a basis of $\mathbb{R}^n$. We now compare $t_j$ to $u_j$. The claim is that each $t_j$ has leading term $u_j$ and only lower-order correction terms: \begin{align*} t_j=u_j+\operatorname{span}\{u_{j+1},\dots,u_n\}. \end{align*} For $j=n$, this is exactly $t_n=B=u_n$. Suppose it has been proved for $j+1$. Then $t_{j+1}$ is $u_{j+1}$ plus a linear combination of $u_{j+2},\dots,u_n$. Applying $A$ gives $Au_{j+1}=u_j$. Also, for $j+2\le k\le n$, the vector $Au_k$ is either $u_{k-1}$ or, when $k=n$, the vector $AB=u_{n-1}$; in all cases these correction terms remain in the span of $u_{j+1},\dots,u_{n-1}$. The recursion adds $a_jB=a_ju_n$, which is also in the correction span. Therefore \begin{align*} t_j=u_j+\operatorname{span}\{u_{j+1},\dots,u_n\}. \end{align*} This means that the coordinate matrix expressing the ordered list $t_1,\dots,t_n$ in the basis $u_1,\dots,u_n$ is triangular with diagonal entries $1$. Such a triangular matrix has determinant $1$, so it is invertible. Therefore $t_1,\dots,t_n$ is also a basis of $\mathbb{R}^n$, and the matrix $T$ with these columns is invertible. [/guided] [/step] [step:Identify the columns of $AT$ in the reachable basis] For $1\le j<n$, the recursion gives \begin{align*} At_{j+1}=t_j-a_jB. \end{align*} Since $B=t_n$, this becomes \begin{align*} At_{j+1}=t_j-a_jt_n. \end{align*} It remains to compute $At_1$. From the recursive formula, expanding $t_1$ gives \begin{align*} t_1=A^{n-1}B+\sum_{r=1}^{n-1}a_rA^{r-1}B. \end{align*} Therefore \begin{align*} At_1=A^nB+\sum_{r=1}^{n-1}a_rA^rB. \end{align*} By the [Cayley-Hamilton Theorem](/theorems/407), since $A\in\mathbb{R}^{n\times n}$ is a square matrix and $p$ is its characteristic polynomial, we have \begin{align*} p(A)=A^n+\sum_{r=0}^{n-1}a_rA^r=0. \end{align*} Applying this identity to $B$ gives \begin{align*} A^nB+\sum_{r=1}^{n-1}a_rA^rB=-a_0B. \end{align*} Hence \begin{align*} At_1=-a_0t_n. \end{align*} [/step] [step:Read off the canonical matrices] Because the columns of $T$ are $t_1,\dots,t_n$, the matrix $T^{-1}AT$ is the matrix of the [linear map](/page/Linear%20Map) $x\mapsto Ax$ in the basis $t_1,\dots,t_n$. The identities just proved say that its first column is $-a_0e_n$, and for $1\le j<n$ its $(j+1)$-st column is \begin{align*} e_j-a_je_n. \end{align*} These are exactly the columns of $A_c$, so \begin{align*} T^{-1}AT=A_c. \end{align*} Finally, since $B=t_n$, the coordinate vector of $B$ in the basis $t_1,\dots,t_n$ is $e_n=B_c$. Thus \begin{align*} T^{-1}B=B_c. \end{align*} This proves the reachability canonical form. [/step]