Bases

Sometimes you have to make things more complicated in order to make them simpler.

My old friend Aiden Bruen visited this week, and told me about a paper by him and his son Trevor which has just appeared in the Mathematical Intelligencer on the subject of bases.

Given a spanning set of n vectors in an r-dimensional vector space, we know that the set contains at least one basis. One of the main questions they tackled was: can one put a sensible lower bound on the number of bases contained in the set? Two big theorems in the paper assert that, if all the vectors are non-zero, there are at least nr+1 bases, the extremal case being when nr+1 of the vectors lie in a 1-dimensional subspace; and, if no vector in the set is a scalar multiple of any other, then the number is at least (nr+2 choose 2), the extremal case being when nr+2 of the vectors lie in a 2-dimensional subspace. (The hypothesis in this case is that the vectors represent distinct points in the projective space; so, in the case when r = 3, for example, we are maximising the number of triangles formed by n points in the projective plane.)

The proofs of the two theorems were moderately complicated and completely independent. But there is an obvious generalisation: introduce a new parameter s, and require that any s of the vectors are linearly independent. The Bruens’ cases were s = 1 and s = 2.

Introducing the parameter s greatly simplifies the argument, since it is available for induction along with the other two parameters. The general statement, whose proof takes only a page, is that a spanning set of n vectors in an r-dimensional vector space, any s of which are linearly independent, contain at least (nr+s choose s) bases; equality implies that nr+s of the vectors are contained in an s-dimensional subspace.

The other simplification is more conceptual than technical. The result holds for arbitrary matrods, not just for representable ones as suggested here. It states that an n-element matroid with rank r, in which any s-element set is independent, has at least (nr+s choose s) bases; equality holds if and only if the matroid is the direct sum of a uniform matroid Unr+s,s and a free matroid on rs elements.

The advantage of proving it in the case of matroids is that the main tool, deletion and contraction, is readily to hand; contraction in a vector space involves taking a quotient space which is less easy to think about.

The other advantage of the matroid formulation is that in the vector space case we have to wonder about whether, for example, there exist m points in an s-dimensional space, any s of which form a basis. This important question, closely related to the existence of maximum-distance-separable codes and a problem of Segre (with which Aiden’s is one of the names most closely associated), is from our point of view quite separate from the main theorem.

The matroid formulation suggests other questions. The bound holds for any matroid; but, for example, it cannot be met for graphic matroids except in very special cases. (From one point of view, this is because graphic matroids are representable over any field whereas sets of vectors of the type just discussed only exist over sufficiently large fields.) However, the question has a natural translation into graph-theoretic terms. What is the smallest number of spanning trees in a connected graph with t vertices and n edges (with t = r+1 in terms of the parameters given above) whose girth is greater than s?

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition, mathematics, open problems and tagged , , . Bookmark the permalink.

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