Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Equivariant Gröbner bases and the Gaussian two-factor model

Authors: Andries E. Brouwer and Jan Draisma
Journal: Math. Comp. 80 (2011), 1123-1133
MSC (2010): Primary 13P10, 16W22; Secondary 62H25
Published electronically: September 9, 2010
MathSciNet review: 2772115
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Exploiting symmetry in Gröbner basis computations is difficult when the symmetry takes the form of a group acting by automorphisms on monomials in finitely many variables. This is largely due to the fact that the group elements, being invertible, cannot preserve a term order. By contrast, inspired by work of Aschenbrenner and Hillar, we introduce the concept of equivariant Gröbner basis in a setting where a monoid acts by homomorphisms on monomials in potentially infinitely many variables. We require that the action be compatible with a term order, and under some further assumptions derive a Buchberger-type algorithm for computing equivariant Gröbner bases.

Using this algorithm and the monoid of strictly increasing functions $ \mathbb{N} \to \mathbb{N}$ we prove that the kernel of the ring homomorphism

$\displaystyle \mathbb{R}[y_{ij} \mid i,j \in \mathbb{N}, i > j] \to\mathbb{R}[s_i,t_i \mid i \in \mathbb{N}], y_{ij} \mapsto s_is_j + t_it_j $

is generated by two types of polynomials: off-diagonal $ 3 \times 3$-minors and pentads. This confirms a conjecture by Drton, Sturmfels, and Sullivant on the Gaussian two-factor model from algebraic statistics.

References [Enhancements On Off] (What's this?)

  • 1. Matthias Aschenbrenner and Christopher J. Hillar.
    Finite generation of symmetric ideals.
    Trans. Amer. Math. Soc., 359(11):5171-5192, 2007. MR 2327026 (2008g:13030)
  • 2. Matthias Aschenbrenner and Christopher J. Hillar.
    An algorithm for finding symmetric Gröbner bases in infinite dimensional rings.
    ISSAC 2008, 117-123, ACM, New York, 2008. MR 2500387
  • 3. Daniel E. Cohen.
    On the laws of a metabelian variety.
    J. Algebra, 5:267-273, 1967. MR 0206104 (34:5929)
  • 4. Daniel E. Cohen.
    Closure relations, Buchberger's algorithm, and polynomials in infinitely many variables.
    In Computation theory and logic, volume 270 of Lect. Notes Comput. Sci., pages 78-87, 1987. MR 907514 (89a:68113)
  • 5. Aldo Conca.
    Gröbner bases of ideals of minors of a symmetric matrix.
    J. Algebra, 166(2):406-421, 1994. MR 1279266 (95g:13012)
  • 6. Jesús A. de Loera, Bernd Sturmfels, and Rekha R. Thomas.
    Gröbner bases and triangulations of the second hypersimplex.
    Combinatorica, 15:409-424, 1995. MR 1357285 (97b:13035)
  • 7. Jan Draisma.
    Finiteness for the $ k$-factor model and chirality varieties.
    Adv. Math., 223:243-256, 2010. MR 2563217
  • 8. Vesselin Drensky and Roberto La Scala.
    Gröbner bases of ideals invariant under endomorphisms.
    J. Symb. Comput., 41(7):835-846, 2006. MR 2232204 (2007m:16023)
  • 9. Mathias Drton, Bernd Sturmfels, and Seth Sullivant.
    Algebraic factor analysis: tetrads, pentads and beyond.
    Probab. Theory Relat. Fields, 138(3-4):463-493, 2007. MR 2299716 (2008f:62086)
  • 10. Mathias Drton and Han Xiao.
    Finiteness of small factor analysis models.
    personal communication, 2008.
  • 11. Chris J. Hillar and Seth Sullivant.
    Finite Gröbner bases in infinite dimensional polynomial rings and applications.
    Preprint, available from, 2009.
  • 12. Bernd Sturmfels.
    Gröbner bases and Stanley decompositions of determinantal ideals.
    Math. Z., 205(1):137-144, 1990. MR 1069489 (91m:14076)
  • 13. Bernd Sturmfels and Seth Sullivant.
    Combinatorial secant varieties.
    Pure Appl. Math. Q., 2(3):867-891, 2006. MR 2252121 (2007h:14082)
  • 14. Seth Sullivant.
    A Gröbner basis for the secant ideal of the second hypersimplex. J. Commut. Algebra 1(2):327-338. MR 2504939 (2010d:13033)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 13P10, 16W22, 62H25

Retrieve articles in all journals with MSC (2010): 13P10, 16W22, 62H25

Additional Information

Andries E. Brouwer
Affiliation: Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands

Jan Draisma
Affiliation: Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands and Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands

Keywords: Equivariant Gröbner bases, algebraic factor analysis
Received by editor(s): August 11, 2009
Received by editor(s) in revised form: February 3, 2010
Published electronically: September 9, 2010
Additional Notes: The second author is supported by DIAMANT, an NWO mathematics cluster.
Article copyright: © Copyright 2010 A. E. Brouwer and J. Draisma

American Mathematical Society