MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 Tried to clarify the sense in which applications of this lemma involve linear algebra.

The Lindstrom-Gessel-Viennot Lemma uses the reflection principle on $S_n$ to say that the number of nonintersecting families of lattice paths in the plane equals the determinant of a matrix so that the $i,j$-th entry is the number of paths from the $i$th source to the $j$th sink.

This was not a linear algebra proof. However, this determinant can be used to enumerate plane partitions inside an $a\times b \times c~$ box, to $q$-enumerate plane partitions by weight, and to count domino tilings of an Aztec diamond. The resulting determinants can be manipulated and evaluated in ways which are natural in linear algebra, but not as clear on the objects, such as factoring the matrices. These enumerations can be viewed as applications of simple results in linear algebra.

Notes:

Lattice paths are defined and the sources and sinks are restricted so that any nonintersecting family must be an even permutation from source indices to sink indices, usually the identity.

Others independently discovered this result, e.g., Karlin and McGregor.

The same idea applies to Brownian motion.

1 [made Community Wiki]

The Lindstrom-Gessel-Viennot Lemma uses the reflection principle on $S_n$ to say that the number of nonintersecting families of lattice paths in the plane equals the determinant of a matrix so that the $i,j$-th entry is the number of paths from the $i$th source to the $j$th sink.

This can be used to enumerate plane partitions inside an $a\times b \times c~$ box, to $q$-enumerate plane partitions by weight, and to count domino tilings of an Aztec diamond. The resulting determinants can be manipulated and evaluated in ways which are natural in linear algebra, but not as clear on the objects.

Notes:

Lattice paths are defined and the sources and sinks are restricted so that any nonintersecting family must be an even permutation from source indices to sink indices, usually the identity.

Others independently discovered this result, e.g., Karlin and McGregor.

The same idea applies to Brownian motion.