Take a finite set of vectors in some vector space. Call a set independent if the corresponding vectors are linearly independent. The collection of all independent sets is denoted ; what properties must it have? Well, it must be a matroid:
A matroid with ground set is a nonempty collection of subsets which is both hereditary and augmentable.
- Hereditary: if , then any subset of is in
- Augmentable: if and has fewer elements than , then can take an element from and still remain in .
The augmentation property brings to mind wealth redistribution (at least if you grew up in the USSR). Anyway, it is fairly obvious that any collection that arises from vectors is a matroid. Is the converse true? Not obvious at all.
Behold the Fano plane, the smallest projective plane in existence: 7 points, 7 lines, any two lines meet at one point, through any two points there is a unique line.
The Fano matroid has these 7 vertices as the ground set. A set of vertices is independent if it has at most three points and is not a line. The hereditary property is clear. The augmentation isn’t hard either: given a 2-point set , let be the line through it; since has 3 points and is not a line, it must contain a point outside of , and this is the point we add to .
Can the Fano matroid be realized by 7 vectors in a Euclidean space? Guess what… no.
Suppose we do have such a set of 7 vectors. Then they span a 3-dimensional space, since there is no linearly independent subset with 4 vectors. The three vertices of the triangle are independent, and we may assume they are realized by the standard basis vectors . Enumerate the other points/vectors so that is the midpoint opposite for . Observe that is a linear combination of , etc. Thus, are the columns of the matrix
But wait, there’s more! Denote and observe that the linear dependence of forces to be a scalar multiple of . Similarly for . So the matrix must be of the form
But wait, there’s even more! The vectors are also dependent (that inscribed circle is actually a line). The determinant of the 4,5,6 columns is . Can any of be zero? No, because that would make a linear combination of two of , which is not supposed to happen. Can any of be zero? No, because that would create a zero vector, and all of the 1- and 2-subsets are independent. So, the Fano matroid cannot be realized by vectors…
unless 2=0. Over there is no problem:
(P.S. All of this stuff is in Whitney’s 1935 paper that introduced matroids.)