${{\mathsf{M}}}(\cdot)$ that is a multiplication time for ${{\mathsf{K}}}[x]$ [@von_zur_gathen_modern_2012 Definition 8.26]. Then two $n\times n$ matrices over ${{\mathsf{K}}}$ can be multiplied in $O(n^{\omega})$ operations in ${{\mathsf{K}}}$, and two polynomials in ${{\mathsf{K}}}[x]$ of degree strictly less than $d$ can be multiplied in ${{\mathsf{M}}}(d)$ operations in ${{\mathsf{K}}}$. The best known algorithms allow $\omega < 2.38$ [@coppersmith_matrix_1990; @LeGall14], and we can always take ${{\mathsf{M}}}(d) \in O(n (\log n) (\operatorname{loglog}n))$ [@CantorKaltofen].

In this paper we assume that $\omega > 2$, and that ${{\mathsf{M}}}(d)$ is super-linear while ${{\mathsf{M}}}(d) \in O(d^{\omega-1})$. The assumption ${{\mathsf{M}}}(d) \in O(d^{\omega-1})$ simply stipulates that if fast matrix multiplication techiques are used then fast polynomial multiplication should be used also: for example, $n \, {{\mathsf{M}}}(nd) \in O(n^{\omega} \, {{\mathsf{M}}}(d))$.

Preliminaries {#sec:preliminaries}
=============

Here we gather together some definitions and results regarding row reduced bases, minimal approximant basis, and their shifted variants. For a matrix $A$ we denote by $A_{i,j}$ the entry in row $i$ and column $j$. For a matrix $A$ over ${{\mathsf{K}}}[x]$ we denote by ${{\textnormal{Row}}}(A)$ the ${{\mathsf{K}}}[x]$-linear row space of $A$.

Degrees and shifted degrees
---------------------------

The degree of a nonzero vector ${\bm{v}} \in {{\mathsf{K}}}[x]^{1 \times m}$ or matrix $A \in {{\mathsf{K}}}[x]^{n\times m}$ is denoted by $\deg {\bm{v}}$ or $\deg 