Maggiorizzazione

In matematica, la maggiorizzazione è un preordine sui vettori di numeri reali. Per due vettori di questo tipo, ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}}$, si dice che ${\displaystyle \mathbf {x} }$ maggiorizza debolmente (o domina) ${\displaystyle \mathbf {y} }$ dal basso, comunemente indicato con ${\displaystyle \mathbf {x} \succ _{w}\mathbf {y} }$, quando:

${\displaystyle \sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }}$ per tutti i ${\displaystyle k=1,\,\dots ,\,n}$,

dove:

${\displaystyle x_{i}^{\downarrow }}$ denota l'i-esimo più grande elemento di ${\displaystyle \mathbf {x} }$.

Se ${\displaystyle \mathbf {x} ,\mathbf {y} }$ poi soddisfa ${\displaystyle \sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}}$, si dice che ${\displaystyle \mathbf {x} }$ maggiorizza (o domina) ${\displaystyle \mathbf {y} }$, fatto comunemente indicato con ${\displaystyle \mathbf {x} \succ \mathbf {y} }$.

Sia la majorizzazione debole che la majorizzazione sono ordinamenti parziali per vettori i cui elementi sono non decrescenti, ma solo un preordinamento per vettori generici, poiché la maggiorizzazione è indipendente dall'ordinamento degli elementi nei vettori: ad esempio, l'affermazione ${\displaystyle (1,2)\prec (0,3)}$ è semplicemente equivalente a ${\displaystyle (2,1)\prec (3,0)}$.

Più nello specifico, valle che ${\displaystyle \mathbf {x} \succ \mathbf {y} \wedge \mathbf {y} \succ \mathbf {x} }$ se e solo se ${\displaystyle \mathbf {x} ,\mathbf {y} }$ sono uno permutazione dell'altro. Lo stesso vale per ${\displaystyle \succ _{w}}$.

Il termine “maggiorizzazione” a volte si riferisce anche all'ordinamento per elementi, ad esempio la funzione a valori reali ‘f’ maggiorizza la funzione a valori reali “g” quando ${\displaystyle f(x)\geq g(x)}$ per tutti gli ${\displaystyle x}$ nel dominio, o altre definizioni tecniche, come le misure di maggiorizzazione nella teoria della probabilità.^[1]

Ciascuna delle seguenti affermazioni è vera se e solo se ${\displaystyle \mathbf {x} \succ \mathbf {y} }$:

• da ${\displaystyle \mathbf {x} }$ si può ottenere ${\displaystyle \mathbf {y} }$ mediante una sequenza finita di operazioni in cui due elementi ${\displaystyle x_{i}}$ e ${\displaystyle x_{j}<x_{i}}$ sono rispettivamente sostituiti con ${\displaystyle x_{i}-\varepsilon }$ e ${\displaystyle x_{j}+\varepsilon }$ per qualche ${\displaystyle \varepsilon \in (0,x_{i}-x_{j})}$.^[4]
• per ogni funzione convessa ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$, ${\displaystyle \sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})}$.^[5]
  • in realtà, è sufficiente un caso particolare: ${\displaystyle \sum _{i}{x_{i}}=\sum _{i}{y_{i}}}$ è, per ogni ${\displaystyle t}$, ${\displaystyle \sum _{i=1}^{d}\max(0,x_{i}-t)\geq \sum _{i=1}^{d}\max(0,y_{i}-t)}$.^[6]
• per ogni ${\displaystyle t\in \mathbb {R} }$, ${\displaystyle \sum _{j=1}^{d}|x_{j}-t|\geq \sum _{j=1}^{d}|y_{j}-t|}$.^[7]

• ${\displaystyle \mathbf {x} }$ può essere disegnata come una curva concava, connettendo ${\displaystyle (0,0),(1,x_{1}^{\downarrow }),(2,x_{1}^{\downarrow }+x_{2}^{\downarrow }),\dots ,(n,x_{1}^{\downarrow }+x_{2}^{\downarrow }+\dots +x_{n}^{\downarrow })}$. Quindi, ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ è equivalente alla curva di ${\displaystyle \mathbf {x} }$, essendo maggiore di quella di ${\displaystyle \mathbf {y} }$.

