Systems theory: show necessary condition for "reachable system" Do not worry if you are new to systems theory, I will define all relevant terminology below, the mathematical problem should be clear!

Suppose the following system is given
\begin{align}
\dot{x} = Ax,\quad x\in \mathbb{R}^{n}
\end{align}
where $A$ is a constant. You are asked to add one input $u\in \mathbb{R}$ to make the system reachable, i.e. you design $b\in \mathbb{R}^{n}$ such that
\begin{align}
\dot{x} = Ax + bu
\end{align}
is reachable.
a) Show that a necessary condition for such $b$ to exist is that $\text{Rank}(A)\geq n-1$.

So, what we have is a so called time invariant system since $A$ is constant ($n$-by-$n$) matrix. Moreover, if the system $\dot{x}=Ax+bu$ is reachable then systems theory tells us that the reachability matrix
\begin{align}
\Gamma = \begin{bmatrix}b,Ab,A^{2}b,\dots,A^{n-1}b\end{bmatrix}
\end{align}
is of full rank. Also $\Gamma$ is a $n$-by-$n$ matrix. Now, correct me if I am wrong, what we want to show is that if the system is reachable, i.e. $\text{Rank}(\Gamma)=n$, then this implies ($\implies$) that $\text{Rank}(A)\geq n-1$? Or is the implication the other way around ...?
Furthermore, how may I proceed from this to showing that $A$ has at least rank of $n-1$? My linear algebra is weak, and I do not know what to do!
 A: You have correctly interpreted the question. Indeed, we want to show that if the system is reachable (AKA controllable), then the rank of $A$ is at least $n-1$. Actually, I would suggest that it is (slightly) easier to do this problem by using the "Hautus test" instead of the reachability matrix. The Hautus test says that a system is reachable iff the matrix $[A - \lambda I  \quad b]$ has full rank for all $\lambda \in \Bbb C$. For our purposes, it suffices to consider what this means for $\lambda = 0$.
However, let's stick to the reachability matrix criterion. We can prove this by contradiction: suppose that the rank of $A$ is not at least $n-1$.
Recall that the rank of a matrix $M$ is equal to the dimension of its column space, which is equivalently the dimension of the span of its columns. The rank of $\Gamma$ is the dimension of the span of its columns, but note that each of the columns $Ab,A^2b,\dots,A^{n-1}b$ is of the form $Ax$ for some vector $x$. That is, all of these vectors are elements of the columns space of $A$. Let $\{x_1,\dots,x_{k}\}$ be a basis for the span of the columns $Ab,A^2b,\dots,A^{n-1}b$; this span is a subspace of the column space of $A$, which means that $k$ (the dimension of the span) is at most $n-2$.
We see that the set $\{b,x_1,\dots,x_k\}$ gives us a set that spans the column space of $\Gamma$. However, this set has at most $(n-2) + 1 = n-1$ columns, so the column space of $\Gamma$ has dimension at most $n-1$. So, the dimension of this space (rank of $\Gamma$) cannot be equal to $n$ after all.

This whole proof can be made much quicker if we can appeal to the fact that for any matrix $M$, we have
$$
\operatorname{rank}([M \mid b]) \leq \operatorname{rank}(M) + 1.
$$
