Combinatorial Methods in Linear Algebra

Question

There are a lot of examples of cases where linear algebra is used to solve problem in combinatorics. For example, the Friendship Theorem and Fisher's Inequality. In fact, there is a whole subject dedicated to this, namely Algebraic Combinatorics.

My question is what are some examples of combinatorics being used to solve linear algebra problems?

Answer 1

Well, the efficiency of the Coppersmith-Winograd multiplication algorithm relies on the existence of a sufficiently dense subset of $[1,N]$ that is a Sidon set. That is a well-studied problem in combinatorics: Rusza proved, for sufficiently large $N$s, the existence of a Sidon subset of $[1,N]$ with at least $N^{\sqrt{2}-1-\varepsilon}$ elements by exploiting the binary representations of the logarithms of some primes.

Answer 2

A little late reply, but aanother example is perhaps the Permanent Lemma, which is an application of the Combinatorial Nullstellensatz.