Then the first row of ${{\textnormal{adj}}}(F)$ will be the first $n$ entries of the first row of ${\bm{v}}G^{-1}$. High-order $X$-adic lifting [@storjohann_high-order_2003 Algorithm 5] using the modulus $X=(x-1)^{\lceil
D/n \rceil}$ will compute ${\bm{v}}G^{-1}$ in $O\big(n^{\omega}\,
{{\mathsf{M}}}(\lceil D/n \rceil) \,(\log \lceil D/n \rceil)\big)$ operations in ${{\mathsf{K}}}$ [@storjohann_high-order_2003 Corollary 16]. Since $D \geq n$ this cost estimate remains valid if we replace $\lceil D/n \rceil$ with $D/n$. Finally, from the super-linearity assumption on ${{\mathsf{M}}}(\cdot)$ we have $M(D/n) \leq (1/n) {{\mathsf{M}}}(D)$, thus matching our target cost.

Now suppose $D < n$. In this case we can not directly appeal to the partial linearisation technique since the resulting $O(n^{\omega} \lceil D/n\rceil)$ may be asymptotically larger than our target cost. But $D < n$ means that $F$ has — possibly many — columns of degree 0; since $F$ is in Popov form, such columns have a 1 on the matrix’s diagonal and are 0 on the remaining entries. The following describes how to essentially ignore those columns. $D$ is then greater than or equal to the number of remaining columns, thus effectuating the gain from the partial linearisation.

If $n-k$ is the number of such columns in $F$ that means we can find a permutation 