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](http://mathworld.wolfram.com/PerfectGraphTheorem.html),  the [Frankl-Wilson theorem](http://gilkalai.wordpress.com/2009/05/21/extremal-combinatorics-vi-the-frankl-wilson-theorem/), and [Fischer's inequality](http://en.wikipedia.org/wiki/Fisher%27s_inequality).

Are there other good examples?