Sharp permutation bound for triangular parts of correlation matrices
For an integer $n \ge 1$ let $B \in \mathbb{C}^{n \times n}$ be Hermitian positive semidefinite with $B_{ii} = 1$ for every $i$. For a permutation $\sigma$ of $\{1, \dots, n\}$ with permutation matrix $P_\sigma$, let $L_\sigma$ be the strictly lower triangular part of $P_\sigma B P_\sigma^*$, and write $\|\cdot\|_2$ for the spectral norm. The ratio $\|L\|_2/\|B\|_2$ for the strictly lower triangular part $L$ of $B$ itself enters convergence bounds for SOR methods; over all $n \times n$ matrices its supremum is asymptotic to $(\ln n)/\pi$, and Oswald and Zhou note similar lower estimates for positive semidefinite $B$ with unit diagonal. Following a suggestion of Kashin, they proved that every Hermitian $B$ has a permutation with $\|L_\sigma\|_2 \le C \|B\|_2$ for an absolute constant $C$. Their correction gives $C = 245$ for Hermitian and $C = 122.3$ for positive semidefinite $B$, and withdraws the value $32.42$ claimed earlier for unit diagonal. The all-ones matrix is fixed by every permutation; a direct computation shows that its strictly lower triangular part has norm $1/(2\sin(\pi/(4n - 2)))$, so the ratio tends to $2/\pi$ as $n \to \infty$.
Problem. Does every such $B$, for every $n \ge 1$, admit a permutation $\sigma$ with $$\|L_\sigma\|_2 \le \frac{2}{\pi}\, \|B\|_2 \,?$$ Equivalently, is $$\sup_{n \ge 1}\ \sup_{B}\ \min_{\sigma} \frac{\|L_\sigma\|_2}{\|B\|_2} = \frac{2}{\pi},$$ the inner supremum taken over all such $B$ of size $n$?
Source: Oswald, in Oswald and Zhou (2023), the correction to Oswald and Zhou (2017), who conjectures that 2/π is the best possible constant.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- FA
- Keywords
- AIM Open Applied Problems, correlation matrices, SOR methods, triangular truncation
References
@article{oswald2023,
author = {Oswald, Peter and Zhou, Weiqi},
title = {Correction: {R}andom reordering in {SOR}-type methods},
journal = {Numer. Math.},
volume = {154},
number = {3-4},
year = {2023},
pages = {521--525},
doi = {10.1007/s00211-023-01365-9},
}
@article{oswald2017,
author = {Oswald, Peter and Zhou, Weiqi},
title = {Random reordering in {SOR}-type methods},
journal = {Numer. Math.},
volume = {135},
number = {4},
year = {2017},
pages = {1207--1220},
doi = {10.1007/s00211-016-0829-7},
eprint = {1510.04727},
archivePrefix = {arXiv},
}
@misc{aim-sor-permutation-sharp-constant,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Sharp permutation bound for triangular parts of correlation matrices}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/568-sor-permutation-sharp-constant.md},
note = {Entry 568 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00384, "Sharp permutation bound for triangular parts of correlation matrices", clopen.solutions.