Fact:   Start with $V$ a subspace of $\mathbb R^n$. Take the set of all supports of vectors in $V$. Throw out $\emptyset$. You now have the dependent sets of some matroid.

Not sure you believe me? Or just want to get your hands on the independent sets? (If you tell people that you have a matroid, they always ask you for the independent sets. How can you blame them?) Okay, no problem.

Choose a basis for $V^\perp$ and take those vectors as the rows of a matrix $A$. The sets of indices corresponding to linearly independent columns give the independent sets of the matroid. (A set of indices corresponds to linearly dependent columns, of course, exactly when it can be matched up with nonzero scalars so as to give a vector orthogonal to every row, i.e., a vector in $V$. This also shows that it doesn't matter which basis you choose.)

It follows from the above that the matroids that arise in this fashion are precisely the ones that are representable over $\mathbb R$.

I like this way of thinking about representability. But I've never seen it presented this way in the literature. Why not? (Maybe it has to do with how I seem to be relying on a nice Euclidean inner product?) This leads me to a couple of questions.

  1. Is the fact I stated above presented in any reference anywhere? I would greatly appreciate it if anyone could point me in the direction of one.
  2. Is it the case that the fact I stated above remains true when $\mathbb R$ is replaced by any field? If so, does it characterize representability over any field?

EDIT: I just realized that it's not difficult to prove that the above fact does hold over any field; I believe one can simply show that those support sets which are minimal with respect to $\subseteq$ satisfy the circuit axioms, and that's enough. So my main question here is whether or not this stills serves to characterize representability over other fields.

  • $\begingroup$ Something's wrong here, if I interpret 'the above fact does hold over any field' as claiming that for any subspace $V\subseteq F^n$, the set of supports of nonzero vectors in $V$ forms the dependent sets of a matroid. The obvious counterexample is the space of vectors of even parity in $\mathbb{F}_2^n$, for which the set of supports is not upwards closed. So what exactly is the correct statement? $\endgroup$ – Tobias Fritz Jul 30 '17 at 20:02

This is just taking the dual of the usual definition of representability: a representable matroid over a field $k$ is given by $n$ vectors in a vector space $V$, that is by a map $k^n\to V$. If you dualize, you get a map $V^* \to k^n$ (indeed using the inner product on $k^n$), and the description you gave. I think it's a little more standard to think about the hyperplanes in $V$ where the coordinates vanish: a set is independent if the intersection of the hyperplanes is transverse (i.e. its codimension is the same as the number of hyperplanes).

I think this interpretation is considered quite standard by people in matroid theory and hyperplane arragnements; for example, Section 1.9 in these notes of Reiner or Section 3 of these notes by Stanley. Certainly I tend to think more about matroids in terms of hyperplane arrangements, rather than vectors.

  • $\begingroup$ This does seem to be a useful perspective to keep in mind. Thanks! $\endgroup$ – Louis Deaett Jun 15 '15 at 22:00

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.