[proofplan] We pass to the controllability basis generated by $B, AB, \dots, A^{n-1}B$. In that basis the pair $(A,B)$ takes companion form: the input vector is the first basis vector and the matrix shifts the controllability basis, with one final column determined by the characteristic polynomial of $A$. The row $e_n^\top \mathcal{C}(A,B)^{-1}$ becomes the last coordinate functional in this basis, so the feedback is reduced to a companion-matrix calculation. We then prove directly, by a determinant-rank-one computation, that subtracting $e_1 e_n^\top q(M)$ from a controllable companion matrix $M$ replaces its characteristic polynomial by $q$. [/proofplan] [step:Put the system into the controllability basis] Define \begin{align*} T := \mathcal{C}(A,B) = \begin{bmatrix} B & AB & \cdots & A^{n-1}B \end{bmatrix} \in \mathbb{R}^{n \times n}. \end{align*} By controllability, $T$ is invertible. Define \begin{align*} M := T^{-1}AT \in \mathbb{R}^{n \times n}, \qquad b := T^{-1}B \in \mathbb{R}^{n \times 1}. \end{align*} For each integer $j$ with $1 \le j \le n$, let $e_j \in \mathbb{R}^n$ denote the $j$-th standard basis vector. Since the first column of $T$ is $B$, we have $b=e_1$. For $1 \le j \le n-1$, the $j$-th column of $T$ is $A^{j-1}B$, hence \begin{align*} M e_j = T^{-1}A T e_j = T^{-1}A^jB = e_{j+1}. \end{align*} Let \begin{align*} p: \mathbb{R} \to \mathbb{R}, \qquad s \mapsto \det(sI_n - M) \end{align*} be the characteristic polynomial of $M$. Since $M$ is similar to $A$, this is also the characteristic polynomial of $A$. Write \begin{align*} p(s) = s^n + c_{n-1}s^{n-1} + \cdots + c_1s + c_0. \end{align*} Define scalars $\gamma_1,\dots,\gamma_n \in \mathbb{R}$ by \begin{align*} M e_n = \gamma_1 e_1 + \gamma_2 e_2 + \cdots + \gamma_n e_n. \end{align*} Using $M e_j=e_{j+1}$ for $1\le j\le n-1$, a Laplace expansion of $\det(sI_n-M)$ along the first row and induction on $n$ gives \begin{align*} \det(sI_n-M)=s^n-\gamma_n s^{n-1}-\gamma_{n-1}s^{n-2}-\cdots-\gamma_2s-\gamma_1. \end{align*} Comparing this expression with the displayed formula for $p(s)$ yields $\gamma_{i+1}=-c_i$ for $0\le i\le n-1$. Hence \begin{align*} M e_n = -c_0e_1 - c_1e_2 - \cdots - c_{n-1}e_n. \end{align*} Thus $M$ is the companion matrix determined by \begin{align*} M e_j = e_{j+1} \quad \text{for } 1 \le j \le n-1, \end{align*} and \begin{align*} M e_n = -\sum_{i=0}^{n-1} c_i e_{i+1}. \end{align*} [/step] [step:Rewrite the feedback in companion coordinates] Since polynomial evaluation commutes with similarity, we have \begin{align*} q(A)T = Tq(M). \end{align*} Therefore \begin{align*} KT = -e_n^\top T^{-1}q(A)T = -e_n^\top q(M). \end{align*} The closed-loop matrix is similar to \begin{align*} T^{-1}(A+BK)T = T^{-1}AT + T^{-1}BKT = M - e_1e_n^\top q(M). \end{align*} It is therefore enough to prove that \begin{align*} \det(sI_n - M + e_1e_n^\top q(M)) = q(s). \end{align*} [/step] [step:Compute the characteristic polynomial after the rank-one feedback] Let \begin{align*} h: \mathbb{R} \to \mathbb{R}, \qquad s \mapsto q(s)-p(s). \end{align*} Then $\deg h \le n-1$. Since $p(M)=0$, we have \begin{align*} q(M)=h(M). \end{align*} Let $D := \{r \in \mathbb{R}: p(r) \ne 0\}$. Define the resolvent-vector map \begin{align*} x: D \to \mathbb{R}^n, \qquad s \mapsto (sI_n-M)^{-1}e_1. \end{align*} Fix $s \in D$. Write \begin{align*} x(s)=x_1(s)e_1+x_2(s)e_2+\cdots+x_n(s)e_n \end{align*} with coordinate functions $x_i:D\to\mathbb R$ for $1\le i\le n$. The equation $(sI_n-M)x(s)=e_1$ is equivalent, using the displayed companion relations for $M$, to the scalar recurrence \begin{align*} sx_1(s)+c_0x_n(s)=1, \end{align*} \begin{align*} -x_{i-1}(s)+sx_i(s)+c_{i-1}x_n(s)=0 \quad \text{for }2\le i\le n. \end{align*} Solving backward from the second recurrence gives, for every integer $k$ with $1\le k\le n-1$, \begin{align*} x_{n-k}(s)=\left(s^k+c_{n-1}s^{k-1}+\cdots+c_{n-k}\right)x_n(s). \end{align*} Taking $k=n-1$ gives \begin{align*} x_1(s)=\left(s^{n-1}+c_{n-1}s^{n-2}+\cdots+c_1\right)x_n(s). \end{align*} Substituting this expression into $sx_1(s)+c_0x_n(s)=1$ gives \begin{align*} p(s)x_n(s)=1. \end{align*} Hence \begin{align*} e_n^\top x(s)=x_n(s)=\frac{1}{p(s)}. \end{align*} Moreover, for every integer $j$ with $0 \le j \le n-1$, \begin{align*} e_n^\top M^j x(s)=\frac{s^j}{p(s)}. \end{align*} Indeed, the case $j=0$ is the displayed identity. If $1 \le j \le n-1$, then $Mx(s)=sx(s)-e_1$, and $e_n^\top M^{j-1}e_1=0$ because $M^{j-1}e_1=e_j$ with $j<n$. Hence induction gives the formula. Writing \begin{align*} h(s)=h_0+h_1s+\cdots+h_{n-1}s^{n-1}, \end{align*} we obtain \begin{align*} e_n^\top h(M)(sI_n-M)^{-1}e_1 = \frac{h(s)}{p(s)}. \end{align*} Because $p(s) \ne 0$, the matrix $N:=sI_n-M$ is invertible. Set $u:=e_1$ and $v:=h(M)^\top e_n$. Factoring $N$ from the rank-one perturbation gives \begin{align*} \det(N+uv^\top)=\det(N)\det(I_n+N^{-1}uv^\top). \end{align*} Set $a:=N^{-1}u \in \mathbb{R}^n$ and $b:=v \in \mathbb{R}^n$. To evaluate the second determinant, write $b_j$ for the $j$-th coordinate of $b$. The $j$-th column of $I_n+ab^\top$ is $e_j+b_j a$, so multilinearity and alternation of the determinant give \begin{align*} \det(I_n+ab^\top)=1+\sum_{j=1}^n b_j a_j=1+b^\top a. \end{align*} Applying this with $a=N^{-1}u$ and $b=v$ therefore gives \begin{align*} \det(sI_n-M+e_1e_n^\top h(M)) = \det(sI_n-M)\left(1+e_n^\top h(M)(sI_n-M)^{-1}e_1\right). \end{align*} Substituting the preceding computation yields \begin{align*} \det(sI_n-M+e_1e_n^\top h(M)) = p(s)\left(1+\frac{h(s)}{p(s)}\right)=p(s)+h(s)=q(s). \end{align*} Both sides are polynomials in $s$, and they agree for every $s$ with $p(s)\ne 0$. Since the set of such $s$ is infinite, the polynomial identity holds for all $s \in \mathbb{R}$. [guided] The purpose of this step is to isolate the only real computation in the proof. We have reduced the problem to a companion matrix $M$ and must show that the rank-one correction $-e_1e_n^\top q(M)$ changes the characteristic polynomial from $p$ to $q$. First define the difference polynomial \begin{align*} h: \mathbb{R} \to \mathbb{R}, \qquad s \mapsto q(s)-p(s). \end{align*} Because both $p$ and $q$ are monic of degree $n$, the leading terms cancel, so $\deg h \le n-1$. Also $p(M)=0$ for this companion matrix: the identity $M^{j-1}e_1=e_j$ holds for $1 \le j \le n$, and the final-column relation gives exactly \begin{align*} M^n e_1 + c_{n-1}M^{n-1}e_1+\cdots+c_1Me_1+c_0e_1=0. \end{align*} Since $e_1,Me_1,\dots,M^{n-1}e_1$ form the standard basis, we must still check the identity on each vector of this basis. The matrix $p(M)$ commutes with $M$ because $p(M)$ is a polynomial in $M$. Hence, for every integer $k$ with $0\le k\le n-1$, \begin{align*} p(M)M^k e_1=M^k p(M)e_1=0. \end{align*} Thus $p(M)$ vanishes on the basis $e_1,Me_1,\dots,M^{n-1}e_1$, and therefore $p(M)=0$. Consequently $q(M)=h(M)$. Let $D := \{r \in \mathbb{R}: p(r) \ne 0\}$. For $s \in D$, the condition $p(s)\ne 0$ is exactly the condition that $sI_n-M$ is invertible. Define the resolvent-vector map \begin{align*} x: D \to \mathbb{R}^n, \qquad s \mapsto (sI_n-M)^{-1}e_1. \end{align*} Fix $s \in D$. The scalar quantity we need is $e_n^\top h(M)x(s)$. Since $h$ has degree at most $n-1$, it is enough to understand $e_n^\top M^j x(s)$ for $0 \le j \le n-1$. Write \begin{align*} x(s)=x_1(s)e_1+x_2(s)e_2+\cdots+x_n(s)e_n, \end{align*} where each $x_i:D\to\mathbb R$ is the $i$-th coordinate function. Expanding $(sI_n-M)x(s)=e_1$ using the companion relations for $M$ gives \begin{align*} sx_1(s)+c_0x_n(s)=1, \end{align*} and, for $2\le i\le n$, \begin{align*} -x_{i-1}(s)+sx_i(s)+c_{i-1}x_n(s)=0. \end{align*} The second recurrence is best solved backward because it expresses $x_{i-1}(s)$ in terms of $x_i(s)$ and $x_n(s)$: \begin{align*} x_{i-1}(s)=sx_i(s)+c_{i-1}x_n(s). \end{align*} Iterating this identity gives, for every integer $k$ with $1\le k\le n-1$, \begin{align*} x_{n-k}(s)=\left(s^k+c_{n-1}s^{k-1}+\cdots+c_{n-k}\right)x_n(s). \end{align*} In particular, \begin{align*} x_1(s)=\left(s^{n-1}+c_{n-1}s^{n-2}+\cdots+c_1\right)x_n(s). \end{align*} Substituting this into the first coordinate equation gives \begin{align*} \left(s^n+c_{n-1}s^{n-1}+\cdots+c_1s+c_0\right)x_n(s)=1. \end{align*} The polynomial in parentheses is $p(s)$, so \begin{align*} e_n^\top x(s)=x_n(s)=\frac{1}{p(s)}. \end{align*} The remaining recurrence comes from rewriting the same equation as \begin{align*} Mx(s)=sx(s)-e_1. \end{align*} For $1 \le j \le n-1$, multiply by $M^{j-1}$ and then apply $e_n^\top$: \begin{align*} e_n^\top M^j x(s)=s\,e_n^\top M^{j-1}x(s)-e_n^\top M^{j-1}e_1. \end{align*} But $M^{j-1}e_1=e_j$, and $e_n^\top e_j=0$ for $j<n$. Thus \begin{align*} e_n^\top M^j x(s)=s\,e_n^\top M^{j-1}x(s). \end{align*} Starting from $e_n^\top x(s)=1/p(s)$, induction gives \begin{align*} e_n^\top M^j x(s)=\frac{s^j}{p(s)} \end{align*} for every $0 \le j \le n-1$. Write \begin{align*} h(s)=h_0+h_1s+\cdots+h_{n-1}s^{n-1}. \end{align*} Using linearity and the preceding moment computation, \begin{align*} e_n^\top h(M)(sI_n-M)^{-1}e_1 = \sum_{j=0}^{n-1} h_j e_n^\top M^j x(s) = \frac{h(s)}{p(s)}. \end{align*} Finally set $N:=sI_n-M$, $u:=e_1$, and $v:=h(M)^\top e_n$. Since $s\in D$, the matrix $N$ is invertible. We factor $N$ from the rank-one perturbation: \begin{align*} \det(N+uv^\top)=\det(N)\det(I_n+N^{-1}uv^\top). \end{align*} Set $a:=N^{-1}u \in \mathbb{R}^n$ and $b:=v \in \mathbb{R}^n$. We now compute the rank-one determinant directly. Write $a_j$ and $b_j$ for the $j$-th coordinates of $a$ and $b$. The $j$-th column of $I_n+ab^\top$ is $e_j+b_j a$. By multilinearity of the determinant in the columns, expanding the product produces the determinant of $I_n$, the $n$ terms with exactly one column replaced by $a$, and terms with at least two columns equal to scalar multiples of $a$. The latter terms vanish by alternation. Therefore \begin{align*} \det(I_n+ab^\top)=1+\sum_{j=1}^n b_j\det(e_1,\dots,e_{j-1},a,e_{j+1},\dots,e_n). \end{align*} The displayed determinant with $a$ in the $j$-th column equals $a_j$, so \begin{align*} \det(I_n+ab^\top)=1+\sum_{j=1}^n b_j a_j=1+b^\top a. \end{align*} Applying this with $a=N^{-1}u$ and $b=v$ yields \begin{align*} \det(sI_n-M+e_1e_n^\top h(M)) = \det(sI_n-M)\left(1+e_n^\top h(M)(sI_n-M)^{-1}e_1\right). \end{align*} Since $\det(sI_n-M)=p(s)$, this becomes \begin{align*} \det(sI_n-M+e_1e_n^\top h(M)) = p(s)\left(1+\frac{h(s)}{p(s)}\right) = p(s)+h(s) = q(s). \end{align*} This proves the identity for all $s$ with $p(s)\ne 0$. The two sides are polynomials in $s$, and a nonzero polynomial has only finitely many roots, so equality on the infinite set $\{s \in \mathbb{R}:p(s)\ne 0\}$ implies equality for every $s \in \mathbb{R}$. [/guided] [/step] [step:Transfer the companion-coordinate identity back to the original coordinates] From the preceding step and $q(M)=h(M)$, we have \begin{align*} \det(sI_n - M + e_1e_n^\top q(M))=q(s) \end{align*} for every $s \in \mathbb{R}$. Since \begin{align*} T^{-1}(A+BK)T = M - e_1e_n^\top q(M), \end{align*} the invariance of characteristic polynomial under similarity gives that similar matrices have the same characteristic polynomial. Hence \begin{align*} \det(sI_n-A-BK)=\det(sI_n-M+e_1e_n^\top q(M))=q(s). \end{align*} This is precisely the asserted pole-placement formula for the feedback gain \begin{align*} K=-e_n^\top \mathcal{C}(A,B)^{-1}q(A). \end{align*} [/step]