independentSets -- some size-maximal independent subsets of variables modulo an ideal

Synopsis

• Usage:

  independentSets J

• Inputs:
  • J, an ideal, or a monomial ideal
• Optional inputs:
  • Limit => an integer, default value infinity, the maximum number of independent sets to be found
• Outputs:
  • a list, of products of variables. The support of any one of these products is a maximal independent subset of variables modulo J

Description

If the Krull dimension of R/J is d, then a maximal independent set is an independent set having size d.

i1 : R = QQ[a..h];

i2 : I = minors(2,genericMatrix(R,a,2,4))

o2 = ideal (- b*c + a*d, - b*e + a*f, - d*e + c*f, - b*g + a*h, - d*g + c*h,
     ------------------------------------------------------------------------
     - f*g + e*h)

o2 : Ideal of R

i3 : inI = ideal leadTerm I

o3 = ideal (f*g, d*g, b*g, d*e, b*e, b*c)

o3 : Ideal of R

i4 : independentSets I

o4 = {a*b*d*f*h, a*c*d*f*h, a*c*e*f*h, a*c*e*g*h}

o4 : List

i5 : independentSets inI

o5 = {a*b*d*f*h, a*c*d*f*h, a*c*e*f*h, a*c*e*g*h}

o5 : List

The independent sets returned correspond one for one with the minimal primes of smallest codimension of the ideal of lead terms of J.

i6 : I = ideal"abc,bcd,cde,adf,cgh,b3f,a3g"

                                                3    3
o6 = ideal (a*b*c, b*c*d, c*d*e, a*d*f, c*g*h, b f, a g)

o6 : Ideal of R

i7 : minimalPrimes I

o7 = {ideal (c, b, a), ideal (f, c, a), ideal (g, d, b), ideal (g, e, b, a),
     ------------------------------------------------------------------------
     ideal (g, f, c), ideal (g, f, d, a), ideal (g, f, e, b), ideal (h, d, b,
     ------------------------------------------------------------------------
     a), ideal (h, e, b, a), ideal (h, f, d, a)}

o7 : List

i8 : independentSets I

o8 = {a*b*d*e*h, a*c*e*f*h, b*d*e*g*h, d*e*f*g*h}

o8 : List

i9 : L = independentSets(I, Limit=>1)

o9 = {a*b*d*e*h}

o9 : List

Often, you want the list of the variables in a maximal independent set, or the list of those not in the set.

i10 : support L_0

o10 = {a, b, d, e, h}

o10 : List

i11 : rsort toList(set gens R - set support L_0)

o11 = {c, f, g}

o11 : List

This function is useful as a subroutine to primary decomposition algorithms.

See also

• PrimaryDecomposition -- primary decomposition and associated primes routines for ideals and modules
• minimalPrimes -- minimal primes of an ideal
• support -- list of variables occurring in a polynomial or matrix
• rsort -- sort a list or matrix in reverse order