Variations on the Theorem of Birkhoff – von Neumann and Extensions |
| |
Authors: | Dominique de Werra |
| |
Institution: | (1) Institut de Mathematiques, Ecole Polytechnique Fédérale de Lausanne, MA-Ecublens, CH-1015 Lausanne, Switzerland. e-mail: dewerra.ima@epfl.ch, CH |
| |
Abstract: | The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that
all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we
extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived
by using elementary properties of graph theory.
Received: October 10, 2000 Final version received: April 11, 2002 |
| |
Keywords: | , ,Bistochastic matrices, Permutation matrices, Edge coloring, Network flows, Alternating chains, Matchings |
本文献已被 SpringerLink 等数据库收录! |
|