Let $P \in k[x]^{m \times n}$ be a polynomial matrix in (row) Popov form (see section 2.4 here) of degree (maximum of the degrees of its entries) $d$. Now let $A \in k[x]^{\ell \times n}$ be another matrix. Consider the matrix $M = (P^T A^T) \in k[x]^{m+\ell \times n}$.
Then by using division with remainder iteratively and that $P$ is in Popov form, we are able to reduce the degree of $A^T$ inside $M$ by applying unimodular row operations on $M$ while not touching $P^T$. But doing so, we need to use $O(n^3d)$ operations in $k$.
But I suspect that there is an algorithm to compute $LM = (P^TC^T)$ with $\deg(C) < \deg(P)$ only with $O(n^\omega d)$ where $\omega$ is the matrix multiplication constant. DO you know one?
So I would like to fix $P^T$ and only use it to reduce the degree of $A^T$ inside of $M$.
To do so, we may use the asymptotically fast algorithms for computing
- Popov form of a given matrix of degree $d$
- a reduced left equivalent of a matrix of degree $d$ (which is weaker than Popov form)
- a basis of the row space of a given rectangular matrix of degree $d$
- a basis of the row kernel of a given matrix of degree $d$
- the solution of a rational system $\lambda M = b$ for given matrix $M \in k[x]^{n \times n}$ of degree $d$ and $b \in k[x]^{1 \times n}$
which all have a running time of $O(n^\omega d)$ where we neglect logarithmic terms in $n$ as well as $d$.
I am grateful for any hint or comment with regards to my question. Thank you!