[proofplan] The proof reduces the multi-input statement to the single-input pole placement theorem. We first prove a feedback-cyclic-vector lemma: for a controllable pair $(A,B)$ and a nonzero vector $b$ in the input range, one can choose a preliminary feedback $F$ so that $(A+BF,b)$ is controllable. The construction enlarges the cyclic subspace generated by $b$ one dimension at a time. Then the desired conjugation-invariant pole multiset gives a real monic polynomial, and single-input pole placement applied to $(A+BF,b)$ assigns that polynomial. Since $b$ lies in the range of $B$, the final single-input feedback is absorbed into a real multi-input feedback matrix. [/proofplan]

[step:Convert the desired pole multiset into a real characteristic polynomial] Because $\Lambda$ is closed under complex conjugation, define the real polynomial map $q:\mathbb R\to\mathbb R$ by \begin{align*} q(s):=\prod_{\lambda\in\Lambda}(s-\lambda) \end{align*} has real coefficients. It is monic of degree $n$, and a real matrix has spectrum $\Lambda$ with algebraic multiplicity exactly when its characteristic polynomial is $q$. If $n=0$, the assertion is vacuous. Assume $n\geq 1$. Since $(A,B)$ is controllable, the input map $B:\mathbb R^m\to\mathbb R^n$ is not the zero map. Choose $v\in\mathbb R^m$ such that \begin{align*} b:=Bv\ne 0. \end{align*} [/step]

[step:Prove the feedback-cyclic-vector lemma]We prove the following finite-dimensional lemma. If $(A,B)$ is controllable and $0\ne b\in \operatorname{im}B$, then there exists $F\in\mathbb R^{m\times n}$ such that the single-input pair $(A+BF,b)$ is controllable. First note that controllability of a pair is invariant under state feedback. If $(M,B)$ is controllable and $G\in\mathbb R^{m\times n}$, then $(M+BG,B)$ is controllable. Indeed, every vector $(M+BG)^kBu$ lies in the span of vectors $M^jBw$, by induction on $k$. Conversely, since $M=(M+BG)+B(-G)$, the same argument with $-G$ expresses each $M^kBu$ in the reachable span of $(M+BG,B)$. Thus the two reachable spans are equal. We now construct the feedback by induction. Set \begin{align*} F_0:=0,\qquad A_0:=A. \end{align*} At stage $j$, assume $(A_j,B)$ is controllable and $A_j=A+BF_j$. Let \begin{align*} V_j:=\operatorname{span}\{b,A_jb,A_j^2b,\dots\}. \end{align*} This subspace is $A_j$-invariant. If $V_j=\mathbb R^n$, then $(A_j,b)$ is controllable and $F:=F_j$ proves the lemma. Suppose $V_j\ne\mathbb R^n$. If $\operatorname{im}B\subset V_j$, then $A_j$-invariance of $V_j$ would imply $A_j^kBu\in V_j$ for every $k\geq 0$ and every $u\in\mathbb R^m$, contradicting controllability of $(A_j,B)$. Hence choose $u_j\in\mathbb R^m$ such that \begin{align*} Bu_j\notin V_j. \end{align*} Let $r_j:=\dim V_j$. The vectors $b,A_jb,\dots,A_j^{r_j-1}b$ form a basis of $V_j$: if a first linear dependence occurred earlier, $V_j$ would be spanned by fewer than $r_j$ Krylov vectors, contradicting $r_j=\dim V_j$. Choose a linear functional $\ell_j:\mathbb R^n\to\mathbb R$ such that $\ell_j(A_j^{r_j-1}b)=1$ and $\ell_j(A_j^ib)=0$ for $0\leq i\leq r_j-2$. Define $G_j:\mathbb R^n\to\mathbb R^m$ by \begin{align*} G_jx:=\ell_j(x)u_j. \end{align*} Set \begin{align*} F_{j+1}:=F_j+G_j,\qquad A_{j+1}:=A+BF_{j+1}=A_j+BG_j. \end{align*} For $0\leq i\leq r_j-2$, we have $G_jA_j^ib=0$, so the first $r_j$ cyclic vectors are unchanged: \begin{align*} A_{j+1}^ib=A_j^ib \end{align*} for $0\leq i\leq r_j-1$. The next cyclic vector satisfies \begin{align*} A_{j+1}^{r_j}b=A_j^{r_j}b+Bu_j. \end{align*} Here $A_j^{r_j}b\in V_j$ because $V_j$ is $A_j$-invariant, while $Bu_j\notin V_j$. Therefore $A_{j+1}^{r_j}b\notin V_j$, and the cyclic subspace generated by $b$ under $A_{j+1}$ has dimension at least $r_j+1$. By state-feedback invariance, $(A_{j+1},B)$ is controllable, so the induction hypotheses hold at the next stage. The dimension of $V_j$ strictly increases whenever it is not yet $n$. Hence after at most $n-1$ enlargement steps, some $V_j$ is all of $\mathbb R^n$. For that $j$, $(A+BF_j,b)$ is controllable.[/step]

