# A note on majorization transforms and Ryser’s algorithm

Special Matrices (2013)

- Volume: 1, page 17-24
- ISSN: 2300-7451

## Access Full Article

top## Abstract

top## How to cite

topGeir Dahl. "A note on majorization transforms and Ryser’s algorithm." Special Matrices 1 (2013): 17-24. <http://eudml.org/doc/266566>.

@article{GeirDahl2013,

abstract = {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.},

author = {Geir Dahl},

journal = {Special Matrices},

keywords = {Majorization; transfer; zero-one matrices with given line sums; Ryser’s algorithm • doubly stochastic matrix; majorization; Ryser's algorithm; doubly stochastic matrix},

language = {eng},

pages = {17-24},

title = {A note on majorization transforms and Ryser’s algorithm},

url = {http://eudml.org/doc/266566},

volume = {1},

year = {2013},

}

TY - JOUR

AU - Geir Dahl

TI - A note on majorization transforms and Ryser’s algorithm

JO - Special Matrices

PY - 2013

VL - 1

SP - 17

EP - 24

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/266566

ER -

## References

top- [1] R. Bhatia, Matrix Analysis, Springer, New York, 1997. Zbl0863.15001
- [2] R.A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press, Cambridge, 2006. Zbl1106.05001
- [3] R.A. Brualdi, Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl. 33 (1980), 159-231. Zbl0448.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. Zbl0351.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. Zbl0368.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] Zbl1213.05163
- [7] G. Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra Appl. 390 (2004), 197-208. Zbl1060.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] Zbl1133.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. Zbl0980.05001
- [12] A.W. Marshall, I. Olkin, B.C. Arnold, Inequalities: Theory of Majorization and Its Applications, Second edition, Springer, New York, 2011. [WoS] Zbl1219.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. Zbl34.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. Zbl1229.15002