This is in some sense a sequel to this post. Basically, I want to show that the somewhat awkward, in my opinion, definition of isomorphism of oriented matroids found, for example, here can be interpreted as isomorphism of underlying unary monoids. Moreover, we will show that a unary monoid is the underlying monoid of an oriented matroid if and only if a certain “Gelfand” representation by covectors is faithful and yields an oriented matroid.
First let me recall the definition of an oriented matroid in terms of covectors. Let with product given by
for all . We define a unary operation, written , that fixes and switches (note that negation is an order two automorphism).
If is any set (always finite in this post), then becomes a unary monoid via pointwise operations. The identity will be denoted and the involution by negation. Elements of are called covectors. If are covectors, then their separation set consists of all such that , that is it consists of the coordinates which have opposite signs. One should verify that if , then and that commute if and only if .
An oriented matroid with ground set is a unary submonoid satisfying the separation axiom:
- if and , then there exists such that and, for all , one has .
We call the underlying unary monoid of the oriented matroid.
The primary example comes from hyperplane arrangements, as discussed in this post. Let us recall here the construction of the set of covectors associated to an arrangement. Let us agree that the sign of a real number is , or according to whether it is zero, positive or negative. Then there is a natural mapping that replaces each entry of a vector by its sign.
Now if is a hyperplane arrangement in a finite dimensional real vector space given as the zero sets of forms , then we have a linear mapping given by . The set of covectors turns out to satisfy the oriented matroid axioms.
Indeed, and . If and , then trivially . Else choose on the line segment sufficiently close to so that and have the same sign whenever . This can be done because the are continuous. Then , as is easily checked. Thus is a unary submonoid. To verify the separation axiom, let with . Write and . Then takes on opposite signs at and so for some . Then one checks that taking satisfies the requirements of the separation axiom.
Oriented matroids which come from hyperplane arrangements are called realizable. Not all oriented matroids are realizable. Non-realizable matroids are still interesting to people in discrete geometry. One reason is because of the Bohne-Dress theorem.
The reader should refer back to this post for the definition of a zonotope and the connection with hyperplane arrangements. If is a hyperplane arrangement with associated zonotope , then a zonatopal tiling of is a polyhedral cell decomposition of such that each cell is a zonotope whose edges are parallel to edges of . The Bohne-Dress theorem states that zonotopal tilings of are in bijection with single-element liftings of the oriented matroid . Roughly speaking a single-element lifting of an oriented matroid is an oriented matroid obtained by adding one element to the ground set and whose contraction at that element returns the original matroid.
Now that we have the background out of the way, let me explain how isomorphism of oriented matroids is defined.
A reorientation of an oriented matroid is what you get by choosing and changing the sign of each covector of at . Obviously, this operation does not change the isomorphism class of the underlying unary monoid.
An element is called a loop of an oriented matroid if for all . Obviously removing or adding loops results in an oriented matroid with an isomorphic underlying unary monoid. Two elements are called parallel if either for all or for all . Being parallel is clearly an equivalence relation. Adding or removing elements parallel to a given element of obviously does not change the isomorphism class of the underlying unary monoid.
An oriented matroid is called a relabeling of if it can be obtained from by iteration of the following operations: adding/removing loops; adding/removing parallel elements; renaming the elements of .
Oriented matroids and are considered isomorphic if one can be obtained from the other by a series of relabellings and reorientations. Obviously isomorphic oriented matroids have isomorphic underlying unary monoids. The point of this post is to sketch a proof of the converse.
Theorem 1. Oriented matroids and are isomorphic if and only if and are isomorphic unary monoids.
It seems to me that this is a more concise and natural definition of isomorphism in this context. I have not been able to find it in the literature and it is not 100% trivial
The key idea is to show that “being” the underlying unary monoid of an oriented matroid is in some sense intrinsic in that one can recover up to isomorphism.
All unary monoids will have their identity denoted by and their unary operation by negation. Let us define a functional on a unary monoid to be a homomorphism of unary monoids . The zero functional is defined in the obvious way. If is a functional, then defined by is also a functional because negation is an automorphism. Clearly .
Define the spectrum of to be the set of non-zero functionals on and define the Gelfand transformation by
If is an oriented matroid, then for each we have an associated functional given by . Note that if and only if is a loop. One has that are parallel if and only if .
The proof of Theorem 1 relies on the following result, which I conjectured in this mathoverflow question.
Lemma 1. Let be an oriented matroid. If , then there exists such that .
A geometric argument was sketched by Hugh Thomas in his answer based on induction on rank and using contractions of oriented matroids. I extracted the key ingredient of his proof to construct an algebraic proof using tope graphs in my answer. The interested reader can find the details here. I will sketch the proof for realizable oriented matroids (i.e., hyperplane arrangements) here. The general case follows the same argument, but one must first replace the oriented matroid by an isomorphic one which is simple (i.e., has no loops or parallel elements) and then replace the word“chamber” by “tope”.
Let be a hyperplane arrangement in . Then the complement of the arrangement is a finite union of polyhedral cones called chambers. Two chambers are adjacent if they are separated by a single hyperplane. A gallery between two chambers is a sequence of adjacent chambers starting from and ending in . A key fact about hyperplane arrangements is that any two chambers are connected by a gallery. More generally, each non-empty intersection of halfspaces of the hyperplanes from is a polyhedral cone called a face of the arrangement. The faces are in bijection with the covectors of the corresponding oriented matroid (the signs tell you on which side of each hyperplane the face lies) and we do not distinguish between them notationally.
Now if is a functional on , then since it is non-zero and the chambers make up the minimal ideal of , it follows that does not vanish on any chamber. Fix a chamber . Then . Thus if we consider a gallery from to , we find adjacent chambers along this gallery with . The covectors associated to adjacent chambers differ in exactly one entry corresponding to the hyperplane separating them. Reorienting if necessary, we may assume that , and that belongs to the positive halfspace associated to and to the negative halfspace. We claim that agrees with . Let be the facet separating . Then the covector associated to has in position and agrees with in all other positions. From and one obtains that If is any other face, then and depending on whether , respectively. From this one easily deduces that .
We can now prove Theorem 2, which has Theorem 1 as an immediate consequence because it implies that an oriented matroid can be reconstructed up to isomorphism from its underlying unary monoid.
Theorem 2. Let be a unary monoid. Then is isomorphic to the underlying unary monoid of an oriented matroid if and only if:
- the Gelfand transformation is injective;
- satisfies the separation axiom, that is, is an oriented matroid.
Moreover, if is an oriented matroid, then and are isomorphic oriented matroids.
Proof. Trivially, if 1 and 2 are satisfied, then is isomorphic to the underlying unary monoid of an oriented matroid. If is an oriented matroid, then the functionals with separate points of and so the Gelfand transformation is injective. Lemma 1 immediately implies that if we remove from exactly one element of each parallel class , then, up to reorientation and renaming the elements, we get exactly the same oriented matroid as by removing from all loops and all but one element from each parallel class. This completes the proof.