Isomorphism of oriented matroids from a semigroup viewpoint

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 $L=\{0,+,-\}$ with product $\circ$ given by

$+\circ x=+$
$-\circ x=-$
$0\circ x=x=x\circ 0$

for all $x\in L$ . We define a unary operation, written $x\mapsto -x$ , that fixes $0$ and switches $+,-$ (note that negation is an order two automorphism).

If $E$ is any set (always finite in this post), then $L^E$ becomes a unary monoid via pointwise operations. The identity will be denoted $0$ and the involution by negation. Elements of $L^E$ are called covectors. If $x,y$ are covectors, then their separation set $S(x,y)$ consists of all $e\in E$ such that $x_e=-y_e\neq 0$ , that is it consists of the coordinates which have opposite signs. One should verify that if $e\notin S(x,y)$ , then $(x\circ y)_e=(y\circ x)_e$ and that $x,y$ commute if and only if $S(x,y)=\emptyset$ .

An oriented matroid $(E,\mathcal L)$ with ground set $E$ is a unary submonoid $\mathcal L\subseteq L^E$ satisfying the separation axiom:

if $x,y\in \mathcal L$ and $e\in S(x,y)$ , then there exists $z\in \mathcal L$ such that $z_e=0$ and, for all $f\notin S(x,y)$ , one has $z_f=(x\circ y)_f=(y\circ x)_f$ .

We call $\mathcal L$ 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 $0$ , $+$ or $-$ according to whether it is zero, positive or negative. Then there is a natural mapping $\tau\colon \mathbb R^n\to L^n$ that replaces each entry of a vector by its sign.

Now if $A$ is a hyperplane arrangement in a finite dimensional real vector space $V$ given as the zero sets of forms $f_1,\ldots, f_n\in V^*$ , then we have a linear mapping $\varphi\colon V\to \mathbb R^n$ given by $x\mapsto (f_1(x),\ldots,f_n(x))$ . The set of covectors $\mathcal L(A)=\tau(\varphi(V))$ turns out to satisfy the oriented matroid axioms.

Indeed, $0=\tau\varphi(0)$ and $\tau\varphi(-x)=-\tau\varphi(x)$ . If $x,y\in V$ and $\tau\varphi(x)=\tau\varphi(y)$ , then trivially $\tau\varphi(x)\circ \tau\varphi(y)=\tau\varphi(x)$ . Else choose $z$ on the line segment $[x,y]$ sufficiently close to $x$ so that $f(x)$ and $f(z)$ have the same sign whenever $f(x)\neq 0$ . This can be done because the $f_i$ are continuous. Then $\tau\varphi(x)\circ \tau \varphi(y)=\tau\varphi(z)$ , as is easily checked. Thus $\mathcal L(A)$ is a unary submonoid. To verify the separation axiom, let $x,y\in \mathcal L(A)$ with $x_i=-y_i\neq 0$ . Write $x=\tau\varphi(u)$ and $y=\tau\varphi(v)$ . Then $f_i$ takes on opposite signs at $u,v$ and so $f_i(w)=0$ for some $w\in [u,v]$ . Then one checks that taking $z=\tau\varphi(w)$ 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 $A$ is a hyperplane arrangement with associated zonotope $Z(A)$ , then a zonatopal tiling of $Z(A)$ is a polyhedral cell decomposition of $Z(A)$ such that each cell is a zonotope whose edges are parallel to edges of $Z(A)$ . The Bohne-Dress theorem states that zonotopal tilings of $Z(A)$ are in bijection with single-element liftings of the oriented matroid $\mathcal L(A)$ . 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 $(E,\mathcal L)$ is what you get by choosing $e\in E$ and changing the sign of each covector of $\mathcal L$ at $e$ . Obviously, this operation does not change the isomorphism class of the underlying unary monoid.

An element $e\in E$ is called a loop of an oriented matroid $(E,\mathcal L)$ if $x_e=0$ for all $e\in E$ . Obviously removing or adding loops results in an oriented matroid with an isomorphic underlying unary monoid. Two elements $e,f\in E$ are called parallel if either $x_e=y_e$ for all $x,y\in \mathcal L$ or $x_e=-y_e$ for all $x,y\in \mathcal L$ . Being parallel is clearly an equivalence relation. Adding or removing elements parallel to a given element of $E$ obviously does not change the isomorphism class of the underlying unary monoid.

An oriented matroid $(E',\mathcal L')$ is called a relabeling of $(E,\mathcal L)$ if it can be obtained from $(E,\mathcal L)$ by iteration of the following operations: adding/removing loops; adding/removing parallel elements; renaming the elements of $E$ .

