ELA, Volume 9, pp. 118-121, July 2002, abstract.

Maximal Nests of Subspaces, the Matrix Bruhat 
Decomposition, and the Marriage Theorem - 
with an Application to Graph Coloring

Richard A. Brualdi

Using the celebrated Marriage Theorem of P. Hall, 
we give an elementary combinatorial proof of the 
theorem that asserts that given two maximal nests 
N_1 and N_2 in a finite dimensional vector space V, 
there is an ordered basis of V that generates N_1 and 
a permutation of that ordered basis that generates N_2. 
From this theorem one easily obtains the Matrix Bruhat 
Decomposition. A generalization to matroids is discussed, 
and an application to graph coloring is given.