Orlik-Terao Algebras

class sage.algebras.orlik_terao.OrlikTeraoAlgebra(R, M, ordering=None)

Bases: CombinatorialFreeModule

An Orlik-Terao algebra.

Let \(R\) be a commutative ring. Let \(M\) be a matroid with groundset \(X\) with some fixed ordering and representation \(A = (a_x)_{x \in X}\) (so \(a_x\) is a (column) vector). Let \(C(M)\) denote the set of circuits of \(M\). Let \(P\) denote the quotient algebra \(R[e_x \mid x \in X] / \langle e_x^2 \rangle\), i.e., the polynomial algebra with squares being zero. The Orlik-Terao ideal \(J(M)\) is the ideal of \(P\) generated by

\[\partial e_S := \sum_{i=1}^t (-1)^i \chi(S \setminus \{j_i\}) e_{S \setminus \{j_i\}}\]

for all \(S = \left\{ j_1 < j_2 < \cdots < j_t \right\} \in C(M)\), where \(\chi(T)\) is defined as follows. If \(T\) is linearly dependent, then \(\chi(T) = 0\). Otherwise, let \(T = \{x_1 < \cdots < x_{|T|}\}\), and for every flat \(F\) of \(M\), choose a basis \(\Theta_F\). Then define \(\chi(T) = \det(b_1, \dotsc, b_{|T|})\), where \(b_i\) is \(a_{x_i}\) expressed in the basis \(\Theta_F\).

It is easy to see that \(\partial e_S \in J(M)\) not only for circuits \(S\), but also for any dependent set \(S\) of \(M\). Moreover, every dependent set \(S\) of \(M\) satisfies \(e_S \in J(M)\).

The Orlik-Terao algebra \(A(M)\) is the quotient \(E / J(M)\). This is a graded finite-dimensional commutative \(R\)-algebra. The non-broken circuit (NBC) sets of \(M\) (that is, the subsets of \(X\) containing no broken circuit of \(M\)) form a basis of \(A(M)\). (Recall that a broken circuit of \(M\) is defined to be the result of removing the smallest element from a circuit of \(M\).)

In the current implementation, the basis of \(A(M)\) is indexed by the NBC sets, which are implemented as frozensets.

INPUT:

• R – the base ring

• M – the defining matroid

• ordering – (optional) an ordering of the groundset

EXAMPLES:

We create the Orlik-Terao algebra of the wheel matroid \(W(3)\) and do some basic computations:

Sage

sage: M = matroids.Wheel(3)
sage: OT = M.orlik_terao_algebra(QQ)
sage: OT.dimension()
24
sage: G = OT.algebra_generators()
sage: sorted(map(sorted, M.broken_circuits()))
[[1, 3], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4], [2, 5], [4, 5]]
sage: G[1] * G[2] * G[3]
OT{0, 1, 2} + OT{0, 2, 3}
sage: G[1] * G[4] * G[5]
-OT{0, 1, 4} - OT{0, 1, 5} - OT{0, 3, 4} - OT{0, 3, 5}

Python

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(3))
>>> OT = M.orlik_terao_algebra(QQ)
>>> OT.dimension()
24
>>> G = OT.algebra_generators()
>>> sorted(map(sorted, M.broken_circuits()))
[[1, 3], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4], [2, 5], [4, 5]]
>>> G[Integer(1)] * G[Integer(2)] * G[Integer(3)]
OT{0, 1, 2} + OT{0, 2, 3}
>>> G[Integer(1)] * G[Integer(4)] * G[Integer(5)]
-OT{0, 1, 4} - OT{0, 1, 5} - OT{0, 3, 4} - OT{0, 3, 5}

We create an example of a linear matroid and do a basic computation:

Sage

sage: R = ZZ['t'].fraction_field()
sage: t = R.gen()
sage: mat = matrix(R, [[1-3*t/(t+2), t, 5], [-2, 1, 3/(7-t)]])
sage: M = Matroid(mat)
sage: OT = M.orlik_terao_algebra()
sage: G = OT.algebra_generators()
sage: G[1] * G[2]
((2*t^3-12*t^2-12*t-14)/(8*t^2-19*t-70))*OT{0, 1}
 + ((10*t^2-44*t-146)/(-8*t^2+19*t+70))*OT{0, 2}

