Oriented matroids are abstractions of hyperplane arrangements, or equivalently vector configurations. Let me recall the definition in terms of covectors.

Let $R=\lbrace 0,+,-\rbrace$ with the monoid structure given by the table $$\begin{array}{c|ccc}\circ& 0 &+ &-\\ \hline 0 & 0 &+&-\\ + & + &+ &+\\ - & -&-&-\end{array}$$ $R$ is the oriented matroid corresponding to the unique central arrangement in $\mathbb R$. More generally, $R^n$ corresponds to the arrangement of coordinate hyperplanes $x_i=0$ in $\mathbb R^n$. Elements of $R^n$ are called covectors.

We put $0=(0,\ldots,0)$ and $-(x_1,\ldots, x_n) = (-x_1,\ldots,-x_n)$ where negation is the automorphism of $R$ fixing $0$ and switching $+,-$. We view the structure $(R^n,\circ,x\mapsto -x)$ as a unary monoid (i.e., monoid with a distinguished unary operation).

If $x,y\in R^E$, then the separation set is $$S(x,y)=\lbrace e\in E\mid x_e=-y_e\neq 0\rbrace.$$

An oriented matroid with (finite) ground set E is a collection $\mathcal L\subseteq R^E$ of covectors such that

  1. $0\in \mathcal L$
  2. $x\in \mathcal L\iff -x\in \mathcal L$
  3. $x,y\in \mathcal L\implies x\circ y\in \mathcal L$
  4. 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 $z_f=(x\circ y)_f=(y\circ x)_f$ for $f\notin S(x,y)$.

Axioms 1-3 simply state that $\mathcal L$ is a unary submonoid of $R^E$. Axiom 4 is a statement about the geometry of hyperplane arrangements.

The motivating example is if $\mathcal A=\lbrace H_1,\ldots, H_n\rbrace$ is a hyperplane arrangement in $\mathbb R^d$ given by forms $f_i(x)=0$ for $i=1,\ldots,n$ then the set $\mathcal L$ of covectors encoding the signs of the entries of $(f_1(x),\ldots, f_n(x))$ with $x\in \mathbb R^d$ form an oriented matroid. The covectors are in bijection with the faces of the zonotope $Z=[-f_1,f_1]+\cdots+[-f_n,f_n]$ whose normal fan is $\mathcal A$ and the face poset of $Z$ is isomorphic to $\mathcal L$ with the ordering $x\leq y$ if $y\circ x=x$.

In particular, $R$ is the oriented matroid corresponding to the hyperplane $x=0$ in $\mathbb R$. Thus it makes sense to think of a homomorphism of unary monoids $\varphi\colon \mathcal L\to R$ as a functional on $\mathcal L$.

Question 1. If $\mathcal L\subseteq R^E$ is an oriented matroid, is it true that every non-zero functional is of the form $x\mapsto x_e$ for some $e\in E$?

If the answer to Question 1 is no, then I am interested in the following question.

Question 2. Let $M$ be a unary monoid. We can define $\widehat M$ to be the set of non-zero homomorphisms of unary monoids $\varphi\colon M\to R$. We can then define a Gelfand transformation $\gamma\colon M\to R^{\widehat M}$ by $\gamma(m)_e = e(m)$. Is it true that $M$ is isomorphic as a unary monoid to the set of covectors of an oriented matroid if and only if $\gamma(M)$ is the set of covectors of an oriented matroid on with ground set $\widehat M$?

If the answer to Question 1 is positive, then the answer to Question 2 is positive. Note that if $M$ is the set of covectors of an oriented matroid, then $\gamma$ is injective. I think it is not too difficult to describe unary monoids for which $\gamma$ is injective. (If we forget the unary operation, then I know which monoids have enough homomorphisms to R to separate points.)


2 Answers 2


I think the answer to your first question is "yes".

Oriented matroids can be realized topologically, and I am going to use that language. (This means is that I can pretend the oriented matroid is a hyperplane arrangement, provided I am a little careful.)

Let $\phi$ be a functional. Let the rank of the oriented matroid be $n$. I will show that if $\phi$ is zero on any $n$-dimensional cell, then it is zero everywhere, and otherwise there is some $e \in E$ such that $\phi=\phi_e$. The proof is by induction on $n$.

I claim first that there is an $(n-1)$-dimensional face on which $\phi$ is zero. The proof is by continuity: we can find a path starting in an n-dimensional cell on which $\phi$ is positive, and ending in a cell where $\phi$ is negative, going through only cells of dimension $n$ and $n-1$. If $X$ is an $n$-dimensional cell and $Y$ is an adjacent $n-1$-dimensional cell, then they cannot have opposite signs, since $Y\circ X=X$, but $- \circ + = -$. The same kind of argument shows that we can't have $\phi(X)=0$ but $\phi(Y)\ne 0$. Thus there is some $n-1$-dimensional cell, say $Y$, on which $\phi=0$.

