\documentclass[10pt]{studiamnew}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\sloppy

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lem}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{definition}
\newtheorem{obser}[theorem]{Remark}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{expl}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{notation}[theorem]{Notation}

\renewcommand{\theequation}{\thesection.\arabic{equation}}
\numberwithin{equation}{section}

\begin{document}
%
%\setcounter{page}{1}
%\setcounter{firstpage}{1}
%\setcounter{lastpage}{11}
%\renewcommand{\currentvolume}{unknown yet}
%\renewcommand{\currentyear}{20xx}
%\renewcommand{\currentissue}{2}
%
\title{A new proof of Ackermann\textprime s formula from control theory}
\author{ Marius Costandin}
		\address{Technical University of Cluj-Napoca,
          	Str. Memorandumului nr. 28, 400114, Cluj-Napoca, Romania}
\email{costandin@mail.utcluj.ro}
%
\author{Petru  Dobra}
		\address{Technical University of Cluj-Napoca,
          	Str. Memorandumului nr. 28, 400114, Cluj-Napoca, Romania}
\email{petru.dobra@aut.utcluj.ro}
%
\author{Bogdan Gavrea}
		\address{Technical University of Cluj-Napoca,
          	Str. Memorandumului nr. 28, 400114, Cluj-Napoca, Romania}
\email{bogdan.gavrea@math.utcluj.ro}
%
\subjclass{ 26D10  46N30.}
\keywords{eigenvalues placement algorithms, rank one updates, linear systems, matrix determinants}
\begin{abstract}
This  paper presents a novel proof for the well known Ackermann's formula, related to pole placement in linear time invariant systems. The proof uses a lemma \cite{ref1}, concerning rank one updates for matrices, often used to efficiently compute the determinants. The proof is given in great detail, but it can be summarised to few lines.
\end{abstract}
\maketitle

