A matrix version of the Steinitz lemma

2023/08/19 by Imre Bárány, Barany, Imre · 1 citation
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Rings, Modules, and Algebras #primary 05A20 #secondary 52A22

paper · pdf · doi:10.48550/arxiv.2308.10102

openalex publication_date 2023/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Steinitz lemma, a classic from 1913, states that a₁,…,a_n, a sequence of vectors in \R^d with ∑₁ⁿ a_i=0, can be rearranged so that every partial sum of the rearranged sequence has norm at most 2dmax ‖a_i‖. In the matrix version A is a k× n matrix with entries a_i^j ∈ \R^d with ∑_j=1^k∑_i=1ⁿa_i^j=0. It is proved in \citeOPW that there is a rearrangement of row j of A (for every j) such that the sum of the entries in the first m columns of the rearranged matrix has norm at most 40d⁵max ‖a_i^j‖ (for every m). We improve this bound to (4d-2)max ‖a_i^j‖.

Cited by

• A note on the Steinitz Lemma

Related

• On Matrix Rearrangement Inequalities
• A Colorful Steinitz Lemma with Applications to Block Integer Programs
• Matrix versions of some classical inequalities
• A Spectral Generalization of Von Neumann Minimax Theorem
• Some Matrix Rearrangement Inequalities