Oriented matroids $(E,\mathcal L)$ and $(E',\mathcal L')$ 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 $(E,\mathcal L)$ and $(E',\mathcal L')$ are isomorphic if and only if $\mathcal L$ and $\mathcal L'$ 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 $(E,\mathcal L)$ up to isomorphism.

All unary monoids will have their identity denoted by $0$ and their unary operation by negation. Let us define a functional on a unary monoid $M$ to be a homomorphism of unary monoids $f\colon M\to L$ . The zero functional is defined in the obvious way. If $f\colon M\to L$ is a functional, then $-f\colon M\to L$ defined by $(-f)(m)=-f(m)$ is also a functional because negation is an automorphism. Clearly $-(-f)=f$ .

Define the spectrum $\widehat M$ of $M$ to be the set of non-zero functionals on $M$ and define the Gelfand transformation $\gamma\colon M\to L^{\widehat M}$ by $\gamma(m)(f)=f(m).$

If $(E,\mathcal L)$ is an oriented matroid, then for each $e\in E$ we have an associated functional $\widehat e\colon \mathcal L\to L$ given by $\widehat e(x)=x_e$ . Note that $\widehat e=0$ if and only if $e$ is a loop. One has that $e,f$ are parallel if and only if $\widehat e=\pm\widehat f$ .

The proof of Theorem 1 relies on the following result, which I conjectured in this mathoverflow question.

Lemma 1. Let $(E,\mathcal L)$ be an oriented matroid. If $f\in \widehat {\mathcal L}$ , then there exists $e\in E$ such that $f=\pm \widehat e$ .

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 $A$ be a hyperplane arrangement in $V$ . 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 $C,D$ is a sequence of adjacent chambers starting from $C$ and ending in $D$ . 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 $A$ is a polyhedral cone called a face of the arrangement. The faces are in bijection with the covectors of the corresponding oriented matroid $\mathcal L(A)$ (the signs tell you on which side of each hyperplane the face lies) and we do not distinguish between them notationally.

Now if $f$ is a functional on $\mathcal L(A)$ , then since it is non-zero and the chambers make up the minimal ideal of $\mathcal L(A)$ , it follows that $f$ does not vanish on any chamber. Fix a chamber $C$ . Then $f(C)=-f(-C)$ . Thus if we consider a gallery from $C$ to $-C$ , we find adjacent chambers $C',C''$ along this gallery with $f(C')=-f(C'')$ . The covectors associated to adjacent chambers differ in exactly one entry corresponding to the hyperplane $H_i$ separating them. Reorienting if necessary, we may assume that $f(C')=+$ , $f(C'')=-$ and that $C'$ belongs to the positive halfspace associated to $H_i$ and $C''$ to the negative halfspace. We claim that $f$ agrees with $\widehat{i}$ . Let $F=\overline{C'}\cap \overline{C''}$ be the facet separating $C',C''$ . Then the covector associated to $F$ has $0$ in position $i$ and agrees with $C',C''$ in all other positions. From $F\circ C'=C'$ and $F\circ C''=C''$ one obtains that $f(F)=0.$ If $F'$ is any other face, then $f(F')=f(F\circ F')$ and $F\circ F'=F,C',C''$ depending on whether $F'_i=0,+,-$ , respectively. From this one easily deduces that $f=\widehat{i}$ .

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 $M$ be a unary monoid. Then $M$ is isomorphic to the underlying unary monoid of an oriented matroid if and only if:

the Gelfand transformation $\gamma\colon M\to L^{\widehat{M}}$ is injective;
$\gamma(M)$ satisfies the separation axiom, that is, $(\widehat{M},\gamma(M))$ is an oriented matroid.

Moreover, if $(E,\mathcal L)$ is an oriented matroid, then $(E,\mathcal L)$ and $(\widehat{\mathcal L},\gamma(\mathcal L)))$ are isomorphic oriented matroids.

Proof. Trivially, if 1 and 2 are satisfied, then $M$ is isomorphic to the underlying unary monoid of an oriented matroid. If $(E,\mathcal L)$ is an oriented matroid, then the functionals $\widehat e$ with $e\in E$ separate points of $\mathcal L$ and so the Gelfand transformation is injective. Lemma 1 immediately implies that if we remove from $(\widehat{M},\gamma(M))$ exactly one element of each parallel class $\{\pm f\}$ , then, up to reorientation and renaming the elements, we get exactly the same oriented matroid as by removing from $(E,\mathcal L)$ all loops and all but one element from each parallel class. This completes the proof.

Isomorphism of oriented matroids from a semigroup viewpoint

About Benjamin Steinberg

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta

Isomorphism of oriented matroids from a semigroup viewpoint

Share this:

Like this:

About Benjamin Steinberg

Leave a Reply Cancel reply

Recent Posts

Archives

Categories

Meta