## The pole-shifting theorem, part 2

In the last post I wrote about the pole-shifting theorem but included almost no information about the proof. Now I want to sketch that proof, following the account in the book of Sontag. It is convenient to talk about prescribing the characteristic polynomial rather than prescribing the eigenvalues. The characteristic polynomial contains the information about the set of eigenvalues together with information about their multiplicity. It is helpful to use changes of basis in the state space to simplify the problem. A change of basis leads to a similarity transformation of $A$ and so does not change the characteristic polynomial. It also does not change the rank of $R(A,B)$. Hence the property of controllability is not changed. Which polynomials can be obtained from matrices of the form $A+BF$ also does not change since the change of basis can be used to transform $F$ in an obvious way. Putting these things together shows that when proving the theorem for given matrices it is allowed to pass to new matrices by a change of basis when convenient.

The first step in the proof is to look at the theorem in the case of one control variable ($m=1$). I will use the notation $(A,b)$. In this case the system can be brought into a special form, the controller form, by a change of basis. Then it is elementary to solve for the unique feedback which solves the problem. The next step is to reduce the case of general $m$ to a modified control problem with $m=1$. Let $v$ be any vector with $Bv$ non-zero and $b=Bv$. The idea is to show that there is an $F_1$ such that $(A+BF_1,b)$ is controllable. If this can be done then the result for $m=1$ gives, for a given polynomial $\chi$, a matrix $f$ such that the characteristic polynomial of $(A+BF_1)+bf$ is $\chi$. But $(A+BF_1)+bf=A+B(F_1+vf)$ and so taking $F=F_1+vf$ solves the desired problem.

It remains to find $F_1$. For this purpose a sequence of vectors is constructed as follows. First choose a vector $v$ such that $Bv$ is non-zero and let $x_1=Bv$. Then $x_1$ is a non-zero element of the state space. Next choose $x_2=Ax_1+u_1$, where $u_1$ belongs to the image of $B$, in such a way that $x_1$ and $x_2$ are linearly independent. If this succeeds continue to choose $x_3=Ax_2+u_2$ in a similar way. The idea is to construct a maximal chain of linearly independent vectors $\{x_1,\ldots,x_k\}$ of this type. The claim is now that if $(A,B)$ is controllable $k=n$. Consider the space spanned by the $x_i$. It is of dimension $k$. Since the chain cannot be extended $Ax_k+Bu$ must also belong to this space, for any choice of $u$. In particular $Ax_k$ belongs to the space. Hence the image of $B$ belongs to the space. The definition of the $x_i$ then implies that $Ax_i$ belongs to the space for all $i$ so that the space is invariant under $A$. Putting these facts together shows that the image of $R(A,B)$ is contained in this space. By controllability it must therefore be the whole $n$-dimensional Euclidean space. Next define $F_1x_i=u_i$ for $i=1,2,\ldots,k-1$ and $F_1x_k$ arbitrarily. Then $R(A+BF_1,x_1)=(x_1,\ldots,x_n)$, which completes the proof.

In fact this theorem can be extended to one which describes which polynomials can be assigned when $(A,B)$ is not controllable. They are the polynomials of the form $\chi_1\chi_u$ where $\chi_1$ is an arbitrary monic polynomial of degree $r$ and $\chi_u$ is a polynomial defined by $(A,B)$ called the uncontrollable part of the characteristic polynomial of $A$. What this means is that some poles (the uncontrollable ones) are fixed once and for all and the others can be shifted arbitrarily.