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.)