Python

>>> from sage.all import *
>>> R = ZZ['t'].fraction_field()
>>> t = R.gen()
>>> mat = matrix(R, [[Integer(1)-Integer(3)*t/(t+Integer(2)), t, Integer(5)], [-Integer(2), Integer(1), Integer(3)/(Integer(7)-t)]])
>>> M = Matroid(mat)
>>> OT = M.orlik_terao_algebra()
>>> G = OT.algebra_generators()
>>> G[Integer(1)] * G[Integer(2)]
((2*t^3-12*t^2-12*t-14)/(8*t^2-19*t-70))*OT{0, 1}
 + ((10*t^2-44*t-146)/(-8*t^2+19*t+70))*OT{0, 2}

REFERENCES:

• [OT1994]

• [FL2001]

• [CF2005]

algebra_generators()

Return the algebra generators of self.

These form a family indexed by the groundset \(X\) of \(M\). For each \(x \in X\), the \(x\)-th element is \(e_x\).

EXAMPLES:

Sage

sage: M = matroids.Whirl(2)
sage: OT = M.orlik_terao_algebra()
sage: OT.algebra_generators()
Finite family {0: OT{0}, 1: OT{1}, 2: OT{2}, 3: OT{3}}

sage: M = matroids.catalog.Fano()
sage: OT = M.orlik_terao_algebra()
sage: OT.algebra_generators()
Finite family {'a': OT{a}, 'b': OT{b}, 'c': OT{c}, 'd': OT{d},
               'e': OT{e}, 'f': OT{f}, 'g': OT{g}}

sage: M = matroids.catalog.NonFano()
sage: OT = M.orlik_terao_algebra(GF(3)['t'])
sage: OT.algebra_generators()
Finite family {'a': OT{a}, 'b': OT{b}, 'c': OT{c}, 'd': OT{d},
               'e': OT{e}, 'f': OT{f}, 'g': OT{g}}

Python

>>> from sage.all import *
>>> M = matroids.Whirl(Integer(2))
>>> OT = M.orlik_terao_algebra()
>>> OT.algebra_generators()
Finite family {0: OT{0}, 1: OT{1}, 2: OT{2}, 3: OT{3}}

>>> M = matroids.catalog.Fano()
>>> OT = M.orlik_terao_algebra()
>>> OT.algebra_generators()
Finite family {'a': OT{a}, 'b': OT{b}, 'c': OT{c}, 'd': OT{d},
               'e': OT{e}, 'f': OT{f}, 'g': OT{g}}

>>> M = matroids.catalog.NonFano()
>>> OT = M.orlik_terao_algebra(GF(Integer(3))['t'])
>>> OT.algebra_generators()
Finite family {'a': OT{a}, 'b': OT{b}, 'c': OT{c}, 'd': OT{d},
               'e': OT{e}, 'f': OT{f}, 'g': OT{g}}

degree_on_basis(m)

Return the degree of the basis element indexed by m.

EXAMPLES:

Sage

sage: M = matroids.Wheel(3)
sage: OT = M.orlik_terao_algebra(QQ)
sage: OT.degree_on_basis(frozenset([1]))
1
sage: OT.degree_on_basis(frozenset([0, 2, 3]))
3

Python

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(3))
>>> OT = M.orlik_terao_algebra(QQ)
>>> OT.degree_on_basis(frozenset([Integer(1)]))
1
>>> OT.degree_on_basis(frozenset([Integer(0), Integer(2), Integer(3)]))
3

one_basis()

Return the index of the basis element corresponding to \(1\) in self.

EXAMPLES:

Sage

sage: M = matroids.Wheel(3)
sage: OT = M.orlik_terao_algebra(QQ)
sage: OT.one_basis() == frozenset()
True

Python

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(3))
>>> OT = M.orlik_terao_algebra(QQ)
>>> OT.one_basis() == frozenset()
True

product_on_basis(a, b)

Return the product in self of the basis elements indexed by a and b.

EXAMPLES:

Sage

sage: M = matroids.Wheel(3)
sage: OT = M.orlik_terao_algebra(QQ)
sage: OT.product_on_basis(frozenset([2]), frozenset([3,4]))
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}

