Multihomogeneous resultant formulae by means of complexes

Alicia Dickenstein, Ioannis Z. Emiris

Introduction

In the field of algebraic geometry, determining whether a system of polynomial equations possesses a common solution is a fundamental task with significant implications for robotics, computer vision, and geometric modeling. The mathematical tool used to answer this question is the resultant—a single polynomial in the coefficients of the system that vanishes if and only if a common root exists.

While resultants for homogeneous systems are well-understood, many practical applications involve multihomogeneous systems. In these systems, variables are partitioned into distinct groups, and the equations are homogeneous with respect to each group independently. Constructing efficient matrices for these systems is challenging; standard methods often yield matrices that are either unnecessarily large or whose determinants are merely multiples of the actual resultant. This paper addresses the "holy grail" of resultant theory: the classification and construction of the smallest possible square matrices, known as determinantal formulae, whose determinant is exactly the resultant.

Methodology: Weyman Complexes and Degree Vectors

The authors approach the problem through the lens of Weyman complexes, a sophisticated algebraic framework that represents the resultant as the determinant of a sequence of vector spaces and maps. The structure of these complexes is governed by a "degree vector" ($m$).

The research provides a systematic way to analyze these vectors to determine the structure of the resulting matrix. Key methodological contributions include:

  • Combinatorial Classification: Building upon the foundational work of Sturmfels, Zelevinsky, and Weyman, the authors utilize "defect vectors" to classify which multihomogeneous systems admit specific matrix types (Sylvester, Bézout, or hybrid).
  • Algorithmic Search: Rather than relying on heuristics, the paper establishes explicit bounds to search for optimal degree vectors. This allows for the automated identification of the most efficient matrix representations.
  • Software Implementation: The theoretical findings are implemented in a Maple library, mhomo.mpl, which automates the construction of these complex matrices, making the theory accessible for practical computation.

Key Theoretical Insights

The paper reveals several deep connections between the combinatorics of variable groups and the structure of resultant matrices:

The Defect Connection

A significant finding is the characterization of systems admitting purely Bézout-type determinantal formulae. The authors prove that such a formula exists if and only if the system's "defect vector" is zero. Crucially, this is the same condition required for an optimal Sylvester-type formula, linking two traditionally distinct matrix types through a single combinatorial property.

Permutations and Bézout Matrices

The research identifies a beautiful bijection between pure Bézout matrices and the permutations of the variable groups. For a system with $r$ groups of variables, there are exactly $r!$ such formulae. This discovery provides a complete map of the available Bézout-type representations for a given system.

Symmetry and Serre Duality

By applying Serre’s duality, the authors demonstrate a powerful symmetry in the search space for degree vectors. If a degree vector $m$ yields a determinantal formula, its "critical" counterpart, defined as $\rho - m$, yields a matrix of the identical size. This effectively doubles the pool of known optimal formulae and simplifies the search process.

Results and Performance

The proposed framework demonstrates clear advantages in matrix size and computational efficiency. The authors evaluate their algorithms on specific classes of multihomogeneous systems, such as bilinear systems and custom configurations (e.g., systems with dimension $l=(1,2)$ and degree $d=(2,3)$).

In one benchmark case, the authors identified a $1120 \times 1120$ square matrix (a determinantal formula), whereas previous general-purpose heuristics could only produce a $1120 \times 1200$ rectangular matrix. Furthermore, the paper provides the first necessary and sufficient conditions for a multihomogeneous system to admit a purely Bézout-type determinantal matrix for any number of variables. For systems where pure Sylvester or Bézout forms are impossible, the authors provide a roadmap for constructing "hybrid" matrices, illustrated in the paper by a complex $1320 \times 1320$ example.

Conclusion and Future Directions

This work advances the state of the art in resultant theory by providing explicit tools for constructing minimal matrix representations for multihomogeneous systems. However, several avenues for future research remain:

  • Mixed Systems: The current framework focuses on "unmixed" systems, where all polynomials share the same support. Extending these results to "mixed" systems is a primary goal for future work.
  • Maximal Minors: In cases where a determinantal formula does not exist, identifying which "maximal minor" of a rectangular matrix yields the exact resultant remains an open challenge.
  • Scaled Supports: Generalizing the results to polynomials with varying degrees or scaled supports would further increase the applicability of these methods to real-world engineering problems.

Summary updated

Abstract

We provide conditions and algorithmic tools so as to classify and construct the smallest possible determinantal formulae for multihomogeneous resultants arising from Weyman complexes associated to line bundles in products of projective spaces. We also examine the smallest Sylvester-type matrices, generically of full rank, which yield a multiple of the resultant. We characterize the systems that admit a purely Bézout-type matrix and show a bijection of such matrices with the permutations of the variable groups. We conclude with examples showing the hybrid matrices that may be encountered, and illustrations of our Maple implementation. Our approach makes heavy use of the combinatorics of multihomogeneous systems, inspired by and generalizing results by Sturmfels-Zelevinsky, and Weyman-Zelevinsky.
BibTeX
@article{dickenstein2003multihomogeneous,
  author = {Alicia Dickenstein and Ioannis Z. Emiris},
  title = {{Multihomogeneous resultant formulae by means of complexes}},
  journal = {J. Symb. Comput.},
  year = {2003},
  doi = {10.1016/s0747-7171(03)00086-5},
}
Figure