I'm looking for the reference of the following fact from oriented matroid theory. This must be known; in fact, I think it is in the book "Oriented Matroids" by Björner et al., but I can't locate it.

Let $A$ be a matrix. Consider the possible sign patterns in the kernel and rowspace: $$K = \text{sign}(\ker (A)) \qquad L = \text{sign}(\text{rowspace} (A)).$$ (Convention: The kernel is the left kernel and the rowspace is the linear span of the rows.)

Lemma. Let $\pi\in L$, then for all $\sigma \in K$, there is an entry where $\pi$ and $\sigma$ have the same nonzero sign if and only if there is an entry where $\pi$ and $\sigma$ have opposite nonzero signs.

This smells like oriented matroid duality, doesn't it?


1 Answer 1


After asking this question on mathoverflow (the corresponding question is deleted now) it was pointed out in a comment that the proof is really simple.

Proof. Let $p\in\text{rowspace}(A)$ and $s\in\ker(A)$ be two vectors realizing $\pi$ and $\sigma$. Since $$p\cdot s = \sum_i p_is_i = 0,$$ whenever there is a positive summand, there must also be a negative summand.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .