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 ground set \(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 abroken 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 ringM
– the defining matroidordering
– (optional) an ordering of the ground set
EXAMPLES:
We create the Orlik-Terao algebra of the wheel matroid \(W(3)\) and do some basic computations:
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}
We create an example of a linear matroid and do a basic computation:
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}
REFERENCES:
- algebra_generators()#
Return the algebra generators of
self
.These form a family indexed by the ground set \(X\) of \(M\). For each \(x \in X\), the \(x\)-th element is \(e_x\).
EXAMPLES:
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.named_matroids.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.named_matroids.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}}
- degree_on_basis(m)#
Return the degree of the basis element indexed by
m
.EXAMPLES:
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
- one_basis()#
Return the index of the basis element corresponding to \(1\) in
self
.EXAMPLES:
sage: M = matroids.Wheel(3) sage: OT = M.orlik_terao_algebra(QQ) sage: OT.one_basis() == frozenset([]) True
- product_on_basis(a, b)#
Return the product in
self
of the basis elements indexed bya
andb
.EXAMPLES:
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}
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}
- subset_image(S)#
Return the element \(e_S\) of
self
corresponding to a subsetS
of the ground set of the defining matroid.INPUT:
S
– a frozenset which is a subset of the ground set of \(M\)
EXAMPLES:
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: 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}
An example of a custom ordering:
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)}
- 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 coefficientsM
– a matroidG
– a semigroupaction_on_groundset
– a function defining the action ofG
on the elements of the groundset ofM
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: 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)
Calling elements
g
ofG
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: def on_groundset(g,x): ....: return g(x+1)-1
Now that we have defined an action we can create the invariant, and get its basis:
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}]
Since it is invariant, the action of any
g
inG
is trivial: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: x = OTG.random_element() sage: g = G.random_element() sage: g*x == x True
The underlying ambient module is the Orlik-Terao algebra, which is accessible via
ambient()
:sage: M.orlik_terao_algebra(QQ) is OTG.ambient() True
For a bigger example, here we will look at the rank-\(3\) braid matroid:
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}]
- construction()#
Return the functorial construction of
self
.This implementation of the method only returns
None
.