Inequalities: Theory of Majorization and Its Applications

I Theory of Majorization
1 Introduction 3
A Motivation and Basic Definitions . . . . . . . . . . 3
B Majorization as a Partial Ordering . . . . . . . . . 18
C Order-Preserving Functions . . . . . . . . . . . . . 19
D Various Generalizations of Majorization . . . . . . . 21
2 Doubly Stochastic Matrices 29
A Doubly Stochastic Matrices and Permutation
Matrices . . . . . . . . . . . . . . . . . . . . . . . . 29
B Characterization of Majorization Using Doubly
StochasticMatrices . . . . . . . . . . . . . . . . . . 32
C Doubly Substochastic Matrices and Weak
Majorization . . . . . . . . . . . . . . . . . . . . . . 36
D Doubly Superstochastic Matrices and Weak
Majorization . . . . . . . . . . . . . . . . . . . . . . 42
E Orderings on D . . . . . . . . . . . . . . . . . . . . 45
F Proofs of Birkhoff’s Theorem and Refinements . . . 47
G Classes of Doubly Stochastic Matrices . . . . . . . . 52
xvii
xviii Contents
H More Examples of Doubly Stochastic and Doubly
Substochastic Matrices . . . . . . . . . . . . . . . . 61
I Properties of Doubly Stochastic Matrices . . . . . . 67
J Diagonal Equivalence of Nonnegative Matrices . . . 76
3 Schur-Convex Functions 79
A Characterization of Schur-Convex Functions . . . . 80
B Compositions Involving Schur-Convex Functions . . 88
C Some General Classes of Schur-Convex Functions . 91
D Examples I. Sums of Convex Functions . . . . . . . 101
E Examples II. Products of Logarithmically
Concave (Convex) Functions . . . . . . . . . . . . . 105
F Examples III. Elementary Symmetric Functions . . 114
G Muirhead’s Theorem . . . . . . . . . . . . . . . . . 120
H Schur-Convex Functions on D and Their
Extension to Rn . . . . . . . . . . . . . . . . . . . 132
I Miscellaneous Specific Examples . . . . . . . . . . . 138
J Integral Transformations Preserving
Schur-Convexity . . . . . . . . . . . . . . . . . . . . 145
K Physical Interpretations of Inequalities . . . . . . . 153
4 Equivalent Conditions for Majorization 155
A Characterization by Linear Transformations . . . . 155
B Characterization in Terms of Order-Preserving
Functions . . . . . . . . . . . . . . . . . . . . . . . . 156
C A Geometric Characterization . . . . . . . . . . . . 162
D A Characterization Involving Top Wage Earners . . 163
5 Preservation and Generation of Majorization 165
A Operations Preserving Majorization . . . . . . . . . 165
B Generation of Majorization . . . . . . . . . . . . . . 185
C Maximal and Minimal Vectors Under Constraints . 192
D Majorization in Integers . . . . . . . . . . . . . . . 194
E Partitions . . . . . . . . . . . . . . . . . . . . . . . 199
F Linear Transformations That Preserve Majorization 202
6 Rearrangements and Majorization 203
A Majorizations from Additions of Vectors . . . . . . 204
B Majorizations from Functions of Vectors . . . . . . 210
C Weak Majorizations from Rearrangements . . . . . 213
D L-Superadditive Functions—Properties
and Examples . . . . . . . . . . . . . . . . . . . . . 217
Contents xix
E Inequalities Without Majorization . . . . . . . . . . 225
F A Relative Arrangement Partial Order . . . . . . . 228
II Mathematical Applications
7 Combinatorial Analysis 243
A Some Preliminaries on Graphs, Incidence
Matrices, and Networks . . . . . . . . . . . . . . . . 243
B Conjugate Sequences . . . . . . . . . . . . . . . . . 245
C The Theorem of Gale and Ryser . . . . . . . . . . . 249
D Some Applications of the Gale–Ryser Theorem . . . 254
E s-Graphs and a Generalization of the
Gale–Ryser Theorem . . . . . . . . . . . . . . . . . 258
F Tournaments . . . . . . . . . . . . . . . . . . . . . . 260
G Edge Coloring in Graphs . . . . . . . . . . . . . . . 265
H Some Graph Theory Settings in Which
Majorization Plays a Role . . . . . . . . . . . . . . 267
8 Geometric Inequalities 269
A Inequalities for the Angles of a Triangle . . . . . . . 271
B Inequalities for the Sides of a Triangle . . . . . . . 276
C Inequalities for the Exradii and Altitudes . . . . . . 282
D Inequalities for the Sides, Exradii, and Medians . . 284
E Isoperimetric-Type Inequalities for Plane Figures . 287
F Duality Between Triangle Inequalities and
Inequalities Involving Positive Numbers . . . . . . . 294
G Inequalities for Polygons and Simplexes . . . . . . . 295
9 MatrixTheory 297
A Notation and Preliminaries . . . . . . . . . . . . . . 298
B Diagonal Elements and Eigenvalues of a Hermitian Matrix
. . . . . . . . . . . . . . . . . . . . . . . . . . . 300
C Eigenvalues of a Hermitian Matrix and Its
Principal Submatrices . . . . . . . . . . . . . . . . . 308
D Diagonal Elements and Singular Values . . . . . . . 313
E Absolute Value of Eigenvalues and Singular Values 317
F Eigenvalues and Singular Values . . . . . . . . . . . 324
G Eigenvalues and Singular Values of A, B,
and A + B . . . . . . . . . . . . . . . . . . . . . . . 329
H Eigenvalues and Singular Values of A, B, and AB . 338
I Absolute Values of Eigenvalues and Row Sums . . . 347

Inequalities: Theory of Majorization and Its Applications