combinations of the rows of $A$ are solutions. We recall the relevant definitions and lemmas in \[sec:preliminaries\].

We will call such a matrix $A$ a *solution basis*. In the complexities we report here, we cannot afford to compute $A$ explicitly. For example, if all $g_i = x^d$, the number of field elements required to explicitly write down all of the entries of $A$ could be $\Omega(n^2d)$. Instead, we remark that $A$ is completely given by the problem instance as well as the first column of $A$, containing the $\lambda$ polynomials.[^3] Our algorithms will therefore represent $A$ row-wise using the following compact representation.

For a given instance of \[prob:sim\_pade\_basis\], a *solution specification* is a tuple $({\bm{\lambda}},{\bm{\delta}}) \in
{{\mathsf{K}}}[x]^{k \times 1} \times {\mathbb Z\xspace}_{<0}^k$ such that the *completion* of ${\bm{\lambda}}$ is a solution basis, and where ${\bm{\delta}}$ are the $(-{\bm{N}})$-degrees of the rows of $A$.

The *completion* of ${\bm{\lambda}} = (\lambda_1,\ldots,\lambda_k){^\top}$ is the matrix $$\begin{bmatrix}
    \lambda_1 & {{\textnormal{rem}}}(\lambda_1 S_1,\ g_1) & \ldots & {{\textnormal{rem}}}(\lambda_1 S_n,\ g_n) \\
    \vdots & & \ddots & \vdots \\
    \lambda_k & {{\textnormal{rem}}}(\lambda_k S_1,\ g_1) & \ldots & {{\textnormal{rem}}}(\lambda_k S_n,\ g_n) \\
  \end{bmatrix}
  \ .$$

Note that ${\bm{\delta}}$ will consist of only negative numbers, since any solution ${\bm{v}}$ 