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.