Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-30T19:43:39.604Z Has data issue: false hasContentIssue false
  • English
  • Français

On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices

Published online by Cambridge University Press:  20 November 2018

Diane M. Johnson ,
A. L. Dulmage  and
N. S. Mendelsohn
Diane M. Johnson
Affiliation:
University of Manitoba
A. L. Dulmage
Affiliation:
University of Manitoba
N. S. Mendelsohn
Affiliation:
University of Manitoba
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 3 , Issue 3 , 01 September 1960 , pp. 237 - 242
Copyright
Copyright © Canadian Mathematical Society 1960

References

1. Birkhbff, G., Tres observaciones sobre el ?lgebra lineal, Univ. Nac. Tucum?n. Rev. Ser. A 5(1946), 147-150.Google Scholar
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. Dulmage, A. L. and Mendelsohn, N. S., Coverings of bipartite graphs, Canad. J. Math. 10 (1958), 517-534.Google Scholar
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. 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. Marcus, M. and Ree, R., Diagonals of doubly stochastic matrices, Quart. J. Math. Oxford, Ser. (2), 10(1959), 296-302,Google Scholar
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