Multihomogeneous resultant matrices

ABSTRACT

Multihomogeneous structure in algebraic systems is the first step away from the classical theory of homogeneous equations towards fully exploiting arbitrary supports. We propose constructive methods for resultant matrices in the entire spectrum of resultant formulae, ranging from pure Sylvester to pure Bézout types, including hybrid matrices. Our approach makes heavy use of the combinatorics of multihomogeneous systems, inspired by and generalizing certain joint results by Zelevinsky, and Sturmfels or Weyman [15, 18]. One contribution is to provide conditions and algorithmic tools so as to classify and construct the smallest possible determinantal formulae for multihomogeneous resultants. We also examine the smallest Sylvester-type matrices, generically of full rank, which yield a multiple of the resultant. The last contribution is to 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. Interestingly, it is the same class of systems admitting an optimal Sylvester-type formula. We conclude with an example showing all kinds of matrices that may be encountered, and illustrations of our MAPLE implementation.

REFERENCES

• 1: CARDINAL, J.-P., AND MOURRAIN, B. Algebraic approach of residues and applications. In Math. of Numerical Analysis, J. Renegar, M. Shub, & S. Smale, eds., vol. 32 Lect. Appl. Math. AMS, 1996, pp. 189-210.
• 2: CHIONH, E., GOLDMAN, R., AND ZHANG, M. Hybrid Dixon resultants. In Proc. 8th IMA Conf. Math. of Surfaces (1998), pp. 193-212.
• 3: Arthur D. Chtcherba , Deepak Kapur, Conditions for exact resultants using the Dixon formulation, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.62-70, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345583]
• 4: D'ANDREA, C., AND DICKENSTEIN, A. Explicit formulas for the multivariate resultant. J. Pure Appl. Algebra 164, 1-2 (2001), 59-86.
• 5: D'ANDREA, C., AND EMIRIS, I. Z. Computing Sparse Projection Operators. In Symb. Comput.: Solving Equations in Algebra, Geometry, & Engineering, E. Green, S. Hoşşten, R. Laubenbacher, & V. Powers, eds., vol. 286, Cont. Math. AMS, 2001, pp. 121-139.
• 6: EISENBUD, D., AND SCHREYER, F.-O. Resultants and Chow forms via exterior syzygies. Tech. Rep. 037, MSRI, 2001.
• 7: Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
• 8: Ioannis Z. Emiris , Bernard Mourrain, Matrices in elimination theory, Journal of Symbolic Computation, v.28 n.1-2, p.3-44, July/Aug. 1999 [doi>10.1006/jsco.1998.0266]
• 9: Ioannis Z. Emiris , Victor Y. Pan, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Journal of Symbolic Computation, v.33 n.4, p.393-413, April 2002 [doi>10.1006/jsco.2002.0520]
• 10: GELFAND, I., KAPRANOV, M., AND ZELEVINSKY, A. Discriminants, Resultants and Multidimensional Determinants. Birkhäuser, Boston, 1994.
• 11: HARTSHORNE, R. Algebraic Geometry. Graduate Texts in Math. Springer, New York, 1977.
• 12: JOUANOLOU, J.-P. Formes d'inertie et résultant: Un formulaire. Adv. in Math. 126 (1997), 119-250.
• 13: Bernard Mourrain , Victor Y. Pan, Multivariate polynomials, duality, and structured matrices, Journal of Complexity, v.16 n.1, p.110-180, March 2000 [doi>10.1006/jcom.1999.0530]
• 14: Tushar Saxena, Efficient variable elimination using resultants, State University of New York at Albany, Albany, NY, 1997
• 15: STURMFELS, B., AND ZELEVINSKY, A. Multigraded resultants of Sylvester type. J.Algebra 163, 1(1994), 115-127.
• 16: WAMPLER, C. Bezout number calculations for multi-homogeneous polynomial systems. Appl. Math. & Computat. 51 (1992), 143-157.
• 17: WEYMAN, J. Calculating discriminant direct images. Trans. AMS 343, 1 (1994), 367-389.
• 18: WEYMAN, J., AND ZELEVINSKY, A. Determinantal formulas for multigraded resultants. J. Alg. Geom. 3, (1994), 569-597.
• 19: Ming Zhang , Ronald Goldman, Topics in resultants and implicitization, 2000

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Pre- and post-conditions

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Documentation

Keywords:
Sylvester and Bézout type matrix, degree vector, determinantal, formula, multihomogeneous system, sparse resultant