Let $M(x)$ be an $m$ by $n$ matrix with entries in $\mathbb{C}[x]$. Suppose that for all $x\in \mathbb{C}$ the rank of $M(x)$ is constant and equal to $r<n$. Therefore, for any $x\_0\in \mathbb{C}$ we can find a full-rank $N\in \mathbb{C}^{n,n-r}$ such that
$$
M(x\_0)N=0.
$$
Question: is it possible to find an $n$ by $n-r$ matrix $N(x)$ *with entries in $\mathbb{C}[x]$* such that
$$
M(x)N(x)=0
$$
and $N(x)$ is full-rank for all $x\in \mathbb{C}$? If yes, is there a constructive algorithm? If no, what are the obstructions? The question is interesting to me even under the restriction that $M(x)$ is linear in $x$.


Here's an example of a matrix for which I'm failing to find such a $N(x)$ ($m=4, n=6, r=4$)
$$
\left(
\begin{array}{cccccc}
 0 & 0 & 1 & 1 & 0 & 0 \\
 0 & 0 & 0 & 0 & 0 & 2 \\
 2 (x+2) & 4 (x-3) & 2 (8-x) & 0 & 0 & 0 \\
 -8 & 0 & -4 & 4 (x-3) & 2 (6-x) & 0 \\
\end{array}
\right)
$$



Global polynomial basis for the kernel of a matrix polynomial
Yes, and there is a constructive algorithm. Put $M$ into Smith normal form:
$ PMQ = D$ for invertible $P$ and $Q$ and diagonal $D$. Since $M(x\_0)$ is full rank for all $x\_0$, the same is true for $D$, and thus $D$ is of the form
$$ D = \begin{bmatrix} c\_1 & 0 & \cdots & 0 & 0 & \cdots &0\\
0 & c\_2 & \cdots & 0 & 0 & \cdots & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & &\vdots\\
0 & 0 & \cdots & c\_r& 0 & \cdots & 0\\
0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\
\vdots & \vdots & &\vdots & \vdots & & \vdots\end{bmatrix}$$
where $c\_1, \ldots, c\_r$ are in $\mathbb C$.
Hence, the kernel of $D$ is the span of the last $n-r$ standard basis vectors,
and thus the kernel of $M$ is the span of the last $n-r$ columns of $Q$. These columns form a full rank matrix in any desired sense since $Q$ is invertible over $\mathbb C[x]$.


