Vector Packing and Sharp Bounds for Matrices of Bounded Rank
Version 1 / Nov 15, 2026 / CC BY 4.0
Abstract
We prove a packing theorem in real and complex normed spaces. Given a possibly infinite family of vectors whose span has finite dimension , let be the supremum of the norms of its finite linear combinations with coefficients of modulus at most one. If is finite, the family splits into nonempty sets, each with sum of norms at most . The same partition works for every norm on the span, using that norm's value of . We also determine exactly which finite lists of nonnegative numbers can be realized as the norms of a family of capacity one in some normed space of dimension at most . We also obtain sharp rank-dependent bounds for products of the moduli of the entries on generalized diagonals and the permanent of the entrywise modulus, extending the known nonnegative-matrix bounds to real and complex matrices. The packing theorem also gives sharp support and entropy bounds for doubly stochastic matrices of bounded rank.
Tools used
- OpenAI
- GPT (Sol)
- OpenAI
- GPT (Astra)
- Anthropic
- Claude Fable
References
- G. Ambrus and F. Grundbacher, ``Large Signed Sums and the Polarization Constant of Convex Bodies,'' arXiv:2502.13752v2 (https://arxiv.org/abs/2502.13752v2), 2026.arXiv
- A. Brauer, ``Limits for the characteristic roots of a matrix. II,'' Duke Mathematical Journal 14 (1947), 21--26. doi:10.1215/S0012-7094-47-01403-8 (https://doi.org/10.1215/S0012-7094-47-01403-8).DOI
- F. Cicalese, L. Gargano and U. Vaccaro, ``Bounds on the Entropy of a Function of a Random Variable and Their Applications,'' IEEE Transactions on Information Theory 64 (2018), 2220--2230. doi:10.1109/TIT.2017.2787181 (https://doi.org/10.1109/TIT.2017.2787181). Preprint: arXiv:1712.07906 (https://arxiv.org/abs/1712.07906).arXivDOI
- K. Fan and A. J. Hoffman, ``Lower bounds for the rank and location of the eigenvalues of a matrix,'' in O. Taussky (ed.), Contributions to the Solution of Systems of Linear Equations and the Determination of Eigenvalues , National Bureau of Standards Applied Mathematics Series 39 , U.S. Government Printing Office, Washington, D.C., 1954, 117--130.
- A. J. Hoffman, ``On the variation of co-ordinates in subspaces,'' Annali di Matematica Pura ed Applicata 86 (1970), 53--59. doi:10.1007/BF02415709 (https://doi.org/10.1007/BF02415709).DOI
- G. J. O. Jameson, Summing and Nuclear Norms in Banach Space Theory , London Mathematical Society Student Texts 8 , Cambridge University Press, 1987.
- M. I. Kadets and M. G. Snobar, ``Some functionals over a compact Minkovskii space,'' Mathematical Notes 10 (1971), 694--696. doi:10.1007/BF01106467 (https://doi.org/10.1007/BF01106467).DOI
- Y. Lavi, ``The permanent and diagonal products on the set of nonnegative matrices with bounded rank,'' arXiv:1808.00016v1 (https://arxiv.org/abs/1808.00016v1), 2018.arXiv
- Y. Lavi, ``The Maximum Diagonal Product of a Stochastic Matrix of Bounded Rank,'' arXiv:2611.01763v1 (https://arxiv.org/abs/2611.01763v1), 2026.arXiv
- Y. Lavi, ``The Maximum Permanent of a Stochastic Matrix of Bounded Rank,'' arXiv:2609.27911v1 (https://arxiv.org/abs/2609.27911v1), 2026.arXiv
Show all 17 referencesShow fewer references
- D. R. Lewis, ``Ellipsoids defined by Banach ideal norms,'' Mathematika 26 (1979), 18--29. doi:10.1112/S0025579300009566 (https://doi.org/10.1112/S0025579300009566).DOI
- M. Marcus and H. Minc, ``Generalized matrix functions,'' Transactions of the American Mathematical Society 116 (1965), 316--329. doi:10.1090/S0002-9947-1965-0194445-9 (https://doi.org/10.1090/S0002-9947-1965-0194445-9).DOI
- A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications , 2nd ed., Springer, 2011. doi:10.1007/978-0-387-68276-1 (https://doi.org/10.1007/978-0-387-68276-1).DOI
- A. Ostrowski, ``Über die Determinanten mit überwiegender Hauptdiagonale,'' Commentarii Mathematici Helvetici 10 (1937), 69--96. doi:10.1007/BF01214284 (https://doi.org/10.1007/BF01214284).DOI
- A. Ostrowski, ``Ueber das Nichtverschwinden einer Klasse von Determinanten und die Lokalisierung der charakteristischen Wurzeln von Matrizen,'' Compositio Mathematica 9 (1951), 209--226. Numdam: CM_1951__9__209_0 (https://www.numdam.org/item/CM_1951__9__209_0/).link
- G. Pisier, The Volume of Convex Bodies and Banach Space Geometry , Cambridge Tracts in Mathematics 94 , Cambridge University Press, 1989.
- A. Riazanov and M. Vyalyi, ``Exploring the bounds on the positive semidefinite rank,'' arXiv:1704.06507v1 (https://arxiv.org/abs/1704.06507v1), 2017.arXiv