Python

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(3))
>>> OT = M.orlik_terao_algebra(QQ)
>>> OT.product_on_basis(frozenset([Integer(2)]), frozenset([Integer(3),Integer(4)]))
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}

Sage

sage: G = OT.algebra_generators()
sage: prod(G)
0
sage: G[2] * G[4]
OT{1, 2} + OT{1, 4}
sage: G[3] * G[4] * G[2]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}
sage: G[2] * G[3] * G[4]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}
sage: G[3] * G[2] * G[4]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}

Python

>>> from sage.all import *
>>> G = OT.algebra_generators()
>>> prod(G)
0
>>> G[Integer(2)] * G[Integer(4)]
OT{1, 2} + OT{1, 4}
>>> G[Integer(3)] * G[Integer(4)] * G[Integer(2)]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}
>>> G[Integer(2)] * G[Integer(3)] * G[Integer(4)]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}
>>> G[Integer(3)] * G[Integer(2)] * G[Integer(4)]
OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4}

subset_image(S)

Return the element \(e_S\) of self corresponding to a subset S of the groundset of the defining matroid.

INPUT:

• S – frozenset which is a subset of the groundset of \(M\)

EXAMPLES:

Sage

sage: M = matroids.Wheel(3)
sage: OT = M.orlik_terao_algebra()
sage: BC = sorted(M.broken_circuits(), key=sorted)
sage: for bc in BC: (sorted(bc), OT.subset_image(bc))
([1, 3], OT{0, 1} + OT{0, 3})
([1, 4, 5], -OT{0, 1, 4} - OT{0, 1, 5} - OT{0, 3, 4} - OT{0, 3, 5})
([2, 3, 4], OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4})
([2, 3, 5], -OT{0, 2, 3} + OT{0, 3, 5})
([2, 4], OT{1, 2} + OT{1, 4})
([2, 5], -OT{0, 2} + OT{0, 5})
([4, 5], -OT{3, 4} - OT{3, 5})

sage: # needs sage.graphs
sage: M4 = matroids.CompleteGraphic(4).ternary_matroid()
sage: OT = M4.orlik_terao_algebra()
sage: OT.subset_image(frozenset({2,3,4}))
OT{0, 2, 3} + 2*OT{0, 3, 4}

Python

>>> from sage.all import *
>>> M = matroids.Wheel(Integer(3))
>>> OT = M.orlik_terao_algebra()
>>> BC = sorted(M.broken_circuits(), key=sorted)
>>> for bc in BC: (sorted(bc), OT.subset_image(bc))
([1, 3], OT{0, 1} + OT{0, 3})
([1, 4, 5], -OT{0, 1, 4} - OT{0, 1, 5} - OT{0, 3, 4} - OT{0, 3, 5})
([2, 3, 4], OT{0, 1, 2} + OT{0, 1, 4} + OT{0, 2, 3} + OT{0, 3, 4})
([2, 3, 5], -OT{0, 2, 3} + OT{0, 3, 5})
([2, 4], OT{1, 2} + OT{1, 4})
([2, 5], -OT{0, 2} + OT{0, 5})
([4, 5], -OT{3, 4} - OT{3, 5})

>>> # needs sage.graphs
>>> M4 = matroids.CompleteGraphic(Integer(4)).ternary_matroid()
>>> OT = M4.orlik_terao_algebra()
>>> OT.subset_image(frozenset({Integer(2),Integer(3),Integer(4)}))
OT{0, 2, 3} + 2*OT{0, 3, 4}

An example of a custom ordering:

Sage

sage: # needs sage.graphs
sage: G = Graph([[3, 4], [4, 1], [1, 2], [2, 3], [3, 5], [5, 6], [6, 3]])
sage: M = Matroid(G).regular_matroid()
sage: s = [(5, 6), (1, 2), (3, 5), (2, 3), (1, 4), (3, 6), (3, 4)]
sage: sorted([sorted(c) for c in M.circuits()])
[[(1, 2), (1, 4), (2, 3), (3, 4)],
 [(3, 5), (3, 6), (5, 6)]]