[guided]We repeat the induction carefully. State feedback does not change the reachable span: for a feedback $G$, the reachable span of $(M+BG,B)$ is contained in the reachable span of $(M,B)$ because $(M+BG)^kBu$ expands into a linear combination of vectors $M^aBw$. Replacing $M$ by $M+BG$ and $G$ by $-G$ gives the reverse containment, since $M=(M+BG)+B(-G)$. Initialize \begin{align*} F_0:=0,\qquad A_0:=A. \end{align*} Assume at stage $j$ that $A_j=A+BF_j$ and $(A_j,B)$ is controllable. Define \begin{align*} V_j:=\operatorname{span}\{b,A_jb,A_j^2b,\dots\}. \end{align*} If $V_j=\mathbb R^n$, then $(A_j,b)$ is controllable and we stop. If $V_j\ne\mathbb R^n$, then $\operatorname{im}B$ cannot be contained in $V_j$. Otherwise $A_j^kBu\in V_j$ for all $k\geq 0$ and all $u\in\mathbb R^m$, contradicting controllability of $(A_j,B)$. Choose $u_j\in\mathbb R^m$ with \begin{align*} Bu_j\notin V_j. \end{align*} Let $r_j:=\dim V_j$. The vectors $b,A_jb,\dots,A_j^{r_j-1}b$ form a basis of $V_j$, because a first linear dependence among earlier Krylov vectors would make all later Krylov vectors lie in their smaller span. Choose $\ell_j:\mathbb R^n\to\mathbb R$ with \begin{align*} \ell_j(A_j^{r_j-1}b)=1 \end{align*} and \begin{align*} \ell_j(A_j^ib)=0 \end{align*} for $0\leq i\leq r_j-2$. Define \begin{align*} G_jx:=\ell_j(x)u_j. \end{align*} Then $F_{j+1}:=F_j+G_j$ and $A_{j+1}:=A_j+BG_j$. For $0\leq i\leq r_j-2$, the equality $G_jA_j^ib=0$ preserves the next vector, and therefore \begin{align*} A_{j+1}^ib=A_j^ib \end{align*} for $0\leq i\leq r_j-1$. At the next power, \begin{align*} A_{j+1}^{r_j}b=A_j^{r_j}b+Bu_j. \end{align*} The first term lies in $V_j$ and the second does not, so this new vector is outside $V_j$. Thus $\dim V_{j+1}\geq r_j+1$. State-feedback invariance gives controllability of $(A_{j+1},B)$, so the induction can continue. Since dimensions are bounded by $n$, the process reaches $V_j=\mathbb R^n$ in finitely many steps.[/guided]

[step:Apply single-input pole placement after the preliminary feedback] By the lemma, choose $F\in\mathbb R^{m\times n}$ such that $(A+BF,b)$ is controllable. We now use the independently staged theorem [Pole Placement Theorem for Single-Input Controllable Linear Systems](/theorems/6393) (TEMP-33), whose precise form says: if $M\in\mathbb R^{n\times n}$ and $b_0\in\mathbb R^{n\times 1}$ form a controllable single-input pair, then for every real monic polynomial $p$ of degree $n$ there is a row $h_0\in\mathbb R^{1\times n}$ with $\det(sI_n-M-b_0h_0)=p(s)$. Its hypotheses hold here with $M=A+BF$, $b_0=b$, and $p=q$. Therefore there is a row vector $h\in\mathbb R^{1\times n}$ such that \begin{align*} \det(sI_n-(A+BF)-bh)=q(s). \end{align*} Since $b=Bv$, define \begin{align*} K:=F+vh\in\mathbb R^{m\times n}. \end{align*} Here $vh$ denotes the product of the column vector $v\in\mathbb R^m$ and the row vector $h\in\mathbb R^{1\times n}$. Then \begin{align*} A+BK=A+BF+Bvh=A+BF+bh. \end{align*} Consequently \begin{align*} \det(sI_n-A-BK)=q(s). \end{align*} The roots of this characteristic polynomial are exactly the elements of $\Lambda$, counted with algebraic multiplicity. Thus $\sigma(A+BK)=\Lambda$ with algebraic multiplicity, as required. [/step]