# Minimal time to reach s given state

I've got the following question from a test I took a while back:

Consider the discrete-time state-space realization:

$$x(t+1) = Ax(t)+Bu(t), \quad y(t) = Cx(t)$$

with

$$A =\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}, \quad B =\begin{bmatrix} 0 \\ 0 \\ 1 \\ \end{bmatrix}, \quad C =\begin{bmatrix} 1 & 0 & 0\\ \end{bmatrix}$$

and let $x(t,x_{0},u) : \mathbb{N} \rightarrow \mathbb{R^{3}}$ denote the state $x(t)$ of the state-space realization $(A,B,C)$ at time $t \in \mathbb{N}$ corresponding to initial state $x(0) = x_{0}$ and input function $u : \mathbb{N} \rightarrow \mathbb{R}$.

What is the minimal time $T \in \mathbb{N}$ for which there exists an input signal $u : \mathbb{N} \rightarrow \mathbb{R}$ such $\qquad$ $\quad$ that $x(T,0,u) = x_{f}$ with $x_{f} = \begin{bmatrix} 0 & 1 & 1\\ \end{bmatrix} ^{T}$?

I don't know what to do. It has something to with the reachability of the final state and maybe the reachability gramian. I do know that the controllability matrix has to be full rank, which it is or else the final state can't be reached. But other than that I'm clueless.

I would really appreciate any help/tips. Thanks very much in advance.

If the controllability matrix is full rank then it should always be possible to reach any desired state within $n$ steps, with $n$ the dimension of $x$/$A$ so 3. However it could of course be possible that the initial condition is chosen such that it would be possible to reach the desired state within fewer steps. For example if $x_0 = x_f$ then zero steps would be needed.

To see why it is possible to reach any desired state within $n$ steps, when the controllability matrix is full rank, one can write out these steps. For $n=3$ this yields

$$x_1 = A\,x_0 + B\,u_0,$$

$$x_2 = A\,x_1 + B\,u_1 = A^2\,x_0 + A\,B\,u_0 + B\,u_1,$$

\begin{align} x_3 = A\,x_2 + B\,u_2 &= A^3\,x_0 + A^2 B\,u_0 + A\,B\,u_1 + B\,u_2 \\ &= A^3\,x_0 + \underbrace{\begin{bmatrix}B & A\,B & A^2 B\end{bmatrix}}_{\mathcal{C}} \underbrace{\begin{bmatrix}u_2 \\ u_1 \\ u_0\end{bmatrix}}_{\vec{u}} \end{align}

The matrix $\mathcal{C}$ is just the controllability matrix and the inputs can be found with,

$$\vec{u} = \mathcal{C}^{-1} \left(x_3 - A^3 x_0\right).$$

So if $\mathcal{C}$ is invertible then an input sequence exists which can bring the system to any desired state. If $\mathcal{C}$ is square and full rank then it would also be invertible.

It can be noted that if $\mathcal{C}$ is not square, namely when the number of inputs is larges then one, then it might be possible to do it in less steps. Namely if $\mathcal{C}$ cutoff at a lower power of $A$ is already full rank. This matrix might not be square (width larger then $n$), in which case a (pseudo) right inverse could be used. This will give a solution which brings the system to the desired state while also minimizing $\|\vec{u}\|$ as well, since it has more degrees of freedom then $x$.