Vector Packing and Sharp Bounds for Matrices of Bounded Rank

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.FA — Functional Analysis

Contributed by Yair Lavi ↗

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 (vj)(v_j) whose span has finite dimension r≥1r\ge1, let MM be the supremum of the norms of its finite linear combinations with coefficients of modulus at most one. If MM is finite, the family splits into rr nonempty sets, each with sum of norms at most MM. The same partition works for every norm on the span, using that norm's value of MM. 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 kk. 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

  1. 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
  2. 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
  3. 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
  4. 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.
  5. 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
  6. G. J. O. Jameson, Summing and Nuclear Norms in Banach Space Theory , London Mathematical Society Student Texts 8 , Cambridge University Press, 1987.
  7. 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
  8. 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
  9. Y. Lavi, ``The Maximum Diagonal Product of a Stochastic Matrix of Bounded Rank,'' arXiv:2611.01763v1 (https://arxiv.org/abs/2611.01763v1), 2026.arXiv
  10. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. G. Pisier, The Volume of Convex Bodies and Banach Space Geometry , Cambridge Tracts in Mathematics 94 , Cambridge University Press, 1989.
  7. A. Riazanov and M. Vyalyi, ``Exploring the bounds on the positive semidefinite rank,'' arXiv:1704.06507v1 (https://arxiv.org/abs/1704.06507v1), 2017.arXiv

Version history

  1. v1 · 24 pagesSubmitted by Yair LaviInitial depositCurrentNov 14, 2026