Examples of combinatorial/probabilistic proofs of theorems in linear algebra

Question

Are there any examples of combinatorial/probabilistic proofs of theorems in linear algebra?

---

Motivation: I see here, the inverse is true.

Answer 1

Applications to proving linear-algebraic results:

Doron Zeilberger, A combinatorial approach to matrix algebra. The same, but scanned better.

Richard Swan's combinatorial proof of the Amitsur-Levitzki theorem and a correction.

Dodgson's theorem proved using Zeilberger's famed talent for matchmaking.

More generally, the Dodgson-Muir determinantal identity proved combinatorially by Berliner and Brualdi.

Donald Knuth, Overlapping Pfaffians.

Jiang Zeng, A bijective proof of Muir's identity and the Cauchy-Binet formula.

Applications in which the results themselves involve combinatorics:

Britz and Fomin on posets and Young diagrams, with a section (§6) sketching how Young tableau combinatorics explains the workings of nilpotent matrices. More on it in a paper of Marc van Leeuwen.

Also, quiver representation theory, which can be seen as a generalization of things like the Jordan normal form and the rank of a matrix. But there is too much to cite here and I don't have a good overview.

Answer 2

The classical example is Straubing's combinatorial proof of the Cayley–Hamilton theorem.

Answer 3

This might be semi-off topic, but I want to include some of this in case you find it interesting. Totally unimodular matrices are those with all entries $a_{ij} \in \{0, 1, -1\}$ and the determinant of every square submatrix is also in $\{0, 1, -1\}$. These matrices are useful in studying network flow, shortest path, and matching algorithms from a linear and integer programming perspective. In a sense, we are using algebraic tools to study combinatorial and graph theoretic problems.

Some more info: ocw.nctu.edu.tw/upload/classbfs1211090940107417.pdf

The change of basis proof can also be thought of combinatorially, in terms of the exchange property on spanning trees. That is, it is possible to take an edge out of a spanning tree and swap it in for another edge, so long as a cycle isn't created. The change of basis property says basically the same thing. We can take a vector out of a basis and replace it with a new vector, provided the new vector preserves linear independence of the set. There are a whole class of greedy algorithms known as a greedy basis algorithms, including minimum spanning tree algorithms and collinear points on the Fano plane. This concept of independence is formalized in terms of Matroids.

More here: http://www.maa.org/sites/default/files/pdf/shortcourse/2011/matroidsknown.pdf