sage: OT = M.orlik_terao_algebra(QQ, ordering=s)
sage: OT.subset_image(frozenset())
OT{}
sage: OT.subset_image(frozenset([(1,2),(3,4),(1,4),(2,3)]))
0
sage: OT.subset_image(frozenset([(2,3),(1,2),(3,4)]))
OT{(1, 2), (2, 3), (3, 4)}
sage: OT.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(5,6)]))
-OT{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)}
 - OT{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)}
 + OT{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)}
sage: OT.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(3,5)]))
-OT{(1, 2), (1, 4), (2, 3), (3, 5), (5, 6)}
 + OT{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)}
 - OT{(1, 2), (1, 4), (3, 4), (3, 5), (5, 6)}
 + OT{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)}
 + OT{(1, 2), (2, 3), (3, 4), (3, 5), (5, 6)}
 - OT{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)}

Python

>>> from sage.all import *
>>> # needs sage.graphs
>>> G = Graph([[Integer(3), Integer(4)], [Integer(4), Integer(1)], [Integer(1), Integer(2)], [Integer(2), Integer(3)], [Integer(3), Integer(5)], [Integer(5), Integer(6)], [Integer(6), Integer(3)]])
>>> M = Matroid(G).regular_matroid()
>>> s = [(Integer(5), Integer(6)), (Integer(1), Integer(2)), (Integer(3), Integer(5)), (Integer(2), Integer(3)), (Integer(1), Integer(4)), (Integer(3), Integer(6)), (Integer(3), Integer(4))]
>>> sorted([sorted(c) for c in M.circuits()])
[[(1, 2), (1, 4), (2, 3), (3, 4)],
 [(3, 5), (3, 6), (5, 6)]]
>>> OT = M.orlik_terao_algebra(QQ, ordering=s)
>>> OT.subset_image(frozenset())
OT{}
>>> OT.subset_image(frozenset([(Integer(1),Integer(2)),(Integer(3),Integer(4)),(Integer(1),Integer(4)),(Integer(2),Integer(3))]))
0
>>> OT.subset_image(frozenset([(Integer(2),Integer(3)),(Integer(1),Integer(2)),(Integer(3),Integer(4))]))
OT{(1, 2), (2, 3), (3, 4)}
>>> OT.subset_image(frozenset([(Integer(1),Integer(4)),(Integer(3),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(6)),(Integer(5),Integer(6))]))
-OT{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)}
 - OT{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)}
 + OT{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)}
>>> OT.subset_image(frozenset([(Integer(1),Integer(4)),(Integer(3),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(6)),(Integer(3),Integer(5))]))
-OT{(1, 2), (1, 4), (2, 3), (3, 5), (5, 6)}
 + OT{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)}
 - OT{(1, 2), (1, 4), (3, 4), (3, 5), (5, 6)}
 + OT{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)}
 + OT{(1, 2), (2, 3), (3, 4), (3, 5), (5, 6)}
 - OT{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)}

class sage.algebras.orlik_terao.OrlikTeraoInvariantAlgebra(R, M, G, action_on_groundset=None, *args, **kwargs)

Bases: FiniteDimensionalInvariantModule

Give the invariant algebra of the Orlik-Terao algebra from the action on \(A(M)\) which is induced from the action_on_groundset.

INPUT:

• R – the ring of coefficients

• M – a matroid

• G – a semigroup

• action_on_groundset – a function defining the action of G on the elements of the groundset of M default

OUTPUT:

• The invariant algebra of the Orlik-Terao algebra induced by the action of action_on_groundset

EXAMPLES:

Lets start with the action of \(S_3\) on the rank-\(2\) braid matroid:

Sage

sage: A = matrix([[1,1,0],[-1,0,1],[0,-1,-1]])
sage: M = Matroid(A)
sage: M.groundset()
frozenset({0, 1, 2})
sage: G = SymmetricGroup(3)                                                     # needs sage.groups

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(0)],[-Integer(1),Integer(0),Integer(1)],[Integer(0),-Integer(1),-Integer(1)]])
>>> M = Matroid(A)
>>> M.groundset()
frozenset({0, 1, 2})
>>> G = SymmetricGroup(Integer(3))                                                     # needs sage.groups

Calling elements g of G on an element \(i\) of \(\{1,2,3\}\) defines the action we want, but since the groundset is \(\{0,1,2\}\) we first add \(1\) and then subtract \(1\):

Sage

sage: def on_groundset(g, x):
....:     return g(x+1)-1

