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

Are there other good examples?