Tra i vettori non negativi con tre componenti, ${\displaystyle (1,0,0)}$ e le sue permutazioni maggiorizzano tutti gli altri vettori ${\displaystyle (p_{1},p_{2},p_{3})}$ tali che ${\displaystyle p_{1}+p_{2}+p_{3}=1}$. Ad esempio, ${\displaystyle (1,0,0)\succ (1/2,0,1/2)}$. Allo stesso modo, ${\displaystyle (1/3,1/3,1/3)}$ è maggiorizzato da tutti gli altri vettori simili, quindi ${\displaystyle (1/2,0,1/2)\succ (1/3,1/3,1/3)}$.

Questo comportamento si estende ai vettori di probabilità di lunghezza generale: il vettore singleton maggiorizza tutti gli altri vettori di probabilità e la distribuzione uniforme è maggiorizzata da tutti i vettori di probabilità.

Una funzione ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ è detta convessa di Schur quando ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ implica ${\displaystyle f(\mathbf {x} )\geq f(\mathbf {y} )}$. Pertanto, le funzioni convesse di Schur traducono l'ordinamento dei vettori in un ordinamento standard in ${\displaystyle \mathbb {R} }$. Analogamente, ${\displaystyle f(\mathbf {x} )}$ è una funzione concava di Schur quando ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ implica ${\displaystyle f(\mathbf {x} )\leq f(\mathbf {y} ).}$

Un esempio di funzione convessa di Schur è la funzione max, ${\displaystyle \max(\mathbf {x} )=x_{1}^{\downarrow }}$. Le funzioni convesse di Schur sono necessariamente simmetriche, nel senso che gli elementi del loro argomento possono essere scambiati senza modificare il valore della funzione. Pertanto, le funzioni lineari, che pure sono convesse, non sono convesse secondo Schur a meno che non siano simmetriche. Se una funzione è simmetrica e convessa, allora è convessa secondo Schur.

La maggiorizzazione può essere generalizzata alla ordinamento di Lorenz, un ordine parziale sulle funzioni di distribuzione. Ad esempio, una distribuzione della ricchezza è maggiore secondo Lorenz rispetto a un'altra se la sua curva di Lorenz si trova al di sotto dell'altra. Pertanto, una distribuzione della ricchezza maggiore secondo Lorenz ha un coefficiente di Gini più elevato e presenta una maggiore disparità di reddito.^[8]

Il preordine di maggiorizzazione può essere naturalmente esteso alle matrici di densità nel contesto dell'informatica quantistica.^[7][9] In particolare, ${\displaystyle \rho \succ \rho '}$ precisamente quando ${\displaystyle \mathrm {spec} [\rho ]\succ \mathrm {spec} [\rho ']}$ (dove ${\displaystyle \mathrm {spec} }$ indica lo stato dello spettro di una matrice).

Analogamente, si può dire che l'operatore hermitiano ${\displaystyle \mathbf {H} }$ maggiorizza un altro ${\displaystyle \mathbf {M} }$ se l'insieme degli autovalori di ${\displaystyle \mathbf {H} }$ maggiorizza quello di ${\displaystyle \mathbf {M} }$.

• J. Karamata. "Sur une inegalite relative aux fonctions convexes." Publ. Math. Univ. Belgrade 1, 145–158, 1932.
• G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd edition, 1952, Cambridge University Press, London.
• Inequalities: Theory of Majorization and Its Applications Albert W. Marshall, Ingram Olkin, Barry Arnold, Second edition. Springer Series in Statistics. Springer, New York, 2011. ISBN 978-0-387-40087-7
• A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications"
• Matrix Analysis (1996) Rajendra Bhatia, Springer, ISBN 978-0-387-94846-1
• Topics in Matrix Analysis (1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, ISBN 978-0-521-46713-1
• Majorization and Matrix Monotone Functions in Wireless Communications (2007) Eduard Jorswieck and Holger Boche, Now Publishers, ISBN 978-1-60198-040-3
• The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ISBN 978-0-521-54677-5

• Disuguaglianza di raggruppamento
• Teorema di Schur-Horn

• Maggiorizzazione, MathWorld
• Maggiorizzazione, PlanetMath

Software

• OCTAVE/MATLAB code to check majorization