A matrix version of the Steinitz lemma

Abstract

The Steinitz lemma, a classic from 1913, states that $a_1,\dots ,a_n$, a sequence of vectors in ${\mathbb{R}}^d$ with ${\sum }_1^n{a}_i=0$, can be rearranged so that every partial sum of the rearranged sequence has norm at most $2d\max \Vert a_i\Vert$. In the matrix version $A$ is a $k\times n$ matrix with entries $a_i^j\in {\mathbb{R}}^d$ with ${\sum }_{j=1}^k{\sum }_{i=1}^n{a}_i^j=0$. It is proved in \cite{OPW} 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^5\max \Vert a_i^j\Vert$ (for every $m$). We improve this bound to $(4d-2)\max \Vert a_i^j\Vert$.