Python

>>> from sage.all import *
>>> def on_groundset(g, x):
...     return g(x+Integer(1))-Integer(1)

Now that we have defined an action we can create the invariant, and get its basis:

Sage

sage: # needs sage.groups
sage: OTG = M.orlik_terao_algebra(QQ, invariant=(G, on_groundset))
sage: OTG.basis()
Finite family {0: B[0], 1: B[1]}
sage: [OTG.lift(b) for b in OTG.basis()]
[OT{}, OT{0} + OT{1} + OT{2}]

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> OTG = M.orlik_terao_algebra(QQ, invariant=(G, on_groundset))
>>> OTG.basis()
Finite family {0: B[0], 1: B[1]}
>>> [OTG.lift(b) for b in OTG.basis()]
[OT{}, OT{0} + OT{1} + OT{2}]

Since it is invariant, the action of any g in G is trivial:

Sage

sage: # needs sage.groups
sage: x = OTG.an_element(); x
2*B[0] + 2*B[1]
sage: g = G.an_element(); g
(2,3)
sage: g*x
2*B[0] + 2*B[1]

sage: # needs sage.groups
sage: x = OTG.random_element()
sage: g = G.random_element()
sage: g*x == x
True

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> x = OTG.an_element(); x
2*B[0] + 2*B[1]
>>> g = G.an_element(); g
(2,3)
>>> g*x
2*B[0] + 2*B[1]

>>> # needs sage.groups
>>> x = OTG.random_element()
>>> g = G.random_element()
>>> g*x == x
True

The underlying ambient module is the Orlik-Terao algebra, which is accessible via ambient():

Sage

sage: M.orlik_terao_algebra(QQ) is OTG.ambient()                                # needs sage.groups
True

Python

>>> from sage.all import *
>>> M.orlik_terao_algebra(QQ) is OTG.ambient()                                # needs sage.groups
True

For a bigger example, here we will look at the rank-\(3\) braid matroid:

Sage

sage: # needs sage.groups
sage: A = matrix([[1,1,1,0,0,0],[-1,0,0,1,1,0],
....:             [0,-1,0,-1,0,1],[0,0,-1,0,-1,-1]]); A
[ 1  1  1  0  0  0]
[-1  0  0  1  1  0]
[ 0 -1  0 -1  0  1]
[ 0  0 -1  0 -1 -1]
sage: M = Matroid(A); M.groundset()
frozenset({0, 1, 2, 3, 4, 5})
sage: G = SymmetricGroup(6)
sage: OTG = M.orlik_terao_algebra(QQ, invariant=(G, on_groundset))
sage: OTG.ambient()
Orlik-Terao algebra of
 Linear matroid of rank 3 on 6 elements represented over the Rational Field
 over Rational Field
sage: OTG.basis()
Finite family {0: B[0], 1: B[1]}
sage: [OTG.lift(b) for b in OTG.basis()]
[OT{}, OT{0} + OT{1} + OT{2} + OT{3} + OT{4} + OT{5}]

Python

>>> from sage.all import *
>>> # needs sage.groups
>>> A = matrix([[Integer(1),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)],[-Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0)],
...             [Integer(0),-Integer(1),Integer(0),-Integer(1),Integer(0),Integer(1)],[Integer(0),Integer(0),-Integer(1),Integer(0),-Integer(1),-Integer(1)]]); A
[ 1  1  1  0  0  0]
[-1  0  0  1  1  0]
[ 0 -1  0 -1  0  1]
[ 0  0 -1  0 -1 -1]
>>> M = Matroid(A); M.groundset()
frozenset({0, 1, 2, 3, 4, 5})
>>> G = SymmetricGroup(Integer(6))
>>> OTG = M.orlik_terao_algebra(QQ, invariant=(G, on_groundset))
>>> OTG.ambient()
Orlik-Terao algebra of
 Linear matroid of rank 3 on 6 elements represented over the Rational Field
 over Rational Field
>>> OTG.basis()
Finite family {0: B[0], 1: B[1]}
>>> [OTG.lift(b) for b in OTG.basis()]
[OT{}, OT{0} + OT{1} + OT{2} + OT{3} + OT{4} + OT{5}]

construction()

Return the functorial construction of self.

This implementation of the method only returns None.