Orlik-Solomon Algebras#
- class sage.algebras.orlik_solomon.OrlikSolomonAlgebra(R, M, ordering=None)#
Bases:
CombinatorialFreeModule
An Orlik-Solomon algebra.
Let \(R\) be a commutative ring. Let \(M\) be a matroid with ground set \(X\). Let \(C(M)\) denote the set of circuits of \(M\). Let \(E\) denote the exterior algebra over \(R\) generated by \(\{ e_x \mid x \in X \}\). The Orlik-Solomon ideal \(J(M)\) is the ideal of \(E\) generated by
\[\partial e_S := \sum_{i=1}^t (-1)^{i-1} e_{j_1} \wedge e_{j_2} \wedge \cdots \wedge \widehat{e}_{j_i} \wedge \cdots \wedge e_{j_t}\]for all \(S = \left\{ j_1 < j_2 < \cdots < j_t \right\} \in C(M)\), where \(\widehat{e}_{j_i}\) means that the term \(e_{j_i}\) is being omitted. The notation \(\partial e_S\) is not a coincidence, as \(\partial e_S\) is actually the image of \(e_S := e_{j_1} \wedge e_{j_2} \wedge \cdots \wedge e_{j_t}\) under the unique derivation \(\partial\) of \(E\) which sends all \(e_x\) to \(1\).
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-Solomon algebra \(A(M)\) is the quotient \(E / J(M)\). This is a graded finite-dimensional skew-commutative \(R\)-algebra. Fix some ordering on \(X\); then, the NBC sets of \(M\) (that is, the subsets of \(X\) containing no broken circuit of \(M\)) form a basis of \(A(M)\). (Here, 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 ringM
– the defining matroidordering
– (optional) an ordering of the ground set
EXAMPLES:
We create the Orlik-Solomon algebra of the uniform matroid \(U(3, 4)\) and do some basic computations:
sage: M = matroids.Uniform(3, 4) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.dimension() 14 sage: G = OS.algebra_generators() sage: M.broken_circuits() frozenset({frozenset({1, 2, 3})}) sage: G[1] * G[2] * G[3] OS{0, 1, 2} - OS{0, 1, 3} + OS{0, 2, 3}
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.Uniform(2, 2) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{1}} sage: M = matroids.Uniform(1, 2) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{0}} sage: M = matroids.Uniform(1, 3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.algebra_generators() Finite family {0: OS{0}, 1: OS{0}, 2: OS{0}}
- as_cdga()#
Return the commutative differential graded algebra corresponding to
self
with the trivial differential.EXAMPLES:
sage: H = hyperplane_arrangements.braid(3) sage: O = H.orlik_solomon_algebra(QQ) sage: O.as_cdga() Commutative Differential Graded Algebra with generators ('e0', 'e1', 'e2') in degrees (1, 1, 1) with relations [e0*e1 - e0*e2 + e1*e2] over Rational Field with differential: e0 --> 0 e1 --> 0 e2 --> 0
- as_gca()#
Return the graded commutative algebra corresponding to
self
.EXAMPLES:
sage: H = hyperplane_arrangements.braid(3) sage: O = H.orlik_solomon_algebra(QQ) sage: O.as_gca() Graded Commutative Algebra with generators ('e0', 'e1', 'e2') in degrees (1, 1, 1) with relations [e0*e1 - e0*e2 + e1*e2] over Rational Field
sage: N = matroids.named_matroids.Fano() sage: O = N.orlik_solomon_algebra(QQ) sage: O.as_gca() Graded Commutative Algebra with generators ('e0', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6') in degrees (1, 1, 1, 1, 1, 1, 1) with relations [e1*e2 - e1*e3 + e2*e3, e0*e1*e3 - e0*e1*e4 + e0*e3*e4 - e1*e3*e4, e0*e2 - e0*e4 + e2*e4, e3*e4 - e3*e5 + e4*e5, e1*e2*e4 - e1*e2*e5 + e1*e4*e5 - e2*e4*e5, e0*e2*e3 - e0*e2*e5 + e0*e3*e5 - e2*e3*e5, e0*e1 - e0*e5 + e1*e5, e2*e5 - e2*e6 + e5*e6, e1*e3*e5 - e1*e3*e6 + e1*e5*e6 - e3*e5*e6, e0*e4*e5 - e0*e4*e6 + e0*e5*e6 - e4*e5*e6, e1*e4 - e1*e6 + e4*e6, e2*e3*e4 - e2*e3*e6 + e2*e4*e6 - e3*e4*e6, e0*e3 - e0*e6 + e3*e6, e0*e1*e2 - e0*e1*e6 + e0*e2*e6 - e1*e2*e6] over Rational Field
- degree_on_basis(m)#
Return the degree of the basis element indexed by
m
.EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: OS.degree_on_basis(frozenset([1])) 1 sage: OS.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: OS = M.orlik_solomon_algebra(QQ) sage: OS.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: OS = M.orlik_solomon_algebra(QQ) sage: OS.product_on_basis(frozenset([2]), frozenset([3,4])) OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}
sage: G = OS.algebra_generators() sage: prod(G) 0 sage: G[2] * G[4] -OS{1, 2} + OS{1, 4} sage: G[3] * G[4] * G[2] OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4} sage: G[2] * G[3] * G[4] OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4} sage: G[3] * G[2] * G[4] -OS{0, 1, 2} + OS{0, 1, 4} - OS{0, 2, 3} - OS{0, 3, 4}
- subset_image(S)#
Return the element \(e_S\) of \(A(M)\) (
== self
) corresponding to a subset \(S\) of the ground set of \(M\).INPUT:
S
– a frozenset which is a subset of the ground set of \(M\)
EXAMPLES:
sage: M = matroids.Wheel(3) sage: OS = M.orlik_solomon_algebra(QQ) sage: BC = sorted(M.broken_circuits(), key=sorted) sage: for bc in BC: (sorted(bc), OS.subset_image(bc)) ([1, 3], -OS{0, 1} + OS{0, 3}) ([1, 4, 5], OS{0, 1, 4} - OS{0, 1, 5} - OS{0, 3, 4} + OS{0, 3, 5}) ([2, 3, 4], OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}) ([2, 3, 5], OS{0, 2, 3} + OS{0, 3, 5}) ([2, 4], -OS{1, 2} + OS{1, 4}) ([2, 5], -OS{0, 2} + OS{0, 5}) ([4, 5], -OS{3, 4} + OS{3, 5}) sage: M4 = matroids.CompleteGraphic(4) sage: OS = M4.orlik_solomon_algebra(QQ) sage: OS.subset_image(frozenset({2,3,4})) OS{0, 2, 3} + OS{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) 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: OS = M.orlik_solomon_algebra(QQ, ordering=s) sage: OS.subset_image(frozenset([])) OS{} sage: OS.subset_image(frozenset([(1,2),(3,4),(1,4),(2,3)])) 0 sage: OS.subset_image(frozenset([(2,3),(1,2),(3,4)])) OS{(1, 2), (2, 3), (3, 4)} sage: OS.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(5,6)])) -OS{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)} + OS{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)} - OS{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)} sage: OS.subset_image(frozenset([(1,4),(3,4),(2,3),(3,6),(3,5)])) OS{(1, 2), (1, 4), (2, 3), (3, 5), (5, 6)} - OS{(1, 2), (1, 4), (2, 3), (3, 6), (5, 6)} + OS{(1, 2), (1, 4), (3, 4), (3, 5), (5, 6)} + OS{(1, 2), (1, 4), (3, 4), (3, 6), (5, 6)} - OS{(1, 2), (2, 3), (3, 4), (3, 5), (5, 6)} - OS{(1, 2), (2, 3), (3, 4), (3, 6), (5, 6)}
- class sage.algebras.orlik_solomon.OrlikSolomonInvariantAlgebra(R, M, G, action_on_groundset=None, *args, **kwargs)#
Bases:
FiniteDimensionalInvariantModule
The invariant algebra of the Orlik-Solomon algebra from the action on \(A(M)\) induced from the
action_on_groundset
.INPUT:
R
– the ring of coefficientsM
– a matroidG
– a semigroupaction_on_groundset
– (optional) a function defining the action ofG
on the elements of the groundset ofM
; default isg(x)
EXAMPLES:
Lets start with the action of \(S_3\) on the rank \(2\) braid matroid:
sage: M = matroids.CompleteGraphic(3) 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: OSG = M.orlik_solomon_algebra(QQ, invariant=(G, on_groundset)) sage: OSG.basis() Finite family {0: B[0], 1: B[1]} sage: [OSG.lift(b) for b in OSG.basis()] [OS{}, OS{0} + OS{1} + OS{2}]
Since it is invariant, the action of any
g
inG
is trivial:sage: x = OSG.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 = OSG.random_element() sage: g = G.random_element() sage: g * x == x True
The underlying ambient module is the Orlik-Solomon algebra, which is accessible via
ambient()
:sage: M.orlik_solomon_algebra(QQ) is OSG.ambient() True
There is not much structure here, so lets look at a bigger example. Here we will look at the rank \(3\) braid matroid, and to make things easier, we’ll start the indexing at \(1\) so that the \(S_6\) action on the groundset is simply calling \(g\):
sage: M = matroids.CompleteGraphic(4); M.groundset() frozenset({0, 1, 2, 3, 4, 5}) sage: new_bases = [frozenset(i+1 for i in j) for j in M.bases()] sage: M = Matroid(bases=new_bases); M.groundset() frozenset({1, 2, 3, 4, 5, 6}) sage: G = SymmetricGroup(6) sage: OSG = M.orlik_solomon_algebra(QQ, invariant=G) sage: OSG.basis() Finite family {0: B[0], 1: B[1]} sage: [OSG.lift(b) for b in OSG.basis()] [OS{}, OS{1} + OS{2} + OS{3} + OS{4} + OS{5} + OS{6}] sage: (OSG.basis()[1])^2 0 sage: 5 * OSG.basis()[1] 5*B[1]
Next, we look at the same matroid but with an \(S_3 \times S_3\) action (here realized as a Young subgroup of \(S_6\)):
sage: H = G.young_subgroup([3, 3]) sage: OSH = M.orlik_solomon_algebra(QQ, invariant=H) sage: OSH.basis() Finite family {0: B[0], 1: B[1], 2: B[2]} sage: [OSH.lift(b) for b in OSH.basis()] [OS{}, OS{4} + OS{5} + OS{6}, OS{1} + OS{2} + OS{3}]
We implement an \(S_4\) action on the vertices:
sage: M = matroids.CompleteGraphic(4) sage: G = SymmetricGroup(4) sage: edge_map = {i: M.groundset_to_edges([i])[0][:2] ....: for i in M.groundset()} sage: inv_map = {v: k for k, v in edge_map.items()} sage: def vert_action(g, x): ....: a, b = edge_map[x] ....: return inv_map[tuple(sorted([g(a+1)-1, g(b+1)-1]))] sage: OSG = M.orlik_solomon_algebra(QQ, invariant=(G, vert_action)) sage: B = OSG.basis() sage: [OSG.lift(b) for b in B] [OS{}, OS{0} + OS{1} + OS{2} + OS{3} + OS{4} + OS{5}]
We use this to describe the Young subgroup \(S_2 \times S_2\) action:
sage: H = G.young_subgroup([2,2]) sage: OSH = M.orlik_solomon_algebra(QQ, invariant=(H, vert_action)) sage: B = OSH.basis() sage: [OSH.lift(b) for b in B] [OS{}, OS{5}, OS{1} + OS{2} + OS{3} + OS{4}, OS{0}, -1/2*OS{1, 2} + OS{1, 5} - 1/2*OS{3, 4} + OS{3, 5}, OS{0, 5}, OS{0, 1} + OS{0, 2} + OS{0, 3} + OS{0, 4}, -1/2*OS{0, 1, 2} + OS{0, 1, 5} - 1/2*OS{0, 3, 4} + OS{0, 3, 5}]
We demonstrate the algebra structure:
sage: matrix([[b*bp for b in B] for bp in B]) [ B[0] B[1] B[2] B[3] B[4] B[5] B[6] B[7]] [ B[1] 0 2*B[4] B[5] 0 0 2*B[7] 0] [ B[2] -2*B[4] 0 B[6] 0 -2*B[7] 0 0] [ B[3] -B[5] -B[6] 0 B[7] 0 0 0] [ B[4] 0 0 B[7] 0 0 0 0] [ B[5] 0 -2*B[7] 0 0 0 0 0] [ B[6] 2*B[7] 0 0 0 0 0 0] [ B[7] 0 0 0 0 0 0 0]
Note
The algebra structure only exists when the action on the groundset yields an equivariant matroid, in the sense that \(g \cdot I \in \mathcal{I}\) for every \(g \in G\) and for every \(I \in \mathcal{I}\).
- construction()#
Return the functorial construction of
self
.This implementation of the method only returns
None
.