# finding the input sequence of a discrete-time dynamical system

I am studying Dynamical Systems, actually linear systems and I came across the following question:

Consider the following discrete-time dynamical system:

$x_{i+1}= \left( \begin{array}{ccc} 2 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{array} \right) x_i + \left( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ 0 & 2 \end{array} \right) u_i$ , $i \geq 0$, $y_i= \left( \begin{array}{ccc} 0& 1 &-1\end{array} \right) x_i$.

a)Is the system reachable?

b)Is the system observable?

c)Is the system controllable?

d)The system starts at the origin. We want to take it to the state $x_f = \left( \begin{array}{ccc} 2 & 2 & 2\end{array} \right)^T$. Can we do this in a single step?

e)Now, let the system start at $x_0 = \left( \begin{array}{ccc} 2 & 2 & 2\end{array} \right)^T$. Find an input sequence that take it back to the origin.

I know how to solve a), b),c) but I need some help on d) and e). Is there any systematic way to approach d) and e) or any place where I could read about this types of questions?

d) In one step with $x_0 = 0$ you have $x_1 = B u_0$, so you can only reach the image of $B$ i.e.

$$\operatorname{im} B = \operatorname{span} \left(\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}^\top,\begin{bmatrix} 0 & 1 & 2 \end{bmatrix}^\top \right) \\ = \{\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}^\top a + \begin{bmatrix} 0 & 1 & 2 \end{bmatrix}^\top b\ |\ a,b \in \mathbb{R} \}$$

So no we cannot reach $x_f = \begin{bmatrix} 2 & 2 & 2 \end{bmatrix}^\top$ since this is not in the image of B. There exists no $a$ and $b$ such that we can create the vector $x_f$ in 1 step.

Lets see if we can do it in 2 steps, $x_2 = A x_1 + B u_1 = A (A x_0 + B u_0) + B u_1 = A^2 x_0 + AB u_0 + B u_1 = AB u_0 + B u_1$, (remember that $A^2 x_0$ dissappears since $x_0 = 0$). So now we can reach the states given by $\operatorname{im} \begin{bmatrix} B & AB\end{bmatrix}$ which gives three elementary vectors $\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}^\top$, $\begin{bmatrix} 0 & 1 & 0 \end{bmatrix}^\top$, $\begin{bmatrix} 0 & 0 & 1 \end{bmatrix}^\top$. Hence we can reach $x_f$ in two steps now all we need to do is find $u_0$ and $u_1$.

Now there are multiple solutions for $u_0$ and $u_1$ so there is no decisive manner on how to compute them, you can just 'try' which might give you the vectors $u_0 = \begin{bmatrix} 1 & 1 \end{bmatrix}^\top$ and $u_1 = \begin{bmatrix} 0 & -1 \end{bmatrix}$ or you can also use the Moore–Penrose pseudoinverse of $R_t = \begin{bmatrix} B & AB \end{bmatrix}$. Note that this is only valid when you start from $x_0 = 0$. Let $\bar{u}$ be the stacked input vectors, $\bar{u} = R_t^\top (R_t R_t^\top)^{-1} x_f$. For your exercise you will obtain that $\bar{u} = \begin{bmatrix} u_1 & u_0 \end{bmatrix}^\top = \begin{bmatrix} 0.4 & -1 & 0.8 & 1 \end{bmatrix}^\top$.

e) Now $x_0 = \begin{bmatrix} 2 & 2 & 2 \end{bmatrix}^\top \neq 0$. Now you can compute what the influence of $x_0$ is by $A^2 x_0 = \begin{bmatrix} 8 & 8 & 8 \end{bmatrix}^\top$ now you can use the same technique as in d) to steer $ABu_0 + B u_1$ to $\begin{bmatrix} -8 & -8 & -8 \end{bmatrix}^\top$ as such making the result of $A^2x_0 + ABu_0 + B u_1$ to be $\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}$.

You can use the solution the the equation. Observe that if $x_{i+1} = A x_i + B u_i$, then

\begin{align} 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 \\ &\vdots \\ x_k &= A x_{k-1} + B u_{k-1} = A^k x_0 + B u_{k-1} + AB u_{k-2} + \dots + A^{k-1}B u_0 \\ x_k &= A^k x_0 + \begin{bmatrix}B & AB & \dots & A^{k-1} B \end{bmatrix} \begin{bmatrix}u_{k-1} \\ u_{k-2} \\ \vdots \\ u_0 \end{bmatrix} \end{align}

Actually, this is a proof of reachability condition. Now you can plug in $x_0$ and $x_f$ and solve input vector.

You can try for different values of $k$ to see how many steps are required to reach the desired state. Note that you do not need to check for $k > n$ (where $n$ is the system degree) because of the Cayley-Hamilton Theorem. If you cannot reach the desired state in $n$ steps, then you cannot reach it at all.