Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, the Frankl-Wilson theorem, and Fisher's inequality.

Are there other good examples?

share|improve this question
    
@Francois- thanks for fixing the link. –  Tony Huynh Mar 3 '10 at 20:50
    
    
@Tony: No problem. URL encoding gets tricky. en.wikipedia.org/wiki/Percent-encoding –  François G. Dorais Mar 3 '10 at 20:56
    
You could probably find plenty by searching MathSciNet for papers with a combinatorics MSC code in the journal "Linear Algebra and its Applications". –  Douglas S. Stones Mar 3 '10 at 22:53
    
@Douglas - Thanks for the tip. Unfortunately, I am MathSciNetless for the next little while... –  Tony Huynh Mar 4 '10 at 2:25
add comment

15 Answers 15

up vote 21 down vote accepted

Some other examples are the Erdos-Moser conjecture (see R. Proctor, Solution of two difficult problems with linear algebra, Amer. Math. Monthly 89 (1992), 721-734), a few results at http://math.mit.edu/~rstan/312/linalg.pdf, and Lovasz's famous result on the Shannon capacity of a 5-cycle and other graphs (IEEE Trans. Inform. Theory 25 (1979), 1-7). For a preliminary manuscript of Babai and Frankl on this subject, see http://www.cs.uchicago.edu/research/publications/combinatorics.

share|improve this answer
    
Right, I thought immediately of the lovely manuscript by Babai and Frankl. Too bad it is not more easily available: I was lucky enough to take a combinatorics class from Babai in 1998 and thereby acquire a copy. I still have it! (Do you know why they have apparently lost interest in publishing it?) –  Pete L. Clark Mar 4 '10 at 0:12
    
I don't know why Babai and Frankl have lost interest in publishing it, but the preliminary manuscript is still readily available from the link above. –  Richard Stanley Mar 4 '10 at 0:49
    
@Richard - Much thanks! There is a lot of good information in your post. –  Tony Huynh Mar 4 '10 at 2:24
8  
I know someone tried to contact the UChicago department several times about getting that manuscript without luck, so here is a scanned copy: ifile.it/6wl3uv2 –  Steven Sam Mar 4 '10 at 17:05
3  
I've received a few emails about the link being dead, so here is a new one: ifile.it/wpolrs –  Steven Sam Jan 29 '12 at 5:11
show 1 more comment

Variants of the EKR Theorem offer a wide class of examples. This page has a nice list going, by the way.

A friend of mine once made the outrageous claim -- but hear me out -- that most "linear algebra proofs" in combinatorics are not truly using linear algebra. I think he was getting at such arguments' use of a preferential basis (think positive or $\{0,1\}$-matrices) when linear algebra should, in its purest sense, be basis-independent. In the standard proof of Fisher's inequality, you set up and compute a determinant, get that some matrix has full rank, and then conclude the inequality. But there are no linear transformations (debateable). He conceded that, for instance, Perron-Frobenius belongs inside "matrix analysis", but not "linear algebra"!

I argued a little, but then eventually kind of saw his point. I guess I now really appreciate the obvious (but fortunate) fact that inner products count something!

share|improve this answer
add comment

The polynomial method in combinatorial incidence geometry relies crucially on linear algebra to locate a non-trivial polynomial of controlled degree that vanishes at a specified set of points. A good example of the method in action is Dvir's proof of the finite field Kakeya conjecture, see e.g. http://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/ .

share|improve this answer
2  
This is also in Matousek's book mentioned by Gerry Myerson. –  Richard Stanley Mar 28 '12 at 0:26
add comment

There is also a book in Russian, Линейно-алгебраический метод в комбинаторике by Raygorodsky, that deals with this.

http://www.ozon.ru/context/detail/id/3625051/

share|improve this answer
add comment

This is a crosspost from Why linear algebra is fun!(or ?), suggested by Kevin O'Bryant. I think it's relevant here. Everything below is verbatim from the earlier post.

My favorite application of linear algebra, as introduced to me by Fan Chung, is Oddtown (which I learned about from a manuscript of Lovasz, but may not be due to him).

