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 (couldn't get the wikipedia link to work).

Are there other good examples?