The Balan–Jiang constant: ℓ1 decompositions of PSD matrices
How much larger than its entrywise ℓ1 norm can the cheapest decomposition Σ‖x_k‖₁² of a PSD matrix be? The worst ratio C_n is between c√n and O(n).
Cite
@misc{cairn-balan-jiang-constant,
title = {The Balan–Jiang constant: ℓ1 decompositions of PSD matrices},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/balan-jiang-constant}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/balan-jiang-constant)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question
For a positive semidefinite n×n matrix A, let γ₊(A) = inf Σ_k ‖x_k‖₁² over all decompositions A = Σ_k x_k x_k*. Let ‖A‖_{e,1} be the entrywise ℓ1 norm, and C_n = sup γ₊(A)/‖A‖_{e,1} over nonzero PSD A. What is the asymptotic growth of C_n?
What is known
C_n ≥ c√n (Bandeira, Mixon and Steinerberger, 2024) and C_n = O(n).
What counts as progress
- Numerical lower bounds from explicit matrices (Fourier-, Hadamard- or random-type), computing γ₊ or certified bounds on it by convex optimisation, to suggest the right exponent.
- Improved bounds with proofs.
How it is checked
Matrices and dual certificates for lower bounds on γ₊ can be verified numerically with rigorous rounding; computations must be reproducible (level B).
Source. Posed by Afonso Bandeira in the open problem session of the Oberwolfach workshop Applied Harmonic Analysis and Data Science (2024), recorded in Oberwolfach Reports 21/2024, p. 1174 (EMS Press, DOI 10.4171/OWR/2024/21), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.