A note on majorization transforms and Ryser’s algorithm

Geir Dahl

Special Matrices (2013)

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

Abstract

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

How to cite

top

Geir 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. [1] R. Bhatia, Matrix Analysis, Springer, New York, 1997. Zbl0863.15001
  2. [2] R.A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press, Cambridge, 2006. Zbl1106.05001
  3. [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. [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. [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. [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. [7] G. Dahl, Tridiagonal doubly stochastic matrices, Linear Algebra Appl. 390 (2004), 197-208. Zbl1060.15022
  8. [8] G. Dahl, F. Zhang, Integral majorization polytopes, Discrete Math. Algorithm. Appl. DOI: 10.1142/ S1793830913500195. [Crossref] 
  9. [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. [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. [11] J.H. van Lint, R.M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 2001. Zbl0980.05001
  12. [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. [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. [14] E.M. de Sá, Some subpolytopes of the Birkhoff polytope, Electron. J. Linear Algebra 15 (2006), 1-7. 
  15. [15] F. Zhang, Matrix Theory - Basic Results and Techniques, Springer, New York, 2011. Zbl1229.15002

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.