# minimal time to reach given state. number of time steps unclear.

Consider the discrete-time state-space realization

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

with

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

and let $x(t,x_0,u) : \mathbb N \to \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 \to \mathbb R$ such that $x(T,0,u)=x_f$ with $x_f=\begin{bmatrix} 1 & 1& 0 \end{bmatrix}^T$.

My approach:

The following sequence must be filled in until the state $x_i$ matches $x_f$:

$x_1 = Ax_0+Bu_0$

$x_2 = Ax_1+Bu_1=A^2x_0+ABu_0+Bu_1$

$x_3 = Ax_2+Bu_2=A^3x_0+A^2Bu_0+ABu_1+Bu_2$

$u_{1}, u_2$ and $u_3$ get determined using

$\begin{bmatrix}u_2 \\ u_1 \\ u_0 \end{bmatrix} = \begin{bmatrix} B & AB & A^2B \end{bmatrix}^{-1}(x_f-A^3x_0) = \begin{bmatrix} -1&1&-\frac{1}{2} \\ 1 & 0 & -\frac{1}{2}\\ 0& 0& \frac{1}{2}\end{bmatrix}\begin{bmatrix}1 \\ 1\\ 0 \end{bmatrix}=\begin{bmatrix}0\\1\\0 \end{bmatrix}$

And thus we get:

$x_1 = A \cdot 0 + B \cdot 0 = 0$

$x_2 = A^2 \cdot 0 + A \cdot B \cdot 0 +\begin{bmatrix} 0\\1\\0 \end{bmatrix} \cdot 1 = \begin{bmatrix} 0\\1\\0 \end{bmatrix}$

$x_3 = A^3 \cdot 0 + A^2 \cdot B \cdot 0 + \begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 2 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0\\1\\0 \end{bmatrix} \cdot 1 + \begin{bmatrix} 0\\1\\0 \end{bmatrix} \cdot 0 = \begin{bmatrix}1\\1\\0 \end{bmatrix}=x_f$

It is unclear to me how many time steps this took?

$x_3$ reached the correct state, so $3$ steps or only $2$ because from $x_1$ to $x_2$ is $1$ step and from $x_2$ to $x_3$ is another. But $u_2$ did not get used in the final step because it is $0$ so $2$ steps or $1$?

• I assume that $x_0 = 0$? – Kwin van der Veen Aug 6 '18 at 20:26
• Yes, $x_0$ was indeed zero, I forgot to mention that. My apologies. – user463102 Aug 6 '18 at 22:17

The smallest number of time steps is the smallest $n$ such that $x_f - A^n\,x_0$ lies in the span of $\begin{bmatrix}B & A\,B & \cdots A^{n-1} B\end{bmatrix}$. Namely this implies that there exits a vector $u$ (containing the inputs) such that
$$x_f - A^n\,x_0 = \begin{bmatrix}B & A\,B & \cdots A^{n-1} B\end{bmatrix} v.$$
For your system, assuming $x_0 = 0$, the $n$ which satisfies this is two. If the top element of $v$ is zero just means the not actuated system dynamics after the first input will bring the state to $x_f$ after one more time step. But without that additional (not actuated) time step the system will not end up in $x_f$, so the number of time steps is still $n$.