Maximal nests of subspaces, the matrix Bruhat decomposition, and the marriage theorem---with an application to graph coloring
The electronic journal of linear algebra, Tome 9 (2002), pp. 118-121.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Using the celebrated marriage theorem of P. Hall, we give an elementary combinatorial proof of the theorem that asserts that given two maximal nests ${\cal N}_1$ and ${\cal N}_2$ in a finite-dimensional vector spce $V$, there is an ordered basis of $V$ that generates ${\cal N}_1$ and a permutation of that ordered basis that generates ${\cal 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.
Classification : 15A03, 05C15, 05B35
Keywords: nests of subspaces, matrix Bruhat decomposition, marriage theorem, graph colorings, matroids
@article{ELA_2002__9__a13,
     author = {Brualdi, Richard A.},
     title = {Maximal nests of subspaces, the matrix {Bruhat} decomposition, and the marriage theorem---with an application to graph coloring},
     journal = {The electronic journal of linear algebra},
     pages = {118--121},
     publisher = {mathdoc},
     volume = {9},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2002__9__a13/}
}
TY  - JOUR
AU  - Brualdi, Richard A.
TI  - Maximal nests of subspaces, the matrix Bruhat decomposition, and the marriage theorem---with an application to graph coloring
JO  - The electronic journal of linear algebra
PY  - 2002
SP  - 118
EP  - 121
VL  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2002__9__a13/
LA  - en
ID  - ELA_2002__9__a13
ER  - 
%0 Journal Article
%A Brualdi, Richard A.
%T Maximal nests of subspaces, the matrix Bruhat decomposition, and the marriage theorem---with an application to graph coloring
%J The electronic journal of linear algebra
%D 2002
%P 118-121
%V 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2002__9__a13/
%G en
%F ELA_2002__9__a13
Brualdi, Richard A. Maximal nests of subspaces, the matrix Bruhat decomposition, and the marriage theorem---with an application to graph coloring. The electronic journal of linear algebra, Tome 9 (2002), pp. 118-121. http://geodesic.mathdoc.fr/item/ELA_2002__9__a13/