Orlik-Terao Algebras#

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

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 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 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 by a and b.

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 subset S 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)#

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: 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 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: 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 in G 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}]