Prove the following statement for multiple Input system:
If $(A,B)$ is controllable then for any $x_0 \neq 0$ there exists a sequence $(u_0, u_1, \cdots, u_{n-1})$ such that span $\{x_0, \cdots, x_{n-1} \}= \mathbb{R}^n$ where $$ x_{k+1}=A x_k + B u_k $$
I do not know how to start the proof. I understand that $(A,B)$ are controllable if Rank$(\mathcal{C})=n$ where $\mathcal{C}$ is the controllablility matrix, but I don't know how to get a reach to the statement from this. Any hint?
Let $A$ be a matrix with $n$ rows and $m$ columns, where $m \ge n$. Then $\operatorname{rank}(A)=n$ if and only if there exist $n$ vectors in the domain space $\mathbb{R}^m$, such that their images form a basis of the target space $\mathbb{R}^n$.
$$ \operatorname{rank}(A)=n \quad \Leftrightarrow \quad \exists\{x_k \in \mathbb{R}^m\}_{k=1, \dots, n}\quad \text{ s.t.} \quad \operatorname{span}(Ax_1,\dots,Ax_n)=\mathbb{R}^n $$
Now consider a system
$$ x_{k+1}=A x_k + B u_k $$
with $n$ state variables and $m$ inputs. In this case the controllability matrix $$\mathcal{C} = \begin{bmatrix} B & AB & \dots A^{n-1}B \end{bmatrix}$$ has $n$ rows and $mn\ge n$ columns. Consider a set of $n $ vectors in the domain space $\mathbb{R}^{mn}$ of the controllability matrix $\mathcal{C}$ of the following form
$$ \tilde{u}_0 = \begin{bmatrix} u_0 \\ 0 \\ 0 \\\vdots \\ 0\end{bmatrix}, \quad \tilde{u}_1 = \begin{bmatrix} u_1 \\ u_0 \\ 0 \\\vdots \\ 0\end{bmatrix}, \quad \tilde{u}_2 = \begin{bmatrix} u_2 \\ u_1 \\ u_0 \\\vdots \\ 0\end{bmatrix}, \quad \tilde{u}_{n-1} = \begin{bmatrix} u_{n-1} \\ u_{n-2} \\ u_{n-3} \\\vdots \\ u_0\end{bmatrix}, $$
where $u_k \in \mathbb{R}^m, \; \tilde{u}_k \in \mathbb{R}^{mn}$, such that $\{\mathcal{C}\tilde{u}_0, \mathcal{C}\tilde{u}_1, \dots, \mathcal{C}\tilde{u}_{n-1} \}$ is the basis of the target space $\mathbb{R}^n$.
Note that
$$ \begin{aligned} &\mathcal{C}\tilde{u}_0 = Bu_0,\\ &\mathcal{C}\tilde{u}_1 = ABu_0 + Bu_1,\\ &\vdots \\ &\mathcal{C}\tilde{u}_{n-1} = A^{n-1}Bu_0 + \dots + ABu_{n-2}+Bu_{n-1}, \end{aligned} $$
and thus
$$ x_k= A^kx_0+\mathcal{C}\tilde{u}_{k-1}. $$
This leads us to
$$ \operatorname{span}(x_1, x_2 \dots, x_n) = \operatorname{span}(Ax_0+\mathcal{C}\tilde{u}_{0}, \; A^2x_0+\mathcal{C}\tilde{u}_{1}, \; \dots, \;A^nx_0+\mathcal{C}\tilde{u}_{n-1}) = $$
$$ =\operatorname{span}(\mathcal{C}\tilde{u}_0, \mathcal{C}\tilde{u}_1, \dots, \mathcal{C}\tilde{u}_{n-1})=\mathbb{R}^n $$
So there is always a sequence $\{u_0, u_1, \dots, u_{n-1} \}$ of inputs such that $\{x_1, x_2, \dots, x_n \}$ form a basis of $\mathbb{R}^n$. If we want the same from the sequence $\{x_0, x_1, \dots, x_{n-1} \}$ then we have to assume $x_0 \ne 0$.
This is not a completely rigorous proof, but it has an idea.