[proofplan] We use controllability to choose a basis in which the input vector is the last coordinate vector. In that basis, adding a feedback term changes only the last row of the system matrix. We then compute the characteristic polynomial of a matrix in this companion-row form and choose the feedback row so that its coefficients agree with the prescribed polynomial. Finally, we conjugate the feedback gain back to the original coordinates, using invariance of determinants under similarity. [/proofplan]

[step:Put the system into a controllability basis with input vector $e_n$] Let $I_n \in \mathbb{R}^{n \times n}$ denote the identity matrix. Define the controllability matrix \begin{align*} \mathcal{C}(A,B) := \begin{pmatrix} B & AB & \cdots & A^{n-2}B & A^{n-1}B \end{pmatrix} \in \mathbb{R}^{n \times n}. \end{align*} By controllability of $(A,B)$, the matrix $\mathcal{C}(A,B)$ is invertible. Define \begin{align*} T := \begin{pmatrix} A^{n-1}B & A^{n-2}B & \cdots & AB & B \end{pmatrix} \in \mathbb{R}^{n \times n}. \end{align*} This is obtained from $\mathcal{C}(A,B)$ by reversing the order of its columns. Since reversing columns is multiplication on the right by an invertible permutation matrix, $T$ is invertible. Define $\widetilde{A} \in \mathbb{R}^{n \times n}$ and $\widetilde{B} \in \mathbb{R}^{n \times 1}$ by \begin{align*} \widetilde{A} := T^{-1}AT. \end{align*} Also define \begin{align*} \widetilde{B} := T^{-1}B. \end{align*} Let $e_1,\dots,e_n \in \mathbb{R}^n$ denote the standard coordinate column vectors. Since the last column of $T$ is $B$, we have \begin{align*} \widetilde{B} = T^{-1}B = e_n. \end{align*} For $2 \le j \le n$, the $j$-th column of $T$ is $A^{n-j}B$, hence \begin{align*} A(A^{n-j}B) = A^{n-j+1}B, \end{align*} which is the $(j-1)$-st column of $T$. Therefore the $j$-th column of $\widetilde{A}$ is $e_{j-1}$ for every $2 \le j \le n$. The first column of $\widetilde{A}$ is some vector $c \in \mathbb{R}^n$, namely the coordinate vector of $A^nB$ in the basis given by the columns of $T$. Thus $\widetilde{A}$ is the matrix whose first column is $(c_1,\dots,c_n)^\top$, whose entries in positions $(j-1,j)$ are $1$ for $2 \le j \le n$, and whose remaining entries are $0$. Equivalently, $\widetilde{A}_{i1}=c_i$ for $1 \le i \le n$, $\widetilde{A}_{j-1,j}=1$ for $2 \le j \le n$, and all other entries vanish. The [real numbers](/page/Real%20Numbers) $c_1,\dots,c_n$ are uniquely determined by $A^nB=T(c_1,\dots,c_n)^\top$. [/step]

[step:Show that feedback changes only the last row in these coordinates]Let $\widetilde{K} \in \mathbb{R}^{1 \times n}$ be a row vector, written as \begin{align*} \widetilde{K} = \begin{pmatrix} k_1 & k_2 & \cdots & k_n \end{pmatrix}. \end{align*} Since $\widetilde{B}=e_n$, the rank-one matrix $\widetilde{B}\widetilde{K}$ has all rows equal to zero except the last row, which is $\widetilde{K}$. Hence $\widetilde{A}+\widetilde{B}\widetilde{K}$ is obtained from $\widetilde{A}$ by replacing the last row with $(c_n+k_1,k_2,\dots,k_n)$ and leaving the first $n-1$ rows unchanged.[/step]

[guided]The reason for choosing the reversed controllability basis is now visible. The input vector becomes $e_n$, so multiplication by a feedback row affects only the last row of the transformed state matrix. Let \begin{align*} \widetilde{K} = \begin{pmatrix} k_1 & k_2 & \cdots & k_n \end{pmatrix} \in \mathbb{R}^{1 \times n}. \end{align*} Because $\widetilde{B}=e_n$, the product $\widetilde{B}\widetilde{K}$ is the matrix whose $(i,j)$-entry equals $(e_n)_i k_j$. Thus this entry is $0$ when $i \ne n$, and it is $k_j$ when $i=n$. Therefore $\widetilde{B}\widetilde{K}$ has entries $(\widetilde{B}\widetilde{K})_{ij}=0$ for $i<n$ and $(\widetilde{B}\widetilde{K})_{nj}=k_j$ for $1 \le j \le n$. Adding this matrix to $\widetilde{A}$ leaves the first $n-1$ rows unchanged and replaces the last row by \begin{align*} \begin{pmatrix} c_n+k_1 & k_2 & \cdots & k_n \end{pmatrix}. \end{align*} Thus feedback in these coordinates gives direct control over every entry of the last row while preserving the companion-row structure of the remaining rows.[/guided]

