# Question about an inequality described by matrices

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.

$$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$$.