Geodesic
On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices
Canadian mathematical bulletin, Tome 3 (1960) no. 3, pp. 237-242

Voir la notice de l'article provenant de la source Cambridge

DOI

In [1] G. Birkhoff stated an algorithm for expressing a doubly stochastic matrix as an average of permutation matrices. In this note we prove two graphical lemmas and use these to find an upper bound for the number of permutation matrices which the Birkhoff algorithm may use.A doubly stochastic matrix is a matrix of non-negative elements with row and column sums equal to unity and is there - fore a square matrix. A permutation matrix is an n × n doubly stochastic matrix which has n2-n zeros and consequently has n ones, one in each row and one in each column. It has been shown by Birkhoff [1],Hoffman and Wielandt [5] and von Neumann [7] that the set of all doubly stochastic matrices, considered as a set of points in a space of n2 dimensions constitute the convex hull of permutation matrices. 
Johnson, Diane M.; Dulmage, A. L.; Mendelsohn, N. S. On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices. Canadian mathematical bulletin, Tome 3 (1960) no. 3, pp. 237-242. doi: 10.4153/CMB-1960-029-5
@article{10_4153_CMB_1960_029_5,
     author = {Johnson, Diane M. and Dulmage, A. L. and Mendelsohn, N. S.},
     title = {On an {Algorithm} of {G.} {Birkhoff} {Concerning} {Doubly} {Stochastic} {Matrices}},
     journal = {Canadian mathematical bulletin},
     pages = {237--242},
     year = {1960},
     volume = {3},
     number = {3},
     doi = {10.4153/CMB-1960-029-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1960-029-5/}
}
TY  - JOUR
AU  - Johnson, Diane M.
AU  - Dulmage, A. L.
AU  - Mendelsohn, N. S.
TI  - On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices
JO  - Canadian mathematical bulletin
PY  - 1960
SP  - 237
EP  - 242
VL  - 3
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1960-029-5/
DO  - 10.4153/CMB-1960-029-5
ID  - 10_4153_CMB_1960_029_5
ER  - 
%0 Journal Article
%A Johnson, Diane M.
%A Dulmage, A. L.
%A Mendelsohn, N. S.
%T On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices
%J Canadian mathematical bulletin
%D 1960
%P 237-242
%V 3
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1960-029-5/
%R 10.4153/CMB-1960-029-5
%F 10_4153_CMB_1960_029_5

Cité par Sources :