Relations

Majorization

Take $a,b\in C^m$, rearrange in descending\ order to get $\left\{a_{[i]}\right\},\left\{b_{[i]}\right\}$; and in ascending order to get $\left\{a_{(i)}\right\},\left\{b_{(i)}\right\}$. $a⪯b$ (b majorizes a) if $\sum _{i=1}^m{a}_i=\sum _{i=1}^m{b}_i,\sum _{i=1}^k{a}_{[i]}\le \sum _{i=1}^k{b}_{[i]}\mathrm{\forall }k$. $\equiv$ notion from using ascending order and saying a majorizes b.

Interleaving

If a majorizes $b\in R^n$, $\mathrm{\exists }g\in R^{n-1}$ interleaved among a such that g majorizes $b^{\prime }=b_{1:n-1}$.

Pf: True for 2; suppose $n\ge 2$; take $d\in R^{n-1}$ interleaved among a (ineq A) with $\mathrm{\forall }k\in [1,n-2]:\sum _{i=1}^k{d}_{(i)}\le \sum _{i=1}^k{b}_i$ (ineq B); take their set D; $a^{\prime }=a_{1:n-1}\in D$, D bounded, closed: so compact; D convex; \(\norm{a’}{1} \leq \norm{b’}{1}\); take \(d’ = argmax_{d \in D} \norm{d}{1}\), set \(g(t) = \norm{ta’ + (1-t)d’}{1}\) is continuous over [0,1]; if \(\norm{d’}{1} \geq \norm{b’}{1}\), \(\exists t: g(t) = \norm{b’}{1}\). To show $\parallel d^{\prime }\parallel \ge \parallel b^{\prime }\parallel$: if all ineq B are strict, all of ineq A must be equalities: else \(\norm{d’} \neq max{d} \norm{d}\): then, $\parallel a_{2:n}\parallel \ge \parallel b^{\prime }\parallel$; if some ineq in ineq B is equality, take r = largest k for which this holds; then \(\sum_{i}^{r}d’{i} = \sum{i}^{r} b_{i}\), \(\forall k> r: d’{k} = a{k+1}\); thence again get $\parallel d^{\prime }\parallel \ge \parallel b^{\prime }\parallel$.

Connection with stochastic matrices

b majorizes a iff $\mathrm{\exists }$ doubly stochastic S: $a=Sb$. Lem 1: If b maj a, can make real symmetric $B=Q\mathrm{\Lambda }{Q}^{\ast }$ with diag a and ew b; B is normal matrix, so can say a = Sb for doubly stochastic S. Lem 2: Take a=Sb; as PSP’ remains stochastic with permutation matrix ops P, P’, wlog assume a, b in ascending order; take $w_j^{(k)}=\sum _{i=1}^k{s}_{i,j}$, with $\sum _{i=1}^n{w}_j^{(k)}=k$; see $\sum _{i=1}^k(a_i-b_i)=\sum _{j=1}^n{w}_j^{(k)}{b}_j-\sum _i^k{b}_i+b_k(k-\sum _{j=1}^n{w}_j^{(k)})\ge 0$.

So, by Birkhoff, b maj a iff $a=Sb=\sum _i{p}_i(Pb)$.

Weak majorization

Weak majorization ($⪰$) if $\sum _{i=1}^m{a}_i=\sum _{i=1}^m{b}_i$ condition omitted.

Connection with stochatic matrices

b weakly majorizes $a\ge 0$ iff $\mathrm{\exists }$ doubly substochastic Q: $a=Qb$. Pf of if: $\mathrm{\exists }$ doubly stochastic S: $Q\le S$; so \(\sum_{i=1}^{k}(Qb){[i]} \leq \sum{i=1}^{k}(Sb){[i]} \leq \sum{i=1}^{k}b_{[i]}\). Pf of $\to$: Let a have n nz elements; take $d=\sum b-\sum a$; extend b by adding m 0’s to get b’, extend a by adding m $d/m$ valued entries; then $\mathrm{\exists }$ dbl stoch S with $a^{\prime }=S{b}^{\prime }$; then Q is $n\times n$ principle submatrix.

b weakly majorizes a iff $\mathrm{\exists }$ doubly stochastic S: $a\le Sb$. Pf of $\leftarrow$: If $a\le Sb,a⪯Sb⪯b$. Pf of $\to$: Pick k to get $a^{\prime }=a+k1,b^{\prime }=b+k1$; If $a⪯b$, for substochastic Q, $a+k1=Q(b+k1)$; so $a=Qb\le Sb$ where S is stochastic dilation of Q.

Weak Majorization and convex increasing fn

Take convex increasing scalar function f; b weakly majorizes a; then $f(b)$ weakly majorizes $f(a)$. Pf; For doubly stochastic Q, $a\le Qb$; using monotonicity, $f(a)\le f(Qb)$; so $f(a)⪯f(Qb)$; but by Birkhoff $f(Qb)=f((\sum {\alpha }_i{P}_i)b)\le \sum {\alpha }_{i}f((P_i)b)=\sum {\alpha }_i{P}_{i}f(b)=Qf(b)$, where $\sum {\alpha }_i=1$; so $f(Qb)⪯f(b)$.

If $0\le a$, $0\le b$, with entries in descending order, $\prod _{i=1}^k{a}_i\le \prod _{i=1}^k{b}_i$, g is such that $g(e^x)$ is convex increasing, then g(b) weakly majorizes ($⪰$) g(a): $\log a⪯\log b$; use $f(x)=g(e^x)$; take care of cases where $a_{i>k}=0$ using induction.