1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.