[step:Compute the characteristic polynomial in companion-row form]For arbitrary real numbers $r_1,\dots,r_n$, define $M(r_1,\dots,r_n) \in \mathbb{R}^{n \times n}$ to be the matrix whose first column is $(c_1,\dots,c_{n-1},r_1)^\top$, whose entries in positions $(j-1,j)$ are $1$ for $2 \le j \le n$, whose last-row entries are $(r_1,\dots,r_n)$, and whose remaining entries are $0$. Define polynomials $P_1,\dots,P_n \in \mathbb{R}[s]$ recursively by $P_1(s):=1$ and \begin{align*} P_{j+1}(s):=sP_j(s)-c_j \end{align*} for $1 \le j \le n-1$. Then $P_j$ has degree $j-1$ and leading coefficient $1$ for each $1 \le j \le n$. We claim that \begin{align*} \det(sI_n-M(r_1,\dots,r_n))=(s-r_n)P_n(s)-\sum_{j=1}^{n-1} r_jP_j(s). \end{align*} If $n=1$, then $M(r_1)$ is the $1\times 1$ matrix with entry $r_1$, while $P_1(s)=1$ and the sum over $1 \le j \le 0$ is empty. Hence \begin{align*} \det(sI_1-M(r_1))=s-r_1=(s-r_1)P_1(s), \end{align*} so the identity holds in the one-dimensional case. Assume now that $n\geq 2$. To prove this determinant identity directly, define $N(s) := sI_n-M(r_1,\dots,r_n) \in \mathbb{R}[s]^{n \times n}$. For $1 \le j \le n-1$, let $N_j(s) \in \mathbb{R}[s]^{j \times j}$ be the submatrix consisting of the first $j$ rows and first $j$ columns of $sI_n-M(r_1,\dots,r_n)$, and define $D_j(s):=\det N_j(s)$. Then $D_1(s)=s-c_1=P_2(s)$. Expanding $D_j(s)$ along the last column for $2 \le j \le n-1$ gives \begin{align*} D_j(s)=sD_{j-1}(s)-c_j. \end{align*} Indeed, the last column of $N_j(s)$ has entries $-1$ in row $j-1$, $s$ in row $j$, and $0$ elsewhere; the cofactor of the $-1$ entry is $(-1)^{j-1+j}$ times the determinant of the triangular matrix with diagonal entries $1,\dots,1,c_j$, hence contributes $-c_j$. By induction, $D_j(s)=P_{j+1}(s)$ for $1 \le j \le n-1$. Now expand $\det N(s)$ along its last row. The entry in column $j<n$ is $-r_j$, and its cofactor is $P_j(s)$: deleting the last row and the $j$-th column leaves a block upper triangular matrix whose left block has determinant $P_j(s)$ and whose right block has determinant $1$. The entry in column $n$ is $s-r_n$, and its cofactor is $D_{n-1}(s)=P_n(s)$. Therefore \begin{align*} \det(sI_n-M(r_1,\dots,r_n))=(s-r_n)P_n(s)-\sum_{j=1}^{n-1} r_jP_j(s). \end{align*} This proves the formula as a polynomial identity in $\mathbb{R}[s]$, so no eigenvalue multiplicity argument is needed.[/step]

[guided]The delicate point is that the coefficients $c_1,\dots,c_{n-1}$ do not disappear from the characteristic polynomial. We avoid the possible pitfall of arguing only from the zero set of the characteristic equation by computing the determinant itself. Define $M(r_1,\dots,r_n) \in \mathbb{R}^{n \times n}$ by specifying its entries: the first column is $(c_1,\dots,c_{n-1},r_1)^\top$, the entries in positions $(j-1,j)$ are $1$ for $2 \le j \le n$, the last row is $(r_1,\dots,r_n)$, and all remaining entries are $0$. Define $P_1,\dots,P_n \in \mathbb{R}[s]$ by $P_1(s):=1$ and $P_{j+1}(s):=sP_j(s)-c_j$ for $1 \le j \le n-1$. The recursion shows inductively that $P_j$ has degree $j-1$ and leading coefficient $1$. When $n=1$, there are no coefficients $c_1,\dots,c_{n-1}$, no superdiagonal entries, and no sum over $j<n$. The matrix is $M(r_1)=(r_1)$, so \begin{align*} \det(sI_1-M(r_1))=s-r_1=(s-r_1)P_1(s). \end{align*} This proves the formula for the one-dimensional case. Assume now that $n\geq 2$. Set $N(s):=sI_n-M(r_1,\dots,r_n)$. For $1 \le j \le n-1$, let $N_j(s)$ denote the leading $j \times j$ submatrix of $N(s)$, and let $D_j(s):=\det N_j(s)$. The first determinant is \begin{align*} D_1(s)=s-c_1=P_2(s). \end{align*} For $2 \le j \le n-1$, expand $D_j(s)$ along the last column of $N_j(s)$. That column has only two nonzero entries: $-1$ in row $j-1$ and $s$ in row $j$. The $s$ entry contributes $sD_{j-1}(s)$. The cofactor of the $-1$ entry is computed from the matrix obtained by deleting row $j-1$ and column $j$; after the forced superdiagonal entries are read from right to left, its determinant is $c_j$, with the cofactor sign giving a total contribution $-c_j$. Hence \begin{align*} D_j(s)=sD_{j-1}(s)-c_j. \end{align*} By induction on $j$, this recurrence gives $D_j(s)=P_{j+1}(s)$ for every $1 \le j \le n-1$. It remains to include the last row, where the feedback parameters $r_1,\dots,r_n$ enter. Expand $\det N(s)$ along the last row. The entry in column $n$ is $s-r_n$, and its cofactor is $D_{n-1}(s)=P_n(s)$. For a column $j<n$, the last-row entry is $-r_j$. Deleting the last row and the $j$-th column leaves a block upper triangular matrix: its left block contributes $P_j(s)$, and its right block is triangular with determinant $1$. Thus the cofactor contribution from column $j$ is $-r_jP_j(s)$. Summing the last-row [cofactor expansion](/theorems/398) gives \begin{align*} \det(sI_n-M(r_1,\dots,r_n))=(s-r_n)P_n(s)-\sum_{j=1}^{n-1} r_jP_j(s). \end{align*} This is a determinant computation in the [polynomial ring](/page/Polynomial%20Ring) $\mathbb{R}[s]$, so it proves equality of polynomials directly and does not rely on eigenvalues or algebraic multiplicities.[/guided]

[step:Choose the transformed feedback row to match the prescribed polynomial] The polynomials $P_1,\dots,P_n$ form a basis of the real [vector space](/page/Vector%20Space) of polynomials of degree at most $n-1$, because their degrees are $0,1,\dots,n-1$ and each has leading coefficient $1$ in its own degree. Therefore there are unique real numbers $r_1,\dots,r_n$ such that \begin{align*} q(s)-sP_n(s)=-\sum_{j=1}^n r_jP_j(s). \end{align*} For this choice, the determinant formula from the previous step gives \begin{align*} \det(sI_n-M(r_1,\dots,r_n))=q(s). \end{align*} Since the last row of $\widetilde{A}+\widetilde{B}\widetilde{K}$ is $(c_n+k_1,k_2,\dots,k_n)$, define $k_1:=r_1-c_n$ and $k_j:=r_j$ for $2 \le j \le n$. Then $\widetilde{A}+\widetilde{B}\widetilde{K}=M(r_1,\dots,r_n)$, and hence \begin{align*} \det(sI_n-\widetilde{A}-\widetilde{B}\widetilde{K})=q(s). \end{align*} [/step]

[step:Transform the feedback row back to the original coordinates] Define \begin{align*} K := \widetilde{K}T^{-1} \in \mathbb{R}^{1 \times n}. \end{align*} Then \begin{align*} BK = B\widetilde{K}T^{-1}. \end{align*} Since $B=T\widetilde{B}$, we obtain \begin{align*} A+BK = T(\widetilde{A}+\widetilde{B}\widetilde{K})T^{-1}. \end{align*} Therefore \begin{align*} sI_n-A-BK = T(sI_n-\widetilde{A}-\widetilde{B}\widetilde{K})T^{-1}. \end{align*} Taking determinants and using multiplicativity of the determinant gives \begin{align*} \det(sI_n-A-BK)=\det(T)\det(sI_n-\widetilde{A}-\widetilde{B}\widetilde{K})\det(T^{-1}). \end{align*} Since $\det(T)\det(T^{-1})=1$ and $\det(sI_n-\widetilde{A}-\widetilde{B}\widetilde{K})=q(s)$, this becomes \begin{align*} \det(sI_n-A-BK)=q(s). \end{align*} This proves the desired pole placement statement for the original system. [/step]