# Orlik-Solomon Algebras¶

class sage.algebras.orlik_solomon.OrlikSolomonAlgebra(R, M, ordering=None)

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 ring

• M – the defining matroid

• ordering – (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 * G * G
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}}

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

EXAMPLES:

sage: M = matroids.Wheel(3)
sage: OS = M.orlik_solomon_algebra(QQ)
sage: OS.product_on_basis(frozenset(), 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 * G
-OS{1, 2} + OS{1, 4}
sage: G * G * G
OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}
sage: G * G * G
OS{0, 1, 2} - OS{0, 1, 4} + OS{0, 2, 3} + OS{0, 3, 4}
sage: G * G * G
-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)

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 coefficients

• M – a matroid

• G – a semigroup

• action_on_groundset – (optional) a function defining the action of G on the elements of the groundset of M; default is g(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 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: OSG = M.orlik_solomon_algebra(QQ, invariant=(G, on_groundset))
sage: OSG.basis()
Finite family {0: B, 1: B}
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 in G is trivial:

sage: x = OSG.an_element(); x
2*B + 2*B
sage: g = G.an_element(); g
(2,3)
sage: g * x
2*B + 2*B

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, 1: B}
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())^2
0
sage: 5 * OSG.basis()
5*B


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, 1: B, 2: B}
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])[: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    B    B    B    B    B    B    B]
[   B       0  2*B    B       0       0  2*B       0]
[   B -2*B       0    B       0 -2*B       0       0]
[   B   -B   -B       0    B       0       0       0]
[   B       0       0    B       0       0       0       0]
[   B       0 -2*B       0       0       0       0       0]
[   B  2*B       0       0       0       0       0       0]
[   B       0       0       0       0       0       0       0]


Note

The algebra structure only exists when the action on the groundset yeilds 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}$$.