Linear Algebra Proofs in Combinatorics? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:01:45Z http://mathoverflow.net/feeds/question/17006 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics Linear Algebra Proofs in Combinatorics? Tony Huynh 2010-03-03T20:39:42Z 2012-03-27T18:30:22Z <p>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) <a href="http://mathworld.wolfram.com/PerfectGraphTheorem.html" rel="nofollow">perfect graph theorem</a>, the <a href="http://gilkalai.wordpress.com/2009/05/21/extremal-combinatorics-vi-the-frankl-wilson-theorem/" rel="nofollow">Frankl-Wilson theorem</a>, and <a href="http://en.wikipedia.org/wiki/Fisher%27s_inequality" rel="nofollow">Fisher's inequality</a>.</p> <p>Are there other good examples?</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17012#17012 Answer by Richard Stanley for Linear Algebra Proofs in Combinatorics? Richard Stanley 2010-03-03T21:09:44Z 2010-03-03T21:09:44Z <p>Some other examples are the Erdos-Moser conjecture (see R. Proctor, Solution of two difficult problems with linear algebra, <em>Amer. Math. Monthly</em> <strong>89</strong> (1992), 721-734), a few results at <a href="http://math.mit.edu/~rstan/312/linalg.pdf" rel="nofollow">http://math.mit.edu/~rstan/312/linalg.pdf</a>, and Lovasz's famous result on the Shannon capacity of a 5-cycle and other graphs (<em>IEEE Trans. Inform. Theory</em> <strong>25</strong> (1979), 1-7). For a preliminary manuscript of Babai and Frankl on this subject, see <a href="http://www.cs.uchicago.edu/research/publications/combinatorics" rel="nofollow">http://www.cs.uchicago.edu/research/publications/combinatorics</a>.</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17019#17019 Answer by Gerry Myerson for Linear Algebra Proofs in Combinatorics? Gerry Myerson 2010-03-03T22:33:22Z 2010-03-03T22:33:22Z <p>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. </p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17024#17024 Answer by Douglas Zare for Linear Algebra Proofs in Combinatorics? Douglas Zare 2010-03-03T23:13:02Z 2010-03-03T23:35:56Z <p>The <a href="http://qchu.wordpress.com/2009/11/17/the-lindstrom-gessel-viennot-lemma/" rel="nofollow">Lindstrom-Gessel-Viennot Lemma</a> 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. </p> <p>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.</p> <p>Notes: </p> <p>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.</p> <p>Others independently discovered this result, e.g., Karlin and McGregor.</p> <p>The same idea applies to Brownian motion. </p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17029#17029 Answer by Anton Petrunin for Linear Algebra Proofs in Combinatorics? Anton Petrunin 2010-03-04T00:00:05Z 2010-03-04T04:33:16Z <p>There is nice linear-algebra proof of the following result in discreet geometry:</p> <blockquote> <p>Any $n$ lines in general position cut from the plane at least $n-2$ triangles.</p> </blockquote> <p>See А. Я. Белов <a href="http://www.mathnet.ru/php/journal.phtml?wshow=paper&amp;jrnid=rm&amp;paperid=4516&amp;year=1992&amp;volume=47&amp;issue=3&amp;fpage=151&amp;lpage=152&amp;option_lang=rus" rel="nofollow">Об одной задаче комбинаторной геометрии</a> (thanks to Arseny and Garry). You will find there more examples of such problems.</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17060#17060 Answer by yanzhang for Linear Algebra Proofs in Combinatorics? yanzhang 2010-03-04T05:51:11Z 2010-03-04T05:51:11Z <p>These references may be more shallow than you desired, but they are both fun and lucid.</p> <p>1) Noga Alon's <em>Tools From Higher Algebra</em> contains many things (or at least references to those things) that only require linear algebra at heart, such as Rayleigh's Principle.</p> <p>2) <em>A Course in Combinatorics</em> 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.</p> <p>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.</p> <p>-Yan</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17068#17068 Answer by Lior Silberman for Linear Algebra Proofs in Combinatorics? Lior Silberman 2010-03-04T09:06:58Z 2010-03-04T09:06:58Z <p>The following is a good illustration:</p> <p>Let $P$ be a finite set ("points"), and let <code>$L\subset 2^P$</code> ("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.</p> <p>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 <code>$|L| \geq |P|$</code>.</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17076#17076 Answer by gowers for Linear Algebra Proofs in Combinatorics? gowers 2010-03-04T11:56:32Z 2010-03-04T11:56:32Z <p>Here is a link to a Tricki article that has some further examples.</p> <p><a href="http://www.tricki.org/article/Dimension_arguments_in_combinatorics" rel="nofollow">http://www.tricki.org/article/Dimension_arguments_in_combinatorics</a></p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17175#17175 Answer by Peter Arndt for Linear Algebra Proofs in Combinatorics? Peter Arndt 2010-03-05T12:08:58Z 2010-03-05T12:08:58Z <p>It's not quite what you have asked for, but very close:</p> <p>Some facts - and proofs! - in combinatorics can be interpreted as linear algebra over the "field with one element". In <a href="http://arxiv.org/abs/math/0407093" rel="nofollow">this</a> 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.</p> <p>(by the way: Lior's answer is an instance of linear algebra over field with one element)</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17687#17687 Answer by Gerry Myerson for Linear Algebra Proofs in Combinatorics? Gerry Myerson 2010-03-10T02:09:38Z 2010-03-10T02:09:38Z <p>The AMS has a new book out, Jiri Matousek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra. Info at <a href="http://www.ams.org/bookstore-getitem/item=STML-53" rel="nofollow">http://www.ams.org/bookstore-getitem/item=STML-53</a></p> <p>"This volume contains a collection of clever mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms."</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/17689#17689 Answer by S. Carnahan for Linear Algebra Proofs in Combinatorics? S. Carnahan 2010-03-10T02:41:57Z 2010-03-10T02:41:57Z <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Hoffman-Singleton_graph" rel="nofollow">Hoffman-Singleton graph</a>. The existence of the degree 57 graph is still open (as far as I know).</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/33505#33505 Answer by Tracy Hall for Linear Algebra Proofs in Combinatorics? Tracy Hall 2010-07-27T13:22:40Z 2010-07-27T13:22:40Z <p>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.</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/34132#34132 Answer by Eric Tressler for Linear Algebra Proofs in Combinatorics? Eric Tressler 2010-08-01T18:18:45Z 2010-08-01T18:27:26Z <p>This is a crosspost from <a href="http://mathoverflow.net/questions/33911/" rel="nofollow">http://mathoverflow.net/questions/33911/</a>, suggested by Kevin O'Bryant. I think it's relevant here. Everything below is verbatim from the earlier post.</p> <p>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).</p> <p>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?</p> <p>The answer (taken from <a href="http://discretemath.imp.fu-berlin.de/Combinatorics_2010/covered-material.pdf" rel="nofollow">Tibor Szab&oacute;'s lecture notes</a>) is this:</p> <p>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$.</p> <p>Note that $\mathbf{v}_i^T \mathbf{v}_j = |F_i \cap F_j|$.</p> <p>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$$</p> <p>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.</p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/92371#92371 Answer by Felix Goldberg for Linear Algebra Proofs in Combinatorics? Felix Goldberg 2012-03-27T12:57:52Z 2012-03-27T12:57:52Z <p>There is also a book in Russian, Линейно-алгебраический метод в комбинаторике by Raygorodsky, that deals with this. </p> <p><a href="http://www.ozon.ru/context/detail/id/3625051/" rel="nofollow">http://www.ozon.ru/context/detail/id/3625051/</a></p> http://mathoverflow.net/questions/17006/linear-algebra-proofs-in-combinatorics/92400#92400 Answer by Terry Tao for Linear Algebra Proofs in Combinatorics? Terry Tao 2012-03-27T18:30:22Z 2012-03-27T18:30:22Z <p>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. <a href="http://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/" rel="nofollow">http://terrytao.wordpress.com/2008/03/24/dvirs-proof-of-the-finite-field-kakeya-conjecture/</a> .</p>