4
$\begingroup$

Typically computing resultnt of $n+1$ different $n+1$-variate homogeneous polynomials takes $O(poly(\prod_{i=1}^{d_{i}}))$ time where $d_i$ is degree of $i$th polynomial. In certain cases the polynomial can be compactly represented compact product forms.

Given $2n$ homogeneous polynomials in $2n$ variables $$f_j(x_1,\dots,x_n,y_j)=\prod_{i\in\mathcal T_j}(x_i-y_j)$$ $$g_i(x_i,y_1,\dots,y_n)=\prod_{j\in\mathcal U_i}(x_i-y_j)$$ where $\mathcal T_j,\mathcal U_i$ are subsets of $\{1,\dots,n\}$ expressing the resultant for all the $f_j$'s and the resultant for all the $f_j,g_i$'s as determinant of Macaulay matrices directly takes exponential time for both. Since the polynomials are structured is there a closed form for the two resultants or at least can the latter resultant of both $f_j,g_i$ be computable by a determinant of polynomial size?

$\endgroup$

1 Answer 1

1
$\begingroup$

Too long for a comment so I am posting this as an answer.

It would help if you said precisely what notion of resultant you are using and which variables are being eliminated. There are at least two, off course closely related, notions of resultants.

If $f_1,\ldots,f_{n+1}$ are $n+1$ non-necessarily homogeneous polynomials in $n$ variables $x_1,\ldots,x_n$, then one can form the nonhomogenous resultant ${\rm res}(f_1,\ldots,f_{n+1})$ which is a polynomial in the coefficients of the $f$'s and where the variables $x_1,\ldots,x_n$ have been eliminated.

If $F_1,\ldots,F_{n+1}$ are $n+1$ homogeneous polynomials in $n+1$ variables $x_1,\ldots,x_{n+1}$, then one can form the homogeneous resultant ${\rm Res}(F_1,\ldots,F_{n+1})$ which is a polynomial in the coefficients of the forms $F$ and where $x_1,\ldots,x_{n+1}$ have been eliminated.

I could not figure out from the question which notion you are using.

In any case, the homogeneous resultant satisfies tons of identities, e.g., the multiplicative property $$ {\rm Res}(G_1 H_1,F_2,\ldots,F_{n+1})= {\rm Res}(G_1,F_2,\ldots,F_{n+1})\ \times\ {\rm Res}(H_1,F_2,\ldots,F_{n+1})\ . $$ The same is true if any other entry of the resultant factorizes as a product of two lower degree forms.

By iterating the identity, one can see that if each $F$ is a product of linear forms, the resultant ${\rm Res}(F_1,\ldots,F_{n+1})$ is the product of $d_1\cdots d_{n+1}$ resultants of linear forms where $d_i={\rm deg}(F_i)$. The latter are just the ordinary determinants of the matrices made by the selected linear forms, which should be easy to compute.


Edit post @Freeman.'s explanation:

OK, it seems the OP wants the homogeneous resultant $$ R={\rm Res}(f_1,\ldots, f_n,g_1,\ldots,g_n) $$ obtained by eliminating all the variables.

Let $[n]$ denote $\{1,\ldots,n\}$. Let $A$ be the set of all functions $\alpha:[n]\rightarrow [n]$ such that $\alpha(j)\in\mathcal{T}_j$ for all $j\in [n]$. Likewise, let $B$ be the set of all functions $\beta:[n]\rightarrow [n]$ such that $\beta(i)\in\mathcal{U}_i$ for all $i\in [n]$. Then, by my previous remarks, $R$ is a product of determinants of $2n\times 2n$ matrices which can be described in $2\times 2$ block form as follows. $$ R=\prod_{(\alpha,\beta)\in A\times B}{\rm det}\left(\begin{array}{cc} M_{\alpha} & -I_n\\ I_n & -M_{\beta} \end{array}\right)\ . $$ For any map $\phi:[n]\rightarrow [n]$, I used the notation $M_{\phi}$ for the $n\times n$ matrix which has, in each row $i$, a $1$ at position $\phi(i)$ and zeros otherwise. Of course, $I_n$ is the identity matrix.

Note that $$ {\rm det}\left(\begin{array}{cc} M_{\alpha} & -I_n\\ I_n & -M_{\beta} \end{array}\right)={\rm det}(I_n-M_{\alpha}M_{\beta})= {\rm det}(I_n-M_{\beta\circ\alpha})\ . $$

From this it follows that if there exists $\alpha,\beta$ such that $\beta\circ\alpha$ has a fixed point in $[n]$, then $R=0$. I would have to think more about the combinatorics of the sets $\mathcal{T}$ and $\mathcal{U}$ but I suspect that $R$ would simply vanish most (all?) of the time.


Another edit: In fact the constant vector is in the kernel of these matrices so all of the above determinants vanish. So $R$ is always zero (except if one of the $\mathcal{T},\mathcal{U}$ set is empty). In retrospect, this was obvious from the beginning because the projective system of equations has a nontrivial solution: take all the $x,y$ to be equal to the same nonzero number.

$\endgroup$
16
  • $\begingroup$ My goal is to find if polynomials $f_j,g_i$ have common zero in $\mathbb P^{2n}(\mathbb C)$ in polynomial time. Do you know which resultant would work here in polynomial time? $\endgroup$
    – Turbo
    Sep 20, 2018 at 18:32
  • $\begingroup$ Moreover I need to express it as determinant of polynomial size and not just compute in polynomial time. By the way it should have been $\mathbb P^{2n-1}(\mathbb C)$ since we have $2n$ variables here. I am looking at $2n$ homogeneous polynomials in $2n$ varibales. So the latter resultant in your case. $\endgroup$
    – Turbo
    Sep 20, 2018 at 18:42
  • $\begingroup$ @Freeman.: answer updated accordingly. $\endgroup$ Sep 20, 2018 at 20:28
  • 1
    $\begingroup$ @Freeman.: I don't know. I would need to invest more time on this which is not a priority for me at the moment. $\endgroup$ Sep 20, 2018 at 20:40
  • 1
    $\begingroup$ A good introduction is this article by Cattani and dickenstein mate.dm.uba.ar/~alidick/papers/chapter1cd.pdf the multiplicative property I used is eq. (1.55) in that reference. $\endgroup$ Sep 24, 2018 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.