Proof of a matrix inequality with sorted column vectors and permutation matrices

Question

Consider two coloum vectors $x\in \mathbb{R}^n$ and $y\in \mathbb{R}^n$. The elements in vectors $x$ and $y$ are sorted (in ascending or descending order, but the sorting order of the two vectors should be consistent) and there are no duplicates. Matrix $M\in\mathbb{R}^{n \times n}$ is a permutation matrix (each row and each column has exactly one 1 and all other elements are zeros), and M is not an identity matrix. Proof the following inequation: $$ x^{\top}y>x^{\top}My. $$

Answer 1

We may suppose that $x$ and $y$ are both sorted in strictly ascending order, or else we can simply replace $x$ and $y$ by $-x$ and $-y$. Note that $My$ is simply a vector whose entries are a permutation of entries in $y$, so we may as well directly consider the permutation of entries in $y$.

For notational clarity, fix $x$ and $y$ and let $v\in\mathbb{R}^n$ be a vector whose entries are a permutation of those in $y$. We consider the effect of permutation on the value of $x^\top v$. Let $1\le i<j\le n$. If $v_i>v_j$, then swapping the $i$th and the $j$th entries of $v$ results in an increase of the value of $x^\top v$. This can be seen by noticing $(x_i-x_j)(v_i-v_j)<0$ if $v_i>v_j$.

If there are no $i<j$ such that $v_i>v_j$, then $v$ must be $y$. To see this, suppose $v\neq y$. Let $i$ be the smallest index such that $v_i\neq y_i$. Since $v$ is a permutation of $y$, there is $k$ such that $v_i=y_k$, and $i<k$ by minimality of $i$. By a similar line of reasoning, there is $j>i$ such that $v_j=y_i$. Since $i<k$, we have $y_i<y_k$, so $v_j<v_i$. In other words, we have found $i<j$ such that $v_i>v_j$.

Let $S_v=\{(i,j):i<j,\ v_i>v_j\}$. What we have shown is that $|S_v|=0$ implies $v=y$. Now, suppose $S_v$ is nonempty and let $(i,j)\in S_v$. Let $w$ be the vector resulted from swapping the $i$th and $j$th entries in $v$. We claim that $|S_w|<|S_v|$. The proof is messier when written out. Define $\phi:S_w\to S_v$ as follows:

Condition	Definition of $\phi(k,\ell)$
$\{k,\ell\}\cap\{i,j\}=\emptyset$	$(k,\ell)$
$k=j$	$(i,\ell)$
$\ell=i$	$(k,j)$
$k=i$ and $\ell<j$	$(i,\ell)$
$k=i$ and $\ell>j$	$(j,\ell)$
$\ell=j$ and $k>i$	$(k,j)$
$\ell=j$ and $k<i$	$(k,i)$

It is routine to check that the above table does define a map, and that $\phi\circ\phi=\text{id}_{S_w}$. In particular, $\phi$ has a left inverse, so it is injective. Since $(i,j)\not\in S_w$, we have $(i,j)\not\in \phi(S_w)$ (but $(i,j)\in S_v$). Thus, $|S_w|<|S_v|$.

Finally, given any non-identity permutation $v^{(0)}$ of $y$ (i.e. $v^{(0)}=My$), we can swap any entries in $S_{v^{(0)}}$ and obtain a vector $v^{(1)}$. If $v^{(1)}\neq y$, then we can swap any entries in $S_{v^{(1)}}$ and continue until we obtain $y$. The previous paragraphs guarantee that this process stops in a finite number of steps. Then we will obtain $x^\top v^{(0)} < x^\top v^{(1)} < \cdots < x^\top y$, which shows that $x^\top y > x^\top M y$ for any non-identity permutation matrix $M$.