By 苏剑林 | September 21, 2026
The rearrangement inequality is a classic inequality that is not difficult to understand. Many readers may have encountered it during middle school, especially those who have prepared for mathematics competitions. However, the rearrangement inequality is far more profound than it appears on the surface: it has a deep counterpart in the matrix world—the Von Neumann trace inequality; it can also be further generalized along the directions of "multiple sequences" and "multiple matrices."
This article follows this clue to introduce and connect these contents.
Suppose there are two real sequences sorted from largest to smallest $a_1\geq a_2\geq \cdots\geq a_n$ and $b_1\geq b_2\geq \cdots \geq b_n$. Note that no non-negative constraint is required here. $\tau(1),\tau(2),\cdots,\tau(n)$ represents an arbitrary permutation of $1,2,\cdots,n$. Then the rearrangement inequality holds:
\begin{equation}\sum_{i=1}^n a_i b_{n+1-i} \leq \sum_{i=1}^n a_i b_{\tau(i)}\leq \sum_{i=1}^n a_i b_i\end{equation}
That is, "reverse-ordered product ≤ disordered product ≤ similarly-ordered product." The standard proof for the rearrangement inequality is the local adjustment method: suppose $a_i \geq a_j$ and $b_i\geq b_j$, then
\begin{equation}(a_i b_i + a_j b_j) - (a_i b_j + a_j b_i) = (a_i - a_j)(b_i - b_j) \geq 0\end{equation}
In other words, if there is a pair of differently ordered positions in the sequence, exchanging one side to make them similarly ordered will ensure the corresponding inner product does not decrease. Thus, the maximum value must be achieved when they are completely similarly ordered. Repeating the same process for $a_1,a_2,\cdots,a_n$ and $-b_1,-b_2,\cdots,-b_n$ yields the minimum end.
Note that the rearrangement inequality itself does not require the sequences to be non-negative. However, when we generalize it later, we will add a non-negative constraint. It is worth pointing out that adding a non-negative constraint does not change the scope of the current rearrangement inequality, because any finite real sequence can be turned into a non-negative sequence by adding a sufficiently large constant without changing the order, and after expanding both ends, the rearrangement inequality without the non-negative constraint is restored.
The rearrangement inequality has a very important counterpart in matrices: let $\boldsymbol{A},\boldsymbol{B}$ be two $n\times n$ real symmetric matrices, and $\lambda_i(\cdot)$ denote the $i$-th eigenvalue sorted from largest to smallest. Then the inequality holds:
\begin{equation}\newcommand{tr}{\mathop{\text{tr}}}\sum_{i=1}^n \lambda_i(\boldsymbol{A}) \lambda_{n+1-i}(\boldsymbol{B}) \leq \tr(\boldsymbol{A}\boldsymbol{B})\leq \sum_{i=1}^n \lambda_i(\boldsymbol{A}) \lambda_i(\boldsymbol{B})\label{eq:tr-symm}\end{equation}
Obviously, when $\boldsymbol{A},\boldsymbol{B}$ takes diagonal matrices, this is equivalent to the rearrangement inequality in the previous section. Therefore, this is its matrix generalization, known as "Von Neumann's Trace Inequality," also called "Fan's Trace Inequality (Ky Fan's Trace Inequality)." In this article, it is simply referred to as the "trace inequality."
When $\boldsymbol{A},\boldsymbol{B}$ are general $n\times m$ real matrices, then the inequality holds:
\begin{equation}|\tr(\boldsymbol{A}^{\top}\boldsymbol{B})|\leq \sum_{i=1}^{\min(n,m)} \sigma_i(\boldsymbol{A}) \sigma_i(\boldsymbol{B})\label{eq:tr-gen}\end{equation}
$\sigma_i(\cdot)$ denotes the $i$-th singular value sorted from largest to smallest. Trace inequalities have wide applications in mathematics and physics. For example, in deriving the Muon optimizer, if we already know this inequality, the difficulty of the proof can be significantly reduced. The general version of the inequality can be transformed into the symmetric version using the Jordan–Wielandt symmetrization technique by constructing
\begin{equation}\tilde{\boldsymbol{A}} = \begin{pmatrix}\boldsymbol{0} & \boldsymbol{A} \\ \boldsymbol{A}^{\top} & \boldsymbol{0}\end{pmatrix},\qquad \tilde{\boldsymbol{B}} = \begin{pmatrix}\boldsymbol{0} & \boldsymbol{B} \\ \boldsymbol{B}^{\top} & \boldsymbol{0}\end{pmatrix}\end{equation}
so we only need to focus on the proof of the symmetric version.
In this section, we prove the symmetric version $\eqref{eq:tr-symm}$. Without loss of generality, let $\boldsymbol{A}$ be a diagonal matrix. If not, it can be decomposed into eigenvalues as $\boldsymbol{U}_A \boldsymbol{\Lambda}_A \boldsymbol{U}_A^{\top}$, and then use $\tr(\boldsymbol{A}\boldsymbol{B}) = \tr(\boldsymbol{U}_A \boldsymbol{\Lambda}_A \boldsymbol{U}_A^{\top}\boldsymbol{B}\boldsymbol{U}_A \boldsymbol{U}_A^{\top}) = \tr(\boldsymbol{\Lambda}_A \boldsymbol{U}_A^{\top}\boldsymbol{B}\boldsymbol{U}_A)$, where $\boldsymbol{\Lambda}_A$ is a diagonal matrix and the eigenvalues of $\boldsymbol{U}_A^{\top}\boldsymbol{B}\boldsymbol{U}_A$ are consistent with $\boldsymbol{B}$.
There are many ways to prove Von Neumann's trace inequality. Here we consider a more distinctive proof that is closer to Von Neumann's original idea. Introduce an $n\times n$ orthogonal matrix $\boldsymbol{O}$. Obviously, we have
\begin{equation}\min_{\boldsymbol{O}} \tr(\boldsymbol{A}\boldsymbol{O}^{\top}\boldsymbol{B}\boldsymbol{O}) \leq \tr(\boldsymbol{A}\boldsymbol{B}) \leq \max_{\boldsymbol{O}} \tr(\boldsymbol{A}\boldsymbol{O}^{\top}\boldsymbol{B}\boldsymbol{O})\end{equation}
Next, we want to prove that the maximum and minimum values of $\tr(\boldsymbol{A}\boldsymbol{O}^{\top}\boldsymbol{B}\boldsymbol{O})$ are exactly the upper and lower bounds we expect. First, consider the maximum value. Assume the maximum value is $\tr(\boldsymbol{A}\boldsymbol{O}_*^{\top}\boldsymbol{B}\boldsymbol{O}_*)$. Note that for any skew-symmetric matrix $\boldsymbol{S}$, the matrix exponential $e^{t\boldsymbol{S}}$ is orthogonal. Consider the perturbation $\boldsymbol{O}_*\to \boldsymbol{O}_* e^{t\boldsymbol{S}}$. According to the assumption that $\boldsymbol{O}_*$ is optimal, the derivative at $t=0$ should be $0$. Direct calculation gives
\begin{equation}\frac{d}{dt}\tr(\boldsymbol{A}(\boldsymbol{O}_* e^{t\boldsymbol{S}})^{\top}\boldsymbol{B}(\boldsymbol{O}_* e^{t\boldsymbol{S}})) = \tr([\boldsymbol{A},(\boldsymbol{O}_* e^{t\boldsymbol{S}})^{\top}\boldsymbol{B}(\boldsymbol{O}_* e^{t\boldsymbol{S}})]\boldsymbol{S})\end{equation}
where $[\boldsymbol{X},\boldsymbol{Y}]\triangleq\boldsymbol{X}\boldsymbol{Y}-\boldsymbol{Y}\boldsymbol{X}$ is usually called the commutator. The skew-symmetry of $\boldsymbol{S}$ was also used in the simplification process. Substituting $t=0$, setting it to zero, and by the arbitrariness of $\boldsymbol{S}$, we know $[\boldsymbol{A},\boldsymbol{O}_*^{\top}\boldsymbol{B}\boldsymbol{O}_*]=\boldsymbol{0}$, meaning $\boldsymbol{A}$ and $\boldsymbol{O}_*^{\top}\boldsymbol{B}\boldsymbol{O}_*$ are commutable. The same discussion process holds for the minimum value.
Note that $\boldsymbol{A}$ is a diagonal matrix. Further assume that the diagonal elements are distinct (if not, it can always be expressed as the limit of a sequence of matrices satisfying the condition). Then the matrices that commute with $\boldsymbol{A}$ are also only diagonal matrices, so $\boldsymbol{O}_*$ must be the characteristic matrix of $\boldsymbol{B}$, or in other words, $\boldsymbol{O}_*^{\top}\boldsymbol{B}\boldsymbol{O}_*$ must be the diagonalization of $\boldsymbol{B}$. Thus, the problem becomes the upper and lower bounds of the inner product of the eigenvalue vectors of the two matrices, which can be obtained by the rearrangement inequality.
A natural question is: can the rearrangement inequality be generalized to multiple sequences? Taking three sequences as an example, suppose there are non-negative sequences $a_1\geq \cdots\geq a_n\geq 0$, $b_1\geq \cdots \geq b_n\geq 0$, and $c_1\geq \cdots \geq c_n\geq 0$. $\tau(1),\cdots,\tau(n)$ and $\pi(1),\cdots,\pi(n)$ represent any two permutations of $1,\cdots,n$. Then the maximum value is still achieved when they are similarly ordered:
\begin{equation}\sum_{i=1}^n a_i b_{\tau(i)} c_{\pi(i)}\leq \sum_{i=1}^n a_i b_i c_i\end{equation}
The proof is not complicated and can be written in one line:
\begin{equation}\sum_{i=1}^n a_i b_{\tau(i)} c_{\pi(i)} = \sum_{k=1}^n(a_k - a_{k+1})\sum_{i=1}^k b_{\tau(i)} c_{\pi(i)} \leq \sum_{k=1}^n(a_k - a_{k+1})\sum_{i=1}^k b_i c_i = \sum_{i=1}^n a_i b_i c_i\end{equation}
The first equal sign uses the summation by parts method for an identity transformation (set $a_{n+1}=0$); the second equal sign uses summation by parts to transform back; the key is the inequality sign $\leq$, which is under the condition $a_k \geq a_{k+1}$, applying the rearrangement inequality to $\sum_{i=1}^k b_{\tau(i)} c_{\pi(i)}$. Noting that $b_i,c_i$ has already been sorted from largest to smallest, $\sum_{i=1}^k b_i c_i$ must be the largest, and no matter how $\sum_{i=1}^k b_{\tau(i)} c_{\pi(i)}$ is re-paired, it cannot exceed it, thus yielding this inequality.
This proof and result can be recursively generalized to any number of non-negative sequences. Note that non-negativity is necessary because "no matter how $\sum_{i=1}^k b_{\tau(i)} c_{\pi(i)}$ is re-paired, it cannot exceed $\sum_{i=1}^k b_i c_i$" is only guaranteed for non-negative sequences.
However, the minimum side cannot be generalized as simply as the maximum side.
The reason is also intuitive: "similar ordering" is transitive. The Hadamard product of two monotonically decreasing non-negative sequences is still monotonically decreasing, allowing us to repeatedly use the binary rearrangement inequality to obtain the maximum value. However, "reverse ordering" is defined specifically for two sequences. It is difficult to define what "reverse order" means for multiple sequences. The Hadamard product of an increasing and a decreasing non-negative sequence does not have a fixed monotonicity.
However, we can still obtain some signals regarding the minimum value from the inequality of arithmetic and geometric means:
\begin{equation}\sum_{i=1}^n a_i b_{\tau(i)} c_{\pi(i)}\geq n\left(\prod_{i=1}^n a_i b_{\tau(i)} c_{\pi(i)}\right)^{1/n} = n\left(\prod_{i=1}^n a_i b_i c_i\right)^{1/n}\end{equation}
The condition for equality is that all $a_i b_{\tau(i)} c_{\pi(i)}$ are equal. Of course, since we only changed the order of $b,c$, it is difficult to achieve the condition of all $a_i b_{\tau(i)} c_{\pi(i)}$ being equal, but this tells us a qualitative direction: the arrangement corresponding to the minimum value will try to make all $a_i b_{\tau(i)} c_{\pi(i)}$ balanced.
Experienced students may keenly realize that solving such balanced matching problems in discrete situations is usually quite difficult. This is indeed the case; it can essentially be abstracted as a 3-dimensional axial assignment problem, which is known to be NP-Hard. In other words, there is no general analytical solution for the minimum side of the multi-sequence rearrangement inequality, which is the inherent difficulty of the problem.
Similarly, can the trace inequality be generalized to multiple matrices? Considering three $n\times n$ matrices $\boldsymbol{A},\boldsymbol{B},\boldsymbol{C}$, we have
\begin{equation}|\tr(\boldsymbol{A}\boldsymbol{B}\boldsymbol{C})|\leq \sum_{i=1}^n \sigma_i(\boldsymbol{A}) \sigma_i(\boldsymbol{B}) \sigma_i(\boldsymbol{C})\label{eq:tr-gen-ext}\end{equation}
The proof is similar
\begin{equation}\begin{aligned}
|\tr(\boldsymbol{A}\boldsymbol{B}\boldsymbol{C})|\leq&\, \sum_{i=1}^n \sigma_i(\boldsymbol{A}) \sigma_i(\boldsymbol{B}\boldsymbol{C}) \\
=&\, \sum_{k=1}^n (\sigma_k(\boldsymbol{A}) - \sigma_{k+1}(\boldsymbol{A}))\sum_{i=1}^k \sigma_i(\boldsymbol{B}\boldsymbol{C}) \\
\leq&\, \sum_{k=1}^n (\sigma_k(\boldsymbol{A}) - \sigma_{k+1}(\boldsymbol{A}))\sum_{i=1}^k \sigma_i(\boldsymbol{B})\sigma_i(\boldsymbol{C}) \\
=&\, \sum_{i=1}^n \sigma_i(\boldsymbol{A})\sigma_i(\boldsymbol{B})\sigma_i(\boldsymbol{C})
\end{aligned}\end{equation}
That is, first use the binary trace inequality to scale once, and then still use summation by parts, scaling, and summation by parts, where the second $\leq$ uses the following inequality
\begin{equation}\sum_{i=1}^k \sigma_i(\boldsymbol{B}\boldsymbol{C}) \leq \sum_{i=1}^k \sigma_i(\boldsymbol{B})\sigma_i(\boldsymbol{C}),\qquad k=1,2,\cdots,n\end{equation}
This can also be seen as a generalization of formula $\eqref{eq:tr-gen}$. The proof idea is to first convert the left side into a trace and then use formula $\eqref{eq:tr-gen}$. Specifically, let the SVD of $\boldsymbol{B}\boldsymbol{C}$ be $\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{\top}$, then
\begin{equation}\sum_{i=1}^k \sigma_i(\boldsymbol{B}\boldsymbol{C}) = \tr(\boldsymbol{U}_{[:,:k]}^{\top}\boldsymbol{B}\boldsymbol{C}\boldsymbol{V}_{[:,:k]})\leq \sum_{i=1}^k \sigma_i(\boldsymbol{U}_{[:,:k]}^{\top}\boldsymbol{B})\sigma_i(\boldsymbol{C}\boldsymbol{V}_{[:,:k]})\leq \sum_{i=1}^k \sigma_i(\boldsymbol{B})\sigma_i(\boldsymbol{C})\end{equation}
The last inequality uses $\sigma_i(\boldsymbol{X}\boldsymbol{Y})\leq \sigma_i(\boldsymbol{X})\sigma_1(\boldsymbol{Y})$ and the orthogonality of $\boldsymbol{U}_{[:,:k]},\boldsymbol{V}_{[:,:k]}$. The same induction can be continued to obtain versions for any number of matrices.
Formula $\eqref{eq:tr-gen-ext}$ generalizes formula $\eqref{eq:tr-gen}$. How can formula $\eqref{eq:tr-symm}$ be generalized? Suppose there are $n\times n$ semi-definite matrices $\boldsymbol{A},\boldsymbol{B},\boldsymbol{C}$. Consider $\tr(\boldsymbol{A}\boldsymbol{B}\boldsymbol{C})$. The maximum side is trivial, i.e., formula $\eqref{eq:tr-gen-ext}$. Can the minimum side be similarly written in the form of $\sum_{i=1}^n \lambda_i(\boldsymbol{A}) \lambda_{\tau(i)}(\boldsymbol{B}) \lambda_{\pi(i)}(\boldsymbol{C})$?
The answer is no. The eigenvalues of a semi-definite matrix must be non-negative, so $\sum_{i=1}^n \lambda_i(\boldsymbol{A}) \lambda_{\tau(i)}(\boldsymbol{B}) \lambda_{\pi(i)}(\boldsymbol{C})$ must also be non-negative, but the trace of the product of three semi-definite matrices can be negative! Therefore, the minimum value in this form does not hold. Where is the problem? Note that for a semi-definite matrix $\boldsymbol{A},\boldsymbol{B}$, it holds that
\begin{equation}\tr(\boldsymbol{A}\boldsymbol{B}) = \tr((\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2})^{\top}(\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2})) = \Vert\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\Vert_F^2 \geq 0\end{equation}
This ensures non-negativity. From this, one might guess that a reasonable generalization for three matrices might be $\Vert\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}\Vert_F^2$, rather than the simpler $\tr(\boldsymbol{A}\boldsymbol{B}\boldsymbol{C})$. But unfortunately, while this formula looks more "correct," examples can prove that its minimum value is not necessarily equal to a certain $\sum_{i=1}^n \lambda_i(\boldsymbol{A}) \lambda_{\tau(i)}(\boldsymbol{B}) \lambda_{\pi(i)}(\boldsymbol{C})$, so it cannot serve as a generalization for the minimum side of formula $\eqref{eq:tr-symm}$.
However, $\Vert\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}\Vert_F^2$ indeed has some properties similar to the minimum end of the multi-sequence rearrangement inequality, such as the holds of
\begin{equation}\begin{aligned}
\Vert\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}\Vert_F^2 =&\, \sum_{i=1}^n \sigma_i^2(\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}) \\
\geq&\, n\left(\prod_{i=1}^n \sigma_i(\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2})\right)^{2/n} \\
=&\, n [\det(\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2})]^{2/n} \\[4pt]
=&\, n [\det(\boldsymbol{A})\det(\boldsymbol{B})\det(\boldsymbol{C})]^{1/n} \\
\end{aligned}\end{equation}
Equality holds when all singular values of $\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}$ are equal. This implies that when $\Vert\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}\Vert_F^2$ takes its minimum value, the singular values of $\boldsymbol{A}^{1/2}\boldsymbol{B}^{1/2}\boldsymbol{C}^{1/2}$ will tend toward a uniform distribution—"automatic balancing" appears again!
Starting from the rearrangement inequality, this article has combed through its main generalizations along the two clues of "matrixization" and "multi-sequencing."