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$ 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$ 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$ 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$ Aug 8, 2013 at 20:51
  • $\begingroup$ Yes I should assume a simple oriented matroid. $\endgroup$ Aug 9, 2013 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.