A note on majorization transforms and Ryser’s algorithm

• Autorzy: Geir Dahl
• Języki publikacji: EN

Abstrakty

EN

The notion of a transfer (or T -transform) is central in the theory of majorization. For instance, it lies behind the characterization of majorization in terms of doubly stochastic matrices. We introduce a new type of majorization transfer called L-transforms and prove some of its properties. Moreover, we discuss how L-transforms give a new perspective on Ryser’s algorithm for constructing (0; 1)-matrices with given row and column sums.

Słowa kluczowe

EN

Majorization; transfer; zero-one matrices with given line sums; Ryser’s algorithm • doubly stochastic matrix

Kategorie tematyczne

• 05B20: Matrices (incidence, Hadamard, etc.)
• 15A39: Linear inequalities

• Wydawca: De Gruyter Open
• Czasopismo: Special Matrices
• Rocznik: 2013
• Tom: 1
• Strony: 17-24

Daty

otrzymano

2013-09-12

zaakceptowano

2013-09-30

online

2013-10-29

Twórcy

autor

Geir Dahl

• Department of Mathematics, University of Oslo,
  P.O. Box 1053 Blindern, NO-0316 Oslo, Norway

Bibliografia

• [1] R. Bhatia, Matrix Analysis, Springer, New York, 1997.
• [2] R.A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press, Cambridge, 2006.
• [3] R.A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl. 33 (1980), 159-231.
• [4] R.A. Brualdi, P. Gibson, Convex polyhedra of doubly stochastic matrices, II. Graph of Ωn, J. Combin. Theory Ser. A 22 (1977), 175-198.
• [5] R.A. Brualdi, P. Gibson, Convex polyhedra of doubly stochastic matrices, III. Affine and combinatorial properties of Ωn, J. Combin. Theory Ser. A 22 (1977), 338-351.
• [6] L. Costa, C.M. da Fonseca, E.A. Martins, The diameter of the acyclic Birkhoff polytope, Linear Algebra Appl. 428 (2008), 1524-1537. [WoS]
• [7] G. Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra Appl. 390 (2004), 197-208.
• [8] G. Dahl, F. Zhang, Integral majorization polytopes, Discrete Math. Algorithm. Appl. DOI: 10.1142/ S1793830913500195. [Crossref]
• [9] C.M. da Fonseca, E.M. de Sá, Fibonacci numbers, alternating parity sequences and faces of the tridiagonal Birkhoff polytope, Discrete Math. 308 (2008), 1308-1318. [WoS]
• [10] G.H. Hardy, J.E. Littlewood, G. Pólya, Inequalities, (First ed. 1934, 2nd ed. 1952), Cambridge University Press, Cambridge Mathematical Library, 2, 1988.
• [11] J.H. van Lint, R.M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 2001.
• [12] A.W. Marshall, I. Olkin, B.C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second edition, Springer, New York, 2011. [WoS]
• [13] R.F. Muirhead, Some methods applicable to identities and inequalities of symmetric algebraic functions of n letters, Proc. Edinb. Math. Soc. 21 (1902), 144-157.
• [14] E.M. de Sá, Some subpolytopes of the Birkhoff polytope, Electron. J. Linear Algebra 15 (2006), 1-7.
• [15] F. Zhang, Matrix Theory - Basic Results and Techniques, Springer, New York, 2011.

Identyfikatory

DOI

10.2478/spma-2013-0004