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.