The $n$ residents of Oddtown love to form clubs; call the family of these $\mathcal{F}$. If $F_1$ and $F_2$ are in $\mathcal{F}$, then $|F_1|$ must be odd (this is Oddtown!) and $|F_1 \cap F_2|$ must be even unless $F_1 = F_2$ ($\scriptsize{go\;Oddtown?}$). The question is, how many clubs may these $n$ people form?

The answer (taken from Tibor Szabó's lecture notes) is this:

Let $\mathcal{F} = \{F_1,\ldots,F_m\} \subseteq 2^{[n]}$ be a set of clubs in Oddtown. Let $\mathbf{v}_i \in \{0,1\}^n$ be the characteristic vector of $F_i$; the $j$th coordinate is 1 iff $j \in F_i$.

Note that $\mathbf{v}_i^T \mathbf{v}_j = |F_i \cap F_j|$.

Now, $\mathbf{v}_1,\ldots,\mathbf{v}_m$ is independent over $\mathbb{F}^n_2$: if $\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m = 0$, then for each $i$ we have $$0 \;=\; (\lambda_1\mathbf{v}_1 + \cdots + \lambda_m\mathbf{v}_m)^T\mathbf{v}_i \;=\; \lambda_1\mathbf{v}_1^T\mathbf{v}_i + \cdots + \lambda_i\mathbf{v}_i^T\mathbf{v}_i + \ldots + \lambda_m\mathbf{v}_m^T\mathbf{v}_i \;=\; \lambda_i $$

Since $\mathbf{v}_1,\ldots,\mathbf{v}_m$ are linearly independent vectors over $\mathbb{F}^n_2$, $m \leq n$, and Oddtown can have at most $n$ clubs.

share|improve this answer
add comment

Here is an example I learned about this month: The edges of the complete graph cannot be partitioned into fewer than $n-1$ complete bipartite graphs. Apparently the only known proofs involve linear algebra.

share|improve this answer
    
I should add that Richard Brualdi, from whom I learned this, will be writing a book over the course of the next year largely on the connections between linear algebra and graph theory. –  Tracy Hall Jul 27 '10 at 13:27
4  
Recently Sundar Vishwanathan gave a combinatorial proof: arxiv.org/abs/1007.1553 –  Konrad Swanepoel Sep 7 '10 at 13:57
    
Nice proof in arxiv.org/abs/1007.1553 ! (Typo: $\sum_{i=1}^n$ should be $\sum_{i=1}^{n-2}$ in the last formula of the proof; also, $k > n^n$ can just as well be replaced by $k > n^{n-1}$.) Can something similar be done with this problem: artofproblemsolving.com/Forum/viewtopic.php?f=41&t=271585 ? –  darij grinberg Mar 27 '12 at 23:05
add comment

Hoffman and Singleton proved that a regular graph with girth 5 and diameter 2 has to have degree 2, 3, 7, or 57. If I recall correctly, the proof used spectral properties of the adjacency matrix to produce some non-polynomial equation for which these were the integer solutions.

There are unique examples of the first three cases: degree 2 is a pentagon, degree 3 is the Petersen graph, and degree 7 is the Hoffman-Singleton graph. The existence of the degree 57 graph is still open (as far as I know).

share|improve this answer
add comment

The AMS has a new book out, Jiri Matousek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra. Info at http://www.ams.org/bookstore-getitem/item=STML-53

"This volume contains a collection of clever mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms."

share|improve this answer
1  
Thanks Gerry. The book looks good, I'll probably pick it up. I really enjoyed Using the Borsuk-Ulam Theorem by the same author. –  Tony Huynh Mar 10 '10 at 21:28
add comment

It's not quite what you have asked for, but very close:

Some facts - and proofs! - in combinatorics can be interpreted as linear algebra over the "field with one element". In this very nicely written article Henry Cohn gives a concrete meaning to this and shows how to make a proof from linear algebra into a proof about a combinatorical statement by rephrasing it into axiomatic projective geometry.

(by the way: Lior's answer is an instance of linear algebra over field with one element)

share|improve this answer
    
See also this blog post by Peter Cameron: cameroncounts.wordpress.com/2011/07/20/… –  Felix Goldberg Mar 23 at 14:16
add comment

Here is a link to a Tricki article that has some further examples.

http://www.tricki.org/article/Dimension_arguments_in_combinatorics

share|improve this answer
    
This article is very nice, for the trick and also the exposition. Thanks!. A curiosity, who is its author? Sorry, but the author isn't listed at the site. Maybe you? :-) –  Anonymous Mar 4 '10 at 22:14
    
Actually yes ... It's possible to see who Tricki articles are by if you look at their revision history. –  gowers Mar 5 '10 at 11:39
add comment

The following is a good illustration:

Let $P$ be a finite set ("points"), and let $L\subset 2^P$ ("lines") be such that distinct lines intersect in at most one point and any two distinct points are contained in a line. Let $V$ be the real vector space with basis $P$, $W$ the vector space with basis $L$. There are natural linear maps $T\colon V\to W$ and $S\colon W\to V$ mapping every point to the sum of the lines containing it, and every line to the sum of the points in it. Then $ST = J+D-I$ where $J$ is the all-ones matrix (through every two distinct points there is a unique line), $I$ the identity matrix and $D$ is diagonal with entries counting the lines through each point.

Assume that not all points are collinear. Then all the diagonal entries of $D-I$ are at least one; it is then easy to verify that the determinant of $ST$ is positive, and conclude that $|L| \geq |P|$.

share|improve this answer
add comment

These references may be more shallow than you desired, but they are both fun and lucid.

1) Noga Alon's Tools From Higher Algebra contains many things (or at least references to those things) that only require linear algebra at heart, such as Rayleigh's Principle.

2) A Course in Combinatorics by van Lint and Wilson is laced with gems in self-contained sections, such that each page is an adventure. You'll find Lots of techniques here that only require linear algebra, including the awkward-looking "interlacing property" of eigenvalues that have popped up way too much for me to ignore by now.

