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 University Press

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

[1] 1. Birkhbff, G., Tres observaciones sobre el ?lgebra lineal, Univ. Nac. Tucum?n. Rev. Ser. A 5(1946), 147-150. Google Scholar

[2] 2. Dulmage, A. L. and Halperin, I., On a theorem of Frobenius. K?nig and J. von Neumann's game of Hide and Seek, Trans. Roy. Soc. Canada Sect. III 49 (1955), 23-29. Google Scholar

[3] 3. Dulmage, A. L. and Mendelsohn, N. S., Coverings of bipartite graphs, Canad. J. Math. 10 (1958), 517-534. Google Scholar

[4] 4. Dulmage, A. L. and Mendelsohn, N. S., A structure theory of bipartite graphs of finite exterior dimension, Trans. Roy, Soc. Canada Sect, III 53 (1959), 1-13. Google Scholar

[5] 5. Hoffman, A. J. and Wielandt, H. W., The variation of the spectrum of a normal matrix, Duke Math. J. 20 (1953), 37-39. Google Scholar

[6] 6. Marcus, M. and Ree, R., Diagonals of doubly stochastic matrices, Quart. J. Math. Oxford, Ser. (2), 10(1959), 296-302, Google Scholar

[7] 7. von Neumann, J., A certain zero-sum two-person game equivalent to the optimal assignment problem, Contributions to the Theory of Games, vol. II, Ann. of Math. Studies 28, 5-12. Google Scholar

Cité par Sources :