\section{Introduction}
         
	Given a matrix $A \in \mathbb{R}^{n \times n}$ and a vector $B \in \mathbb{R}^{n \times 1}$, it is known, see \cite{refAcker} that if the marix $Co(A,B) = [B| A\cdot B| \hdots |A^{n-1}\cdot B]$ is invertible then there exists a unique $K \in \mathbb{R}^{n \times 1}$ such that $\hat{A} = A  + B\cdot K^T$ has any desired set of eigenvalues $\mathcal{S} = \{\lambda_1^*, \hdots, \lambda_n^*\}$, closed under complex conjugation, that is if $\lambda \in \mathcal{S}$ then $\bar{\lambda} \in \mathcal{S}$.
          Algorithms for finding $K$ are well known in literature among which the algorithm of Bass-Gura (see \cite{refBG}) and Ackerman (see \cite{refAcker}) are mentioned. \\ 
          \indent In the following a new demonstration to Ackermann's result is given, using a well known lemma often used for computing the determinant of a certain invertible matrix, see \cite{ref1}. This lemma relates the determinant of a rank-one update to the determinant of the initial matrix. For an elegant proof of this result we point the reader to \cite{ref1}.
	   
 	\begin{lem}[Matrix determinant lemma, \cite{ref1}] \label{L1}
 	Suppose that $A$ is an invertible square matrix and $u$ and $v$ are column vectors. Then: 
 	\begin{align}
 	det(A + uv^{T}) = \left( 1 + v^{T}A^{-1}u\right)det(A)
 	\end{align}
 	\end{lem}

 	\section{The novel proof for Ackermann's formula} \label{S2}
 	\begin{theorem}[Ackermann]
 	Let $ \dot X = A\cdot X + B\cdot u$ be a linear time invariant dynamical system, with $X,B \in \mathbb{R}^{n}$ and $A \in \mathbb{R}^{n \times n}$. If $Co(A,B) = [B| A\cdot B| \hdots | A^{n-1}\cdot B]$ is invertible, then the matrix $\hat{A} = A - B\cdot K_x^T$ has the user-defined eigenvalues $\{ \lambda^*_1, \hdots, \lambda^*_p\}$, with algebraic multiplicities $q_1, \hdots, q_p$, where
 	\begin{align}
 	 K_x &= \left(\prod_{i=1}^p (A - \lambda^*_i I)^{q_i}\right)^T \cdot Co(A,B)^{-T}\cdot \begin{bmatrix} 0\\ 0\\ \vdots \\ 1\end{bmatrix} \nonumber \\
 	 &= P^*(A)^T\cdot Co(A,B)^{-T}\cdot \begin{bmatrix} 0\\ 0\\ \vdots \\ 1\end{bmatrix} \nonumber 
 	 \end{align}  
 	\end{theorem}
 	\begin{proof}
 	 Let $P^*(\lambda) = \prod_{i=1}^p (\lambda - \lambda^*_i)^{q_i} = det(\lambda I - \hat{A})$ denote the characteristic polynomial of $\hat{A}$ and $P(\lambda) = det(\lambda I - A)$ the characteristic polynomial of $A$. Suppose, for start, that the desired eigenvalues are not already eigenvalues for the system matrix, $A$. Therefore $det(\lambda^*_i I - A) \neq 0$ for all $i \in \{1,\hdots, p\}$.  Then, from Lemma \ref{L1}:
 	\begin{align}\label{E4}
 	P^*(\lambda) =& det(\lambda I - \hat A) \nonumber \\
     %=& (\lambda - \lambda_1^{\star}) \dots \left(\lambda - \lambda_n^{\star}\right) \nonumber \\
 	=& det(\lambda I - (A - BK_x^{T})) \nonumber \\
 	=& det((\lambda I - A) + BK_x^{T}) \nonumber \\
 	=& \left(1 + K_x^{T}(\lambda I - A)^{-1}B\right) det(\lambda I - A) \nonumber \\
 	=& \left(1 + K_x^{T}(\lambda I - A)^{-1}B\right) \cdot P(\lambda)
 	\end{align}
 	
  	We are interested in finding $K_x$ such that Equation (\ref{E4}) holds. Equation (\ref{E4}) is a monic polynomial equality, so it is enough to hold for the roots. Let $\lambda = \lambda^*_i$ in Equation (\ref{E4}). 
 
  	Because $\lambda^*_i$ has multiplicity $q_i$, then the folowing relations are obtained:
  	\begin{align}
  	\begin{cases}
  	K_x^T \cdot (\lambda_i^* I - A)^{-1}\cdot B = -1\\
  	K_x^T \cdot (\lambda_i^* I - A)^{-2}\cdot B = 0\\
  	\vdots \\
  	K_x^T \cdot (\lambda_i^* I - A)^{-q_i}\cdot B = 0
  	\end{cases} \hspace{1cm} \forall i \in \{1,\hdots, p\}
  	\end{align} Hence
  	\begin{align}\label{E6}
  	\begin{bmatrix} B^T \cdot (\lambda_1^* I - A^T)^{-1} \\ B^T \cdot(\lambda_1^* I - A^T)^{-2}\\ 
  	\vdots \\ B^T \cdot (\lambda_1^* I - A^T)^{-q_1} \\ \vdots \\ B^T \cdot (\lambda_p^* I - A^T)^{-1} \\ B^T \cdot(\lambda_p^* I - A^T)^{-2}\\ \vdots \\ B^T \cdot (\lambda_1^* I - A^T)^{-q_p}\end{bmatrix} \cdot K_x =  \begin{bmatrix} -1\\0\\ \vdots \\ 0\\ \vdots \\ -1 \\ 0\\ \vdots\\ 0\end{bmatrix}
  	\end{align} Denote
  	$$ C = \begin{bmatrix}(\lambda_1^* I - A)^{-1}\cdot B| &\hdots &| (\lambda_1^* I - A)^{-q_1}\cdot B| &\hdots \end{bmatrix}$$ and $$N =  \begin{bmatrix} -1&0& \hdots & 0& \hdots & -1 & 0& \hdots& 0\end{bmatrix}^T $$ then 
  	$$ C^T \cdot K_x = N$$ Looking closely at $C$ one can see:
  	\begin{align}\label{E7}
  	&\prod_{i=1}^p(\lambda^*_i I -A)^{q_i} \cdot C = \nonumber \\
  	&=  \begin{bmatrix}P_1\{\lambda_1^*\}(A)\cdot B| &\hdots &| P_{q_1}\{\lambda_1^*\}(A)\cdot B| &\hdots \end{bmatrix} \nonumber \\
  	&= \bar{C}
  	\end{align} where $P_j\{\lambda^*_k\}(A) = \left(\prod_{i=1,i\neq k}^p (\lambda^*_i I - A)^{q_i}\right)\cdot (\lambda^*_k I - A)^{q_k-j}$ with $k \in \overline{1,p}$ and $j \in \overline{1,q_k}$. If seen as a polynomial over $\mathbb{R}$, then it's roots are $\{\lambda^*_1, \hdots, \lambda_k^*, \hdots, \lambda^*_p\}$, with the multiplicity $q_1, \hdots, q_k - j, \hdots, q_p$. The order of the polynomial is $n-j$. Stacking the polynomial's coefficients in a vector, with the coefficient of the smallest power in the first position, and leaving the same name for the vector, one has:
  	\begin{align}\label{E8}
  	\bar{C} &= \begin{bmatrix} B| & A\cdot B| & \hdots| & A^{n-1} \cdot B\end{bmatrix} \cdot \nonumber \\
  	&\cdot \begin{bmatrix} P_1\{\lambda^*_1\}|& \hdots| & P_{q_1}\{\lambda^*_1\}| & \hdots|  & P_1\{\lambda_p^*\}| & \hdots|& P_{q_p}\{\lambda_p^*\} \end{bmatrix} \nonumber \\
  	&= Co(A,B) \cdot \mathcal{P}
  	\end{align}
  	Of course, $\mathcal{P}$ is invertible, since it has linearly independent columns. Indeed let $\alpha_1^1 \cdot P_1\{\lambda^*_1\} + \hdots + \alpha_1^p\cdot P_1\{\lambda^*_p\} + \hdots = 0$ be a null linear combination of the columns of $\mathcal{P}$. Suppose the polynomial's variable is $X$. Let $k \in \overline{1,p}$ and let $\alpha_{j}^k$ be the the coefficient of the polynomial having $\lambda_k^*$ as a root with the smallest multiplicity $m_k$. Differentiating the above linear combination, $m_k$ times, with respect to $X$, then replacing $X$ with $\lambda^*_k$, will yield $\alpha_{q_k}^k = 0$. Repeating the process will conclude that the polynomials are linear independent. Hence:
  	\begin{align}\label{E9}
  	C^{-T} = \left( \prod_{i=1}^p(\lambda^*_i I - A)^{q_i} \right)^{T}\cdot Co(A,B)^{-T} \cdot \mathcal{P}^{-T}
  	\end{align} therefore
  	\begin{align} \label{E10}
  	K_x &= \left( \prod_{i=1}^p(A - \lambda^*_i I)^{q_i} \right)^{T}\cdot Co(A,B)^{-T} \cdot (-1)^n \cdot \mathcal{P}^{-T} \cdot N \nonumber \\
  	&= P^*(A)^T \cdot Co(A,B)^{-T} \cdot (-1)^n \cdot \mathcal{P}^{-T} \cdot N 
  	\end{align} Denote $V = (-1)^n \cdot \mathcal{P}^{-T}\cdot N$ therefore $(-1)^n \cdot \mathcal{P}^T \cdot V = N$. Because $\mathcal{P}$ is invertible, $V$ is unique.
  	\begin{align}\label{E11}
  	(-1)^n \cdot \begin{bmatrix}P_1\{\lambda^*_1\}^T\\ P_2\{\lambda^*_1\}^T\\ \vdots \\ P_{q_1}\{\lambda^*_1\}^T\\ \vdots \\ P_1\{\lambda^*_p\}^T\\ P_2\{\lambda^*_p\}^T\\ \vdots \\ P_{q_p}\{\lambda^*_p\}^T \end{bmatrix} \cdot \begin{bmatrix}v_1 \\ \vdots \\ v_n \end{bmatrix} = \begin{bmatrix} -1\\0\\ \vdots \\ 0\\ \vdots \\ -1 \\ 0\\ \vdots\\ 0\end{bmatrix}
  	\end{align} Because $P_j\{\lambda^*_k\}$ has the order $n-j$, and the coefficient of the smallest power is on the first position in vector,  that is the coefficient of the greatest power is on the last position, follows: 
  	\begin{align}\label{E12}
  	(-1)^n \cdot \begin{bmatrix}\hdots &(-1)^{n-1}\\\hdots &0 \\ \vdots & \vdots\\ \hdots &0 \\ \vdots & \vdots \\ \hdots & (-1)^{n-1}\\ \hdots &0 \\ \vdots & \vdots \\ \hdots &0 \end{bmatrix} \cdot \begin{bmatrix}v_1 \\ \vdots \\ v_n \end{bmatrix} = \begin{bmatrix} -1\\0\\ \vdots \\ 0\\ \vdots \\ -1 \\ 0\\ \vdots\\ 0\end{bmatrix}
  	\end{align} It is easy to see that $V = [0,\hdots, 0,1]^T$ is a solution.
  	Therefore
  	\begin{align}\label{E13}
  	K_x = P^*(A)^T \cdot Co(A,B)^{-T} \cdot V
  	\end{align}
  	 If $\lambda_i^* = \lambda_i$, for some $i\in \overline{1,p}$, then take $\lambda^*_i(\epsilon) = \epsilon + \lambda_i^*$ to obtain $det(\lambda I - (A - B\cdot K_x(\epsilon)^T)) = P^*\{\epsilon\}(\lambda)$. Letting $\epsilon \longrightarrow 0$, one has $det(\lambda I - (A - B\cdot K_x^T)) = P^*(\lambda)$. 
  \end{proof}
 
 	\section{Conclusions}
 	A new proof for the well known Akermann's formula was presented. The proof uses a matrix lemma, giving an in depth look at the mechanics of eigenvalues change using rank one updates.  The state feedback matrix $K_x$ is shown to be the unique solution to a system of equations, obtained using a well known matrix lemma. The proof can be summarised as follows:
 	\begin{enumerate}
 	\item Use Equation (\ref{E4}) to obtaing Equation (\ref{E6})
 	\item Use Equations (\ref{E7}) and (\ref{E8}) to obtain Equation (\ref{E9}) regardind the resolvent matrix
 	\item Use Equation (\ref{E11}) and (\ref{E12}) in Equation (\ref{E10}) to obtain $K_x$ 
 	\end{enumerate}
 	

\section{References} 
 	\begin{thebibliography}{1}
\bibitem{ref1} Jiu Ding, Aihui Zhou \emph{ Eigenvalues of rank-one updated matrices with some applications} Appl. Math. Lett. 20 (2007) 1223-1226

\bibitem{refAcker} Ackermann J., \emph{ Der Entwurf linearer Regelungsysteme im Zustandraum} Regeltech. Proz.-Datenverarb.,7,pp.297-300,1972

\bibitem{refOgata} Ogata K., \emph{ Modern Control Engineering, 4th Ed} Englewood Cliffs, NJ, Prentice Hall, 2001

\bibitem{refBG} W. Bass, I. Gura \emph{ High order system design via state-space considerations} Preprints, 1965 Join Automatic Control Conference, pp. 311-318, Rensselner Polytechnic Institute, Troy, N.Y., June 22-25

 	\end{thebibliography}

\end{document}
