On matrix rearrangement inequalities

Rima Alaifari, Xiuyuan Cheng, Lillian B. Pierce, Stefan SteinerbergerProceedings of the American Mathematical Society 2020 · DOI · arXiv

Abstract

This paper investigates the matrix rearrangement inequality, which posits that the spectral norm of a product of symmetric, positive semidefinite matrices is maximized when the factors are "sorted" (e.g., $A^m B^n$). While counterexamples exist for matrices of dimension $N \geq 3$, we prove that the inequality holds universally for $2 \times 2$ matrices. Furthermore, we demonstrate that for matrices of any dimension, the inequality holds locally for perturbations of the identity, suggesting that counterexamples are rare and the ordered product is a local maximum.

Introduction

In classical analysis, rearrangement inequalities state that the magnitude of certain sums or integrals is maximized when their components are ordered in a specific way. A natural extension of this principle to linear algebra asks whether the spectral norm of a matrix product is maximized when the matrices are grouped by type. Specifically, given $m$ copies of a symmetric positive semidefinite (PSD) matrix $A$ and $n$ copies of a symmetric PSD matrix $B$, is it true that:

$$\| A^{m_1} B^{n_1} A^{m_2} B^{n_2} \dots \| \leq \| A^m B^n \|$$

where $\sum m_i = m$ and $\sum n_i = n$.

If $A$ and $B$ commute, the products are identical. However, in the non-commutative case, the arrangement of factors significantly impacts the spectral norm. Previous research by Drury (2009) identified $3 \times 3$ counterexamples, proving the inequality is not universally true for all dimensions. This work addresses the remaining gap: the $2 \times 2$ case and the behavior of matrices near the identity.

The $2 \times 2$ Case

We establish that for any two $2 \times 2$ symmetric PSD matrices, the rearrangement inequality always holds (Theorem 1). The proof leverages the fact that in two dimensions, the spectral norm (the largest eigenvalue) is entirely determined by the matrix's trace and determinant.

By utilizing a sophisticated trace inequality derived from the work of Ando, Hiai, and Okubo, we show that the "ordered" product $A^m B^n$ consistently yields a larger trace than any disordered sequence of the same factors. Since the determinant of any product of these matrices is invariant under rearrangement (due to the multiplicative property $\det(AB) = \det(A)\det(B)$), the dominance in trace directly translates to dominance in the spectral norm. This suggests that $2 \times 2$ matrices lack the "geometric room" required to construct the complex eigenbasis relationships seen in Drury’s $3 \times 3$ counterexamples.

Perturbation Theory and Local Optimality

To understand why counterexamples are difficult to find, we analyze matrices that are close to the identity: $A = I + \epsilon X$ and $B = I + \epsilon Y$. Using a Taylor expansion in terms of $\epsilon$, we compare the ordered and disordered products (Theorem 2).

Interestingly, the first-order and second-order terms of the expansion are identical for both the ordered and disordered words. The distinction only emerges at the third-order term. Our analysis proves that for any disordered word, the third-order contribution is strictly smaller than that of the ordered word, provided the matrices do not share a specific commutativity relationship (specifically, that the kernel of the commutator $[A, B]$ is empty). This result implies that the rearrangement inequality is "locally" true for all dimensions; for matrices sufficiently close to the identity, sorting the factors is always the optimal strategy for maximizing the norm.

The Intuition of Projection Loss

The physical intuition behind these results involves the concept of "projection loss." Repeatedly applying a single operator $A$ tends to grow the norm of its eigenvectors. In contrast, alternating between $A$ and $B$ is analogous to projecting a vector back and forth between two different coordinate grids. Unless the grids are perfectly aligned (i.e., the matrices commute), this constant shifting typically results in a loss of magnitude relative to the growth achieved by staying within one "grid" for as long as possible. The $2 \times 2$ case is too constrained for the alternating product to overcome this loss, whereas higher dimensions allow for specific rotations where the alternating product can occasionally "win."

Conclusion

This work clarifies the boundaries of matrix rearrangement inequalities. While the $3 \times 3$ case allows for rare configurations where disordered products can grow larger, the $2 \times 2$ case is strictly governed by the rearrangement principle. Furthermore, the perturbation analysis suggests that the "sorted" configuration is a local maximum for the spectral norm across all dimensions. Future research may focus on defining the precise measure of the set of counterexamples in higher dimensions and determining if the commutator condition in the perturbation proof can be relaxed.

Summary updated

Abstract

Given two symmetric and positive semidefinite square matrices <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A comma upper B"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">A, B</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , is it true that any matrix given as the product of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> copies of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> copies of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B"> <mml:semantics> <mml:mi>B</mml:mi> <mml:annotation encoding="application/x-tex">B</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in a particular sequence must be dominated in the spectral norm by the ordered matrix product <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A Superscript m Baseline upper B Superscript n"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>A</mml:mi> <mml:mi>m</mml:mi> </mml:msup> <mml:msup> <mml:mi>B</mml:mi> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">A^m B^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ? For example, is <disp-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-vertical-bar upper A upper A upper B upper A upper A upper B upper A upper B upper B double-vertical-bar less-than-or-equal-to double-vertical-bar upper A upper A upper A upper A upper A upper B upper B upper B upper B double-vertical-bar question-mark"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false"> ‖ </mml:mo> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>B</mml:mi> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>B</mml:mi> <mml:mi>A</mml:mi> <mml:mi>B</mml:mi> <mml:mi>B</mml:mi> <mml:mo fence="false" stretchy="false"> ‖ </mml:mo> <mml:mo> ≤ </mml:mo> <mml:mo fence="false" stretchy="false"> ‖ </mml:mo> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>A</mml:mi> <mml:mi>B</mml:mi> <mml:mi>B</mml:mi> <mml:mi>B</mml:mi> <mml:mi>B</mml:mi> <mml:mo fence="false" stretchy="false"> ‖ </mml:mo> <mml:mo>?</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\begin{equation*} \| AABAABABB \| \leq \| AAAAABBBB \| ? \end{equation*}</mml:annotation> </mml:semantics> </mml:math> </disp-formula> Drury [Electron J. Linear Algebra 18 (2009), pp. 13–20] has characterized precisely which disordered words have the property that an inequality of this type holds for all matrices <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A comma upper B"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">A,B</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . However, the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -parameter family of counterexamples Drury constructs for these characterizations is comprised of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="3 times 3"> <mml:semantics> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo> × </mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">3 \times 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrices, and thus as stated the characterization applies only for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N times upper N"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> × </mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">N \times N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrices with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N greater-than-or-equal-to 3"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> ≥ </mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">N \geq 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In cont
BibTeX
@inproceedings{alaifari2020matrix,
  author = {Rima Alaifari and Xiuyuan Cheng and Lillian B. Pierce and Stefan Steinerberger},
  title = {{On matrix rearrangement inequalities}},
  booktitle = {Proceedings of the American Mathematical Society},
  year = {2020},
  doi = {10.1090/proc/14831},
}

Loading related content...

Figure