This post will discuss the basic concepts of reachability and controllability in the context of a discrete-time linear time-invariant dynamical system. For more information, see these notes and these notes. $\newcommand{\abs}[1]{| #1 |} \newcommand{\ind}{\mathbf{1}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\ip}[2]{\langle #1, #2 \rangle} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\T}{\mathsf{T}} \newcommand{\Proj}{\mathcal{P}} \newcommand{\Tr}{\mathrm{Tr}} \newcommand{\A}{\mathcal{A}}$

For this post, fix a discrete-time LTI system $$\begin{align} x_{k+1} = A x_k + B u_k \:, \label{eq:lti_system} \end{align}$$ with $A \in \R^{n \times n}$ and $B \in \R^{n \times m}$. For $N \geq 1$, let $G_N : \R^n \times \R^{m \times N} \longrightarrow \R^n$ denote the map $G_N(x_0, u) = x_{N-1}$, where $x_{N-1}$ is the result of $\eqref{eq:lti_system}$ with starting state $x_0$ and input $u_0, u_1, ..., u_{N-1}$. An explicit formula for $G_N(x_0, u)$ is $$\begin{align} G_N(x_0, u) = A^N x_0 + \underbrace{\begin{bmatrix} B & A B & A^2 B & \cdots & A^{N-1} B \end{bmatrix}}_{C_N} \begin{bmatrix} u_{N-1} \\ u_{N-2} \\ u_{N-2} \\ \vdots \\ u_0 \end{bmatrix} \:. \end{align}$$

Definition 1: A given state $x \in \R^n$ is reachable for system $\eqref{eq:lti_system}$ if there exists a $N \geq 1$ and a $u \in \R^{m \times N}$ such that $x = G_N(0, u)$.

Definition 2: A given state $x \in \R^n$ is controllable for the system $\eqref{eq:lti_system}$ if there exists a $N \geq 1$ and $u \in \R^{m \times N}$ such that $0 = G_N(x, u)$.

Note that if every $x \in \R^n$ is reachable (resp. controllable), then we say that the pair $(A, B)$ is reachable (resp. controllable).

Proposition 3: For every $N \geq n$, we have $\mathcal{R}(C_N) = \mathcal{R}(C_n)$.

Proof: The base case is trivial. Now suppose that $\mathcal{R}(C_n) = \mathcal{R}(C_{n+1}) = ... = \mathcal{R}(C_{n+k})$. Clearly $\mathcal{R}(C_{n+k}) \subseteq \mathcal{R}(C_{n+k+1})$. On the other hand, by the Cayley-Hamilton theorem, there exists coefficients $\{\alpha_i\}_{i=0}^{n-1}$ such that $$A^n = a_{n-1} A^{n-1} + a_{n-2} A^{n-2} + ... + a_1 A + a_0 \:.$$ Hence, if $x \in \mathcal{R}(C_{n+k+1})$, then $$\begin{align*} x &= c_{n+k} A^{n+k} B + \sum_{j=0}^{n+k-1} c_j A^j B \\ &= c_{n+k} ( a_{n-1} A^{n-1} + a_{n-2} A^{n-2} + ... + a_1 A + a_0 ) A^k B + \sum_{j=0}^{n+k-1} c_j A^j B \\ &= C_{n+k} \widehat{u} \:. \end{align*}$$ The last equality states that $x \in \mathcal{R}(C_{n+k})$. The claim now follows. $\square$

Proposition 4: If $x$ is reachable, then there exists a $u \in \R^{m \times n}$ such that $x = G_n(0, u)$.

Proof: If $x$ is reachable, then there exists an $N \geq 1$ such that $x \in \mathcal{R}(C_N)$. If $N \leq n$, since $\mathcal{R}(C_N) \subseteq \mathcal{R}(C_n)$, the claim follows immediately. On the other hand, if $N > n$, we have that $\mathcal{R}(C_N) = \mathcal{R}(C_n)$ by the last proposition, and hence $x \in \mathcal{R}(C_n)$. $\square$

An immediate corollary of Proposition 4 is that $(A, B)$ is reachable if and only if $\mathcal{R}(C_n) = \R^n$.

Proposition 5: If the pair $(A, B)$ is reachable, then it is controllable.

Proof: Fix an $x \in \R^n$. By the previous proposition, there exists a $u$ such that $x = C_n u$, which implies that $- A^n x \in \mathcal{R}( A^n C_n)$. But we can see that $\mathcal{R}( A^n C_n ) \subseteq \mathcal{R}( C_{2n} ) = \mathcal{R}(C_n)$, where the last equality holds from Proposition 3. But this means that $0 = G_n(x, u)$ for some $u$ as desired. $\square$

What about the converse? If $(A, B)$ is controllable, is it reachable? In continuous-time, the answer is yes. In discrete-time, the answer is maybe.

Proposition 6: $\mathcal{R}(A^n) \subseteq \mathcal{R}(C_n)$ if and only if $(A, B)$ is controllable.

Proof: $(\Longrightarrow)$. Let $N \geq n$. Fix any $x \in \R^n$, and consider $$\begin{align} 0 = A^N x + C_N u \Longleftrightarrow -A^N x = C_N u \:. \label{eq:p6a} \end{align}$$ Observe that $-A^N x \in \mathcal{R}(A^N) = \mathcal{R}(A^n)$ (Cayley-Hamilton again). On the other hand, $\mathcal{R}(C_N) = \mathcal{R}(C_n)$. Hence if $\mathcal{R}(A^n) \subseteq \mathcal{R}(C_n)$, then we will always be abel to find such a $u$ that satisfies $\eqref{eq:p6a}$.

The $(\Longleftarrow)$ direction is argued similarly. Details omitted. $\square$

An immediate corollary of Proposition 6 is a partial converse to Proposition 5: if $(A, B)$ is controllable and $A$ is invertible, then $(A, B)$ is reachable.

Definition 7: The reachability grammian of $\eqref{eq:lti_system}$ is the $n \times n$ positive semi-definite matrix $W_c = C_nC_n^*$.

The following is a basic linear algebra fact.

Fact 8: For any matrix $M$, we have $\mathcal{R}(M) = \mathcal{R}(MM^*)$.

Proof: The $\supseteq$ direction is trivial. The $\subseteq$ direction is a consequence of the fact that $\mathcal{N}(M)^{\perp} = \mathcal{R}(M^*)$. $\square$

We now consider the case when $A$ is a Schur matrix (i.e. $\eqref{eq:lti_system}$ is stable). Then the grammiam $W_\infty := \sum_{k=0}^{\infty} A^k BB^* (A^k)^*$ exists. The following proposition is a basic fact from Lyapunov theory (see e.g. these notes).

Proposition 9: Let $A$ be Schur. Then $P = W_\infty$ is the unique solution to the Lyapunov equation $A P A^* - P = -BB^*$.

The previous fact and proposition give us a recipe for testing if a system $(A, B)$ is reachable when $A$ is stable. Simply (a) solve the Lyapunov equation $A P A^* - P = - BB^*$, and check if the result is positive definite.