Controlability of LTI Discrete-Time Systems

The first $n+1$ states of a linear time-invariant system $$x_{k+1}=A{x}_k+B{u}_k,x_k\in {\mathbb{R}}^n,u_k\in {\mathbb{R}}^m,$$ assuming an initial state $x_0$ and a series of inputs $\{u_k{\}}_0^{N-1}$, can be expressed as $$\begin{array}{rl}{x}_1& =A{x}_0+B{u}_0\\ x_2& =A^2{x}_0+AB{u}_0+B{u}_1\\ & ⋮\\ x_n& =A^n{x}_0+A^{n-1}B{u}_0+A^{n-2}B{u}_1+\dots +B{u}_{n-1}\\ x_{n+1}& =A^{n+1}{x}_0+A^{n}B{u}_0+A^{n-1}B{u}_1+A^{n-2}B{u}_2+\dots +B{u}_n\end{array}$$ For square matrices that satisfy their own characteristic equation the Cayley-Hamilton theorem states that for $N\ge n$ we may express $A^N$ as a linear combination of the lower matrix powers of $A$: $$A^N=a_{0}I+a_{1}A+\dots +a_{n-1}{A}^{n-1}.$$ Therefore, the state $x_{n+1}$ can be rewritten as $$x_{n+1}=A^{n+1}{x}_0+A^{n-1}B(u_1+a_{n-1}{u}_0)+A^{n-2}B(u_2+a_{n-2}{u}_0)+\dots +B(u_n+a_0{u}_0)$$ which can be manipulated into the form $$x_{n+1}=A^{n+1}{x}_0+R\left[\begin{array}{c}{u}_n+a_0{u}_0\\ u_{n-1}+a_1{u}_0\\ u_1+a_{n-1}{u}_0\end{array}\right].$$ where $$R=\left[\begin{array}{cccc}B& AB& \dots & A^{n-1}B\end{array}\right]$$ is the controllability matrix.

The same substitution can be applied also for subsequent timesteps up-to infinity, changing only the particular form of the vector of inputs' linear combinations. This has two consequences:

• All states reachable in $N>n$ steps are also reachable in $n$ steps (with unlimited inputs).
• If $R$ is rank deficient, some directions in the state-space cannot be effected by the inputs and therefore the system is uncontrollable.