Let $A\in\mathbb{R}^{n \times n}$, $B\in\mathbb{R}^{n\times m}$ and $I$ be the $n\times n$ identity matrix. Show that for any polynomial $n$-vector $X_0(s)$ with elements of degree $n-1$ or less, we can always find polynomial vectors $X(s)$ and $U(s)$ such that $(sI-A)X(s)-BU(s)=X_0(s)$, if and only if $$\text{rank}[sI-A\quad B]=n\quad\forall s\in\mathbb{C}$$ i.e., $\{A,B\}$ is controllable.
Thanks for any hint.
On
For the forward implication, we prove the contrapositive. Suppose for some $\lambda$ (necessarily an eigenvalue of $A$) there is some $y \neq 0$ such that $y^T \begin{bmatrix} \lambda I -A & B \end{bmatrix} = 0$.
Now choose $X_0(s) = y$. Note that $y^T ((\lambda I-A) X(\lambda) -B U(\lambda)) = 0$ but $y^T X_o(\lambda) = \|y\|^2$.
The following was motivated by Kwin van der Veen's answer (and George C's comments) but expressed in a manner that I can more easily understand:
For the reverse implication, first note that if we can show that for any $y \in \mathbb{R}^n$, there exists polynomials $U, X$ such that $y = (sI-A) X(s) - B U(s)$, then clearly $s^ky = (sI-A) s^kX(s) - B s^kU(s)$ and hence for any polynomial $X_0$, we can find some polynomials $U,X$ such that $X_0 = (sI-A) X(s) - B U(s)$. In particular, we need only consider $X_0$ of the form $y \in \mathbb{R}^n$.
If the rank condition holds, then $A,B$ is cc. and so there is some sequence $\upsilon_k \in \mathbb{R}^m$ that steers the system $\xi_{k+1}= A \xi_k + B \upsilon_k$ from $\xi_0 = 0$ to $\xi_n = -y$.
If we take $\upsilon_k = 0$ for $k\ge n$ and $|z| > \sigma(A)$ the $z$ transform gives $z\hat{\xi} = A \hat{\xi}+B \hat{\upsilon}$, with $\hat{\xi}(z) = {\xi_1 \over z} + \cdots + {\xi_{n-1} \over z^{n-1}} + {-y \over z^n} + \cdots$ (recall that $\xi_0 = 0$), and similarly for $\hat{\upsilon}$.
Multiplying by $z^{n-1}$ gives $z^n\hat{\xi} = z^{n-1}A \hat{\xi}+z^{n-1}B \hat{\upsilon}$, and equating the terms with non negative powers of $z$ gives the equality $\xi_1 z^{n-1}+ \cdots + \xi_{n-1} z -y = A(\xi_1 z^{n-2}+ \cdots + \xi_{n-1} ) + B (\upsilon_0z^{n-1} + {\upsilon}_1 z^{n-2}+ \cdots + \upsilon_{n-1} )$.
Finally, letting $X(s)= \xi_1 s^{n-2}+ \cdots + \xi_{n-1} $, $U(s) = \upsilon_0s^{n-1} + {\upsilon}_1 s^{n-2}+ \cdots + \upsilon_{n-1} $ gives $(sI-A) X(s)-B U(s) = y$ as desired.
Given that $X_0(s)$, $X(s)$ and $U(s)$ are polynomials, by collecting terms containing the same power of $s$ one can write the initial equation also as
\begin{align} - \begin{bmatrix} A & B \end{bmatrix} y_0 &= v_0, \tag{1a} \\ \begin{bmatrix} I & 0 \end{bmatrix} y_{i-1} - \begin{bmatrix} A & B \end{bmatrix} y_{i} &= v_i,\ \forall\,i=1,\dots,k, \tag{1b} \\ \begin{bmatrix} I & 0 \end{bmatrix} y_k &= 0, \tag{1c} \end{align}
with $k \leq n-1$, $v_i \in\mathbb{R}^n$, $y_i \in\mathbb{R}^{n+m}$ and
\begin{align} X_0(s) &= \sum_{i=0}^k v_i\,s^i, \tag{2a} \\ \begin{bmatrix} X(s) \\ U(s) \end{bmatrix} &= \sum_{i=0}^k y_i\,s^i. \tag{2b} \end{align}
From now on I will use $y^x_i$ and $y^u_i$ to denote the components of $y_i$ associated with $X(s)$ and $U(s)$ respectively. Solving $(1c)$ yields $y^x_k = 0$, substituting this in $(1b)$ and solving it yields the following expression for each $y^x_{i-1}$
$$ y^x_{i-1} = v_i + A\,y^x_i + B\,y^u_i,\ \forall\,i=1,\dots,k, \tag{3} $$
where initially each $y^u_i$ can be chosen to be anything. However, these choices get constrained when one also wants to satisfy $(1a)$. Namely, when substituting each expression for $y^x_i$ in $(1a)$ yields
$$ \sum_{i=0}^k A^i B\,y^u_i = \underbrace{-\sum_{i=0}^k A^i v_i}_{r}, \tag{4} $$
which is equivalent to driving the discrete time system associated with $(A,B)$ from the origin to $r$ in $k+1$ time steps. It can be noted that if the polynomial order of $X_0(s)$ has $k < n-1$ (i.e. $v_k \neq 0$ and $v_i = 0,\ \forall\,i > k$) it might not be possible to drive such system to $r$ in $k+1$ steps. However, iff $(A,B)$ is controllable it should always be possible to drive the system to $r$ in $n$ steps, thus $k = n-1$.