# Equivalence of controllability and reachability in discrete time systems

I am trying to prove that the statements;

1. $\Sigma_d$ is controllable,

2. $\Sigma_d$ is reachable,

3. The pair $(A,B)$ is controllable (in other words $<A|\ im\ B>=\mathcal{X}).$

are equivalent for discrete time systems.

I defined controllability as being able to get from an initial state $x_1$ to any other state $x_2$, reachability to get from the origin $0$ to any other state $x_2$ and null-controllability to get from an initial state $x_1$ to the origin $0$.

I see how being able to get from any state $x_1$ to any state $x_2$ (thus controllability) implies reachability as you can take the origin as $x_1$ and being able to reach any state $x_2$.

However i can't figure out how to proof it the other way around (that reachability implies conrollability).

Also i don't really understand how the last statement is different from the first statement.

Reaching from $x_1$ to $x_2$ in $k$ steps is equivalent to reaching from $0$ to $x_2 - A^k x_1$ in $k$ steps, which can be immediately seen from the solution of the difference equation. Since all the states are reachable from $0$, this implies controllability.
Null-controllability is equivalent to reachability if the system does not have finite modes, i.e. $0$ eigenvalues. If the system has an uncontrollable finite mode, this particular node will be $0$ in a finite time (more precisely at most $n$ steps, where $n$ is the system order), regardless of the input. Therefore null-controllability is equivalent to "all uncontrollable modes are finite".
Note: Not to be confused with stabilizability, which is "all uncontrollable modes are stable". This doesn't imply null-controllability since uncontrollable stable modes may be infinite, i.e. they cannot reach $0$ in a finite time. However, null-controllability implies stabilizability.