A matrix version of the Steinitz lemma

The Steinitz lemma, a classic from 1913, states that <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:msub> <m:mi>a</m:mi> <m:mn>1</m:mn> </m:msub> <m:mo>,</m:mo> <m:mi mathvariant="normal">…</m:mi> <m:mo>,</m:mo> <m:msub> <m:mi>a</m:mi> <m:mi>n</m:mi> </m:msub> </m:mrow> </m:math> {a₁,…,aₙ} , a sequence of vectors in <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msup> <m:mi>ℝ</m:mi> <m:mi>d</m:mi> </m:msup> </m:math> {Rᵈ} with <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:msubsup> <m:mo largeop="true" symmetric="true">∑</m:mo> <m:mrow> <m:mi>i</m:mi> <m:mo>=</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mi>n</m:mi> </m:msubsup> <m:msub> <m:mi>a</m:mi> <m:mi>i</m:mi> </m:msub> </m:mrow> <m:mo>=</m:mo> <m:mn>0</m:mn> </m:mrow> </m:math> {∑ᵢ₌₁ⁿaᵢ=0} , can be rearranged so that every partial sum of the rearranged sequence has norm at most <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mn>2</m:mn> <m:mo>⁢</m:mo> <m:mi>d</m:mi> <m:mo>⁢</m:mo> <m:mrow> <m:mi>max</m:mi> <m:mo>⁡</m:mo> <m:mrow> <m:mo>∥</m:mo> <m:msub> <m:mi>a</m:mi> <m:mi>i</m:mi> </m:msub> <m:mo>∥</m:mo> </m:mrow> </m:mrow> </m:mrow> </m:math> {2dmax\|aᵢ\|} . In the matrix version A is a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mi>k</m:mi> <m:mo>×</m:mo> <m:mi>n</m:mi> </m:mrow> </m:math> {k× n} matrix with entries <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:msubsup> <m:mi>a</m:mi> <m:mi>i</m:mi> <m:mi>j</m:mi> </m:msubsup> <m:mo>∈</m:mo> <m:msup> <m:mi>ℝ</m:mi> <m:mi>d</m:mi> </m:msup> </m:mrow> </m:math> {aᵢʲᵈ} with <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:msubsup> <m:mo largeop="true" symmetric="true">∑</m:mo> <m:mrow> <m:mi>j</m:mi> <m:mo>=</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mi>k</m:mi> </m:msubsup> <m:mrow> <m:msubsup> <m:mo largeop="true" symmetric="true">∑</m:mo> <m:mrow> <m:mi>i</m:mi> <m:mo>=</m:mo> <m:mn>1</m:mn> </m:mrow> <m:mi>n</m:mi> </m:msubsup> <m:msubsup> <m:mi>a</m:mi> <m:mi>i</m:mi> <m:mi>j</m:mi> </m:msubsup> </m:mrow> </m:mrow> <m:mo>=</m:mo> <m:mn>0</m:mn> </m:mrow> </m:math> {∑ⱼ₌₁ᵏ∑ᵢ₌₁ⁿaᵢʲ=0} . It is proved in [T. Oertel, J. Paat and R. Weismantel, A colorful Steinitz lemma with applications to block integer programs, Math. Program. 204 2024, 677–702] 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 <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mn>40</m:mn> <m:mo>⁢</m:mo> <m:msup> <m:mi>d</m:mi> <m:mn>5</m:mn> </m:msup> <m:mo>⁢</m:mo> <m:mrow> <m:mi>max</m:mi> <m:mo>⁡</m:mo> <m:mrow> <m:mo>∥</m:mo> <m:msubsup> <m:mi>a</m:mi> <m:mi>i</m:mi> <m:mi>j</m:mi> </m:msubsup> <m:mo>∥</m:mo> </m:mrow> </m:mrow> </m:mrow> </m:math> {40d⁵max\|aᵢʲ\|} (for every m ). We improve this bound to <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mrow> <m:mrow> <m:mo stretchy="false">(</m:mo> <m:mrow> <m:mrow> <m:mn>4</m:mn> <m:mo>⁢</m:mo> <m:mi>d</m:mi> </m:mrow> <m:mo>-</m:mo> <m:mn>2</m:mn> </m:mrow> <m:mo stretchy="false">)</m:mo> </m:mrow> <m:mo>⁢</m:mo> <m:mrow> <m:mi>max</m:mi> <m:mo>⁡</m:mo> <m:mrow> <m:mo>∥</m:mo> <m:msubsup> <m:mi>a</m:mi> <m:mi>i</m:mi> <m:mi>j</m:mi> </m:msubsup> <m:mo>∥</m:mo> </m:mrow> </m:mrow> </m:mrow> </m:math> {(4d-2)max\|aᵢʲ\|} .