Now consider some 1-dimensional cell, say $L$, incident with $Y$. We can consider the oriented matroid on the link of $L$ (this is generally called the "contraction"). $\phi$ is well-defined here. Induction now shows that $\phi$ is either zero on every cell incident to $L$, or else there is some $e$ such that $\phi/L=\phi_e/L$.

In the former case, we can work our way around the whole oriented matroid,establishing that $\phi=0$.

In the latter case, we will find that there is a consistent choice of $e$, such that for any cell adjacent to the $n-1$-cells of $e$, we have that $\phi$ and $\phi_e$ agree. If $\phi$ were zero anywhere else, then by induction it would be zero on some other $(n-1)$-dimensional cell, and thus also on all the cells of that hyperplane, but these two hyperplanes would meet, and that then would force $\phi$ to be zero everywhere (again by induction).

  • $\begingroup$ thanks for this. I will think about this. I was thinking along similar lines using the tope graph and an argument like what you have in the 4th paragraph. But I didn't think to use induction. $\endgroup$ Commented Aug 8, 2013 at 2:59
  • $\begingroup$ actually it seems to me that there should be an $e$ so that $\phi=\phi_e$ or $-\phi_e$, which is what I should really have asked for in my question I suppose. I think I almost see how to write this algebraically but will think more. $\endgroup$ Commented Aug 8, 2013 at 3:19
  • $\begingroup$ I was was able to translate your argument into tope graphs. Thanks so much. I was actually quite close because I knew the wall between two chambers with opposite signs under $\phi$ had to be sent to zero but didn't see how to move this around. $\endgroup$ Commented Aug 8, 2013 at 3:57

Here is an algebraic proof inspired by Hugh's argument and ideas I had before asking this question. Please upvote his answer. First I need to slightly correct Question 1 to ask if any non-zero functional $\phi$ is of the form $x\to x_e$ or $x\to -x_e$ (that is, one may need to reorient the matroid).

First of all, we may assume without loss of generality that $\mathcal L$ has no loops, i.e., that there is no $e$ with $x_e=0$ for all $x\in \mathcal L$. Covectors $x$ with $x_e\neq 0$ for all $e\in E$ are called topes. If $T$ is a tope, then $T\circ x =T$ for all $x\in \mathcal L$ and so if $\phi(T)=0$, we obtain $\phi(x)=0$ for all $x\in \mathcal L$. Thus $\phi(T)\neq 0$ for all topes $T$. If $\mathcal T$ is the set of topes, we have $\phi(\mathcal T)=\lbrace+,-\rbrace$ because $\mathcal T=-\mathcal T$.

The tope graph of $\mathcal L$ is the graph with $\mathcal T$ as the set of vertices and where there is an edge between $T$ and $T'$ if $|S(T,T')|=1$. It is known that the tope graph is connected and that the distance between two topes $T_1,T_2$ is exactly $|S(T_1,T_2)|$. Notice that there must be adjacent topes $T,T'$ with $\phi(T)=-\phi(T')$. Indeed, fix $T_0\in \mathcal T$ with $\phi(T_0)=+$ and let $p$ be a geodesic path from $T_0$ to $-T_0$. As $\phi(-T_0)=-$, there must be an edge of $p$ whose vertices have opposite signs.

Let $S(T,T')=e$. Replacing $\phi$ by $-\phi$ if necessary, we may assume $\phi(T)=+=T_e$ and $\phi(T') =-=T'_e$. Note that $T_f=T'_f$ for $f\neq e$. We claim that $\phi=\phi_e$, where $\phi_e(x)=x_e$. By axiom 4 there exists $z\in \mathcal L$ with $z_e=0$ and $z_f=T_f=T'_f$ for $f\neq e$. Note $z\circ T=T$ and $z\circ T'=T'$ and so $\phi(z)=0$.

Now let $x\in \mathcal L$. If $x_e=0$, then $z\circ x=z$ and so $\phi_e(x)=0=\phi(z)=\phi(z)\circ \phi(x)=\phi(x)$. If $x_e=+$, then $z\circ x=T$ and so $\phi_e(x)=+=\phi(T)=\phi(z)\circ \phi(x) =\phi(x)$. The same argument shows that if $x_e=-$, then $\phi(x)=-$. Thus $\phi=\phi_e$.

  • $\begingroup$ You're welcome! Your argument for "moving around" the wall on which phi is zero is much nicer than mine. I do think you also want to assume without loss of generality that there are no $e,e'$ parallel. Otherwise what you wrote in paragraph 3 is not literally true. $\endgroup$ Commented Aug 8, 2013 at 20:51
  • $\begingroup$ Yes I should assume a simple oriented matroid. $\endgroup$ Commented Aug 9, 2013 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.