This clearly transforms polynomials of degree $2$ to homogeneous quadratic polynomials. We can write $f_i({{\mathbf}{x}})={{\mathbf}{x}}^{\operatorname{T}}\,H_i\,{{\mathbf}{x}}+L_i\,{{\mathbf}{x}}+c_i$ with $H_i\in{{\mathbb}{K}}^{n\times n}$, $L_i\in{{\mathbb}{K}}^n$ and $c_i\in{{\mathbb}{K}}$, then $f_i(A{{\mathbf}{x}}+b)=(A{{\mathbf}{x}}+b)^{\operatorname{T}}\,H_i\,(A{{\mathbf}{x}}+b)+L_i\,(A{{\mathbf}{x}}+b)+c_i$ and its homogenization is $(A{{\mathbf}{x}}+bx_0)^{\operatorname{T}}\,H_i\,(A{{\mathbf}{x}}+bx_0)+L_i\,(A{{\mathbf}{x}}+bx_0)\,x_0+c_i\,x_0^2
  =f^{\star}_i(A'{{\mathbf}{x}}^{\star})$, with ${{\mathbf}{x}}^{\star}=(x_0,x_1,\ldots,x_n)^{\operatorname{T}}$. If $(A,b) \in
  \operatorname{GL}_{n}({{\mathbb}{K}}) \times {{\mathbb}{K}}^n$ is an affine transformation solution on the inhomogeneous instance then $A^{\prime}={\left(\begin{smallmatrix}1 &{\mathbf}{0}\\
      b &A\end{smallmatrix}\right)}$ is a solution for the homogenized instance. Conversely, a solution $A' \in \operatorname{GL}_{n+1}({{\mathbb}{K}})$ of the homogeneous problem must stabilize the homogenization variable $x_0$ in order to be a solution of the inhomogeneous problem. This is forced by adding $f_0=x_0^2$ and $g_0=x_0^2$ and setting $C'=A'/a_{0,0}'$, with $a_{0,0}'=\pm 1$. One can see that $C'$ is of the form ${\left(\begin{smallmatrix}1 &{\mathbf}{0}\\d &C\end{smallmatrix}\right)}$, and $(C,d)\in \operatorname{GL}_n({{\mathbb}{K}}) \times {{\mathbb}{K}}^n$ is a solution for $({{\mathbf}{f}},{{\mathbf}{g}})$.

#### Redundant Variables {#par:variables}

As a first preliminary natural manipulation, we first want to eliminate – if any – *redundant variables* from the instances considered. Thanks to [@Carlini05reducingthe] (and reformulated in [@Kayal2011]), this task can be done in randomized polynomial time:

([@Carlini05reducingthe; @Kayal2011]) \[prop:carl\] Let $f \in {{\mathbb}{K}}[x_1\ldots,x_n]$ be a polynomial. We shall say that $f$ has $s$ *essential variables* if $\exists \,M \in \operatorname{GL}_n({{\mathbb}{K}})$ such that $f(M
  {{\mathbf}{x}})$ depends only on the first $s$ variables $x_1,\ldots,x_s$. The remaining $n-s$ 