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.

  1. Hereditary: if A\in \mathcal{I}, then any subset of A is in \mathcal{I}
  2. 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.

Fano Plane

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…

unless 2=0. Over \mathbb F_2 there is no problem:

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

(P.S. All of this stuff is in Whitney’s 1935 paper that introduced matroids.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s