Linear independence, matroids, and fun with Fano

Take a finite set of vectors $v_1,\dots,v_n$ in some vector space. Call a set $A\subset \lbrace 1,2,\dots,n\rbrace$ independent if the corresponding vectors are linearly independent. The collection of all independent sets is denoted $\mathcal{I}$ ; what properties must it have? Well, it must be a matroid:

A matroid with ground set $E$ is a nonempty collection of subsets $\mathcal{I}\subseteq 2^E$ which is both hereditary and augmentable.

Hereditary: if $A\in \mathcal{I}$ , then any subset of $A$ is in $\mathcal{I}$
Augmentable: if $A,B\in \mathcal{I}$ and $A$ has fewer elements than $B$ , then $A$ can take an element from $B$ and still remain in $\mathcal{I}$ .

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 $\mathcal{I}$ 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 $A$ , let $L$ be the line through it; since $B$ has 3 points and is not a line, it must contain a point outside of $L$ , and this is the point we add to $A$ .

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 $v_1,v_2,v_3$ . Enumerate the other points/vectors $v_4,\dots,v_7$ so that $v_{j+3}$ is the midpoint opposite $v_j$ for $j=1,2,3$ . Observe that $v_4$ is a linear combination of $v_2,v_3$ , etc. Thus, $v_1,\dots, v_7$ are the columns of the matrix

$\displaystyle M= \begin{pmatrix} 1&0&0&0&*&*&* \\ 0&1&0&*&0&*&* \\ 0&0&1&*&*&0&* \end{pmatrix}$

But wait, there’s more! Denote $v_7=(x,y,z)^T$ and observe that the linear dependence of $v_1,v_4,v_7$ forces $v_4$ to be a scalar multiple of $(0,y,z)^T$ . Similarly for $v_5,v_6$ . So the matrix $M$ must be of the form

$\displaystyle M= \begin{pmatrix} 1&0&0&0&bx&cx&x \\ 0&1&0&ay&0&cy&y \\ 0&0&1&az&bz&0&z \end{pmatrix}$

But wait, there’s even more! The vectors $v_4,v_5,v_6$ are also dependent (that inscribed circle is actually a line). The determinant of the 4,5,6 columns is $2abcxyz$ . Can any of $x,y,z$ be zero? No, because that would make $v_7$ a linear combination of two of $v_1,v_2,v_3$ , which is not supposed to happen. Can any of $a,b,c$ 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…