Many special cases of the [Cerny conjecture][1] in automata theory have been proved using linear algebra, or really representations of monoids, that do not have known combinatorial proofs.  The conjecture states that an $n$-state synchronizing automaton has a synchronizing word of length at most $(n-1)^2$.  In purely mathematical terms the conjecture states that given a set of transformations of an $n$-element set, of which some composition  (with repetitions allowed) is a constant map, then some composition of length at most $(n-1)^2$ is a constant map. 

Many proof analyze the corresponding linear representation of the monoid generated by these transformations. My favorite example is the paper of [Dubuc][2], which proves the conjecture is true if one of the transformations is an $n$-cycle. Cerny had already shown that the bound can be reached by examples with an $n$-cycle. Dubuc uses the nature of representations of the cyclic group over the rationals (or if you like uses minimal polynomials). But there are many more such examples.


  [1]: https://en.wikipedia.org/wiki/Synchronizing_word
  [2]: http://www.numdam.org/item/ITA_1998__32_1-3_21_0/