My favorite is actually the aforementioned Babai/Frankl manuscript, which is still very readable and useful. In theory you can still get it; in practice more difficult. First time I tried to order it I didn't get a reply at all.

-Yan

share|improve this answer
1  
Thanks. The book by van Lint and Wilson is indeed one of my favorites. You're quite right that it's hard to ignore (no matter how hard I try) interlacing eigenvalues. –  Tony Huynh Mar 10 '10 at 16:17
add comment

There is nice linear-algebra proof of the following result in discreet geometry:

Any $n$ lines in general position cut from the plane at least $n-2$ triangles.

See А. Я. Белов Об одной задаче комбинаторной геометрии (thanks to Arseny and Garry). You will find there more examples of such problems.

share|improve this answer
1  
Alexey Kanel-Belov –  akopyan Mar 4 '10 at 3:29
3  
Perhaps the paper in question is A problem in combinatorial geometry, Uspekhi Mat Nauk 47 (1992), no. 3 (285), 151-152, translation in Russian Math Surveys 47 (1992), no. 3, 167-168, MR 93h:52016. Maybe it's also in A Kanel'-Belov and A Kovaldzhi, Taking on triangles: in search of answers between the lines, Quantum 11 (2001), no. 4, 10-16. –  Gerry Myerson Mar 4 '10 at 4:02
add comment

The Lindstrom-Gessel-Viennot Lemma uses the reflection principle on $S_n$ to say that the number of nonintersecting families of lattice paths in the plane equals the determinant of a matrix so that the $i,j$-th entry is the number of paths from the $i$th source to the $j$th sink.

This was not a linear algebra proof. However, this determinant can be used to enumerate plane partitions inside an $a\times b \times c~$ box, to $q$-enumerate plane partitions by weight, and to count domino tilings of an Aztec diamond. The resulting determinants can be manipulated and evaluated in ways which are natural in linear algebra, but not as clear on the objects, such as factoring the matrices. These enumerations can be viewed as applications of simple results in linear algebra.

Notes:

Lattice paths are defined and the sources and sinks are restricted so that any nonintersecting family must be an even permutation from source indices to sink indices, usually the identity.

Others independently discovered this result, e.g., Karlin and McGregor.

The same idea applies to Brownian motion.

share|improve this answer
add comment

The proof that every $n\times n$ semi-magic square can be written as an integer linear combination of $n^2-2n+2$ permutation matrices.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.