A note on majorization transforms and Ryser’s algorithm
Geir Dahl
Special Matrices, Tome 1 (2013), p. 17-24 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2013-01-01
EUDML-ID : urn:eudml:doc:266566 
@article{bwmeta1.element.doi-10_2478_spma-2013-0004,
     author = {Geir Dahl},
     title = {A note on majorization transforms and Ryser's algorithm},
     journal = {Special Matrices},
     volume = {1},
     year = {2013},
     pages = {17-24},
     zbl = {1291.05029},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_spma-2013-0004}
}

Geir Dahl. A note on majorization transforms and Ryser’s algorithm. Special Matrices, Tome 1 (2013) pp. 17-24. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_spma-2013-0004/

[1] R. Bhatia, Matrix Analysis, Springer, New York, 1997. | Zbl 0863.15001

[2] R.A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press, Cambridge, 2006. | Zbl 1106.05001

[3] R.A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl. 33 (1980), 159-231. | Zbl 0448.05047

[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. | Zbl 0351.05130

[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. | Zbl 0368.15010

[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] | Zbl 1213.05163

[7] G. Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra Appl. 390 (2004), 197-208. | Zbl 1060.15022

[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] | Zbl 1133.05005

[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. | Zbl 0980.05001

[12] A.W. Marshall, I. Olkin, B.C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second edition, Springer, New York, 2011. [WoS] | Zbl 1219.26003

[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. | Zbl 34.0202.01

[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. | Zbl 1229.15002