Inequalities under doubly stochastic averaging

If M is a doubly stochastic matrix and y = M x, then every coordinate of y is a convex combination of the coordinates of x, with weights the corresponding row of M. Jensen's inequality bounds φ (y i) by the same convex combination of the values φ (x j), and summing over i, the column sums of M being 1, gives ∑ i, φ (y i) ≤ ∑ j, φ (x j) for every convex φ. This is the easy direction of the Hardy–Littlewood–Pólya characterization of majorization; it is the step through which the forward Schur–Horn inequality passes from the spectrum of a symmetric operator to its diagonal in an arbitrary orthonormal basis.

Doubly stochastic averaging also cannot increase a sorted pairing. If x and y monovary (for instance, both are sorted decreasingly), the rearrangement inequality says that the pairing ∑ i, x i * y (σ i) is largest at σ = 1. By Birkhoff's theorem every doubly stochastic matrix is a convex combination of permutation matrices, so x ⬝ᵥ (M *ᵥ y) ≤ x ⬝ᵥ y. This is the combinatorial core of the von Neumann trace inequality.

Main results

• Matrix.sum_smul_permMatrix_mem_doublyStochastic: a convex combination of permutation matrices is doubly stochastic.
• ConvexOn.sum_map_mulVec_le_of_mem_doublyStochastic: for a doubly stochastic M and a convex φ, ∑ i, φ ((M *ᵥ x) i) ≤ ∑ i, φ (x i).
• Monovary.dotProduct_mulVec_le_of_mem_doublyStochastic: for a doubly stochastic M and monovarying x and y, x ⬝ᵥ (M *ᵥ y) ≤ x ⬝ᵥ y.

References

• A. W. Marshall, I. Olkin, B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, 2nd ed., Springer (2011), Proposition 4.B.1.
• R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics 169, Springer (1997), Chapter II.

theorem Matrix.sum_smul_permMatrix_mem_doublyStochastic {R : Type u_1} {n : Type u_2} [Fintype n] [DecidableEq n] [Semiring R] [PartialOrder R] [IsOrderedRing R] {s : Finset (Equiv.Perm n)} {w : Equiv.Perm n → R} (hw₀ : ∀ σ ∈ s, 0 ≤ w σ) (hw₁ : ∑ σ ∈ s, w σ = 1) : ∑ σ ∈ s, w σ • Equiv.Perm.permMatrix R σ ∈ doublyStochastic R n

A convex combination of permutation matrices is doubly stochastic.

theorem ConvexOn.sum_map_mulVec_le_of_mem_doublyStochastic {𝕜 : Type u_1} {β : Type u_2} {n : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] [AddCommGroup β] [PartialOrder β] [IsOrderedAddMonoid β] [Module 𝕜 β] [IsStrictOrderedModule 𝕜 β] [Fintype n] [DecidableEq n] {s : Set 𝕜} {φ : 𝕜 → β} (hφ : ConvexOn 𝕜 s φ) {M : Matrix n n 𝕜} (hM : M ∈ doublyStochastic 𝕜 n) {x : n → 𝕜} (hx : ∀ (i : n), x i ∈ s) : ∑ i : n, φ (M.mulVec x i) ≤ ∑ i : n, φ (x i)

Convex functions decrease under doubly stochastic averaging. If M is doubly stochastic, φ is convex on s, and every coordinate of x lies in s, then ∑ i, φ ((M *ᵥ x) i) ≤ ∑ i, φ (x i).

theorem Monovary.dotProduct_mulVec_le_of_mem_doublyStochastic {𝕜 : Type u_1} {n : Type u_3} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] [Fintype n] [DecidableEq n] {x y : n → 𝕜} (hxy : Monovary x y) {M : Matrix n n 𝕜} (hM : M ∈ doublyStochastic 𝕜 n) : x ⬝ᵥ M.mulVec y ≤ x ⬝ᵥ y

Doubly stochastic averaging decreases a sorted pairing. If x and y monovary and M is doubly stochastic, then x ⬝ᵥ (M *ᵥ y) ≤ x ⬝ᵥ y.