Let $A=(a_{ij})_{1 \le i, j \le n}$ be a matrix such that $\sum_\limits{i=1}^{n} a_{ij}=1$ for every $j$, and $\sum_\limits{j=1}^n a_{ij} = 1$ for every $i$, and $a_{ij} \ge 0$. Let $$\begin{equation} \begin{pmatrix} y_1 \\ \vdots \\ y_n \\ \end{pmatrix} =\mathbf{A} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \end{equation}$$ with non-negative $y_i$ and $x_i$. Prove that $y_1 \cdots y_n \ge x_1 \cdots x_n$.

It may somehow matter to convex function.


3 Answers 3


$$y_i=\sum_j a_{ij} x_j\geqslant \prod_j x_j^{a_{ij} }$$ by Jensen inequality for logarithm. Now take the product over $i=1,2,\dots,n$.


This is a special case of the so called Schur's majorization inequality. Here are the details. $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bx}{\boldsymbol{x}}$ $\newcommand{\by}{\boldsymbol{y}}$

Given $\bx\in\bR^n$ we denote by $\bar{\bx}$ the vector obtained from $\bx$ by rearranging its coordinates in decreasing order. We say that $\bx$ dominates $\by$ and we write this $\bx\succ\by$ if

$$\sum_{i=1}^k \bar{x}_i\geq \sum_{i=1}^k \bar{y}_i,\;\;\forall k=1,\dotsc, n-1, $$

$$\sum_{i=1}^n \bar{x}_i= \sum_{i=1}^n \bar{y}_i.$$

The symmetric group $S_n$ acts on $\bR^n$ by permuting the coordinates of a vector. For $\bx\in\bR^n$ we denote by $S_n\cdot\bx$ the orbit of $\bx$ with respect to this action, i.e., the set of vectors that can be obtained from $\bx$ by permuting its coordinates. $\DeclareMathOperator{\conv}{conv}$

For a set $S\subset \bR^n$ we denote by $\conv(S)$ its convex hull.

The next nontrivial theorem characterizes the dominance relation. For a nice presentation of this theorem and Schur's majorization inequality I refer to Chapter 13 of

J.Michael Steele: The Cauchy-Schwarz Master Class, Cambridge University Press, 2004.

Theorem. Let $\bx,\by\in\bR^n$. The following statements are equivalent.

  1. $\bx\succ \by$.
  2. $\by\in \conv( S_n\cdot\bx)$.
  3. There exists a doubly stochastic $n\times n$ matrix $A$ such that $\by=A\bx$.

Fix an interval $(a,b)\subset \bR$. A symmetric $C^1$-function $f:(a,b)^n\to\bR$ is called Schur convex if $\newcommand{\pa}{\partial}$

$$ (x_j-x_k)\left( \frac{\pa f}{\pa x_j}(\bx)-\frac{\pa f}{\pa x_k}(\bx)\right)\geq 0,$$

for any $\bx\in (a,b)^n$ and any $j,k=1,\dotsc, n$.

The Schur majorization inequality states that

$$ \bx\succ \by \implies f(\bx)\geq f(\by), $$

for any Schur convex function $f:(a,b)^n\to\bR$ and any $\bx,\by\in(a,b)^n$.

The function

$$ p:[0,\infty)^n\to\bR,\;\;p(\bx)=-x_1\cdots x_n $$

is Schur convex. The inequality $p(\bx)\geq p(\by)$ is the inequality that interests you.


By the equivalence of conditions (ii) and (iv) in Theorem A.3 on page 14, the condition $y=Ax$ for $y=[y,\dots,y_n]^T$ and $x=[x,\dots,x_n]^T$ is equivalent to the condition that $\sum_1^n g(y_i)\ge\sum_1^n g(x_i)$ for all continuous concave functions $g$. Now take $g=\ln$ to get the desired inequality $y_1 \cdots y_n \ge x_1 \cdots x_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.