Duration: 57:53

89 views

0

The Steinitz lemma, a classic from 1913, states that a sequence a_1,...,a_n of (at most) unit vectors in R^d whose sum is the origin, can be rearranged so that every partial sum of the rearranged sequence has norm at most 2d. It is an important result with several applications. I plan to mention a few. I also explain its connection to vector balancing.
In the matrix version of the Steinitz lemma A is a k by n matrix whose entries unit vectors in R^d and their sum is the origin. Oertel, Paat, Weismantel have proved recently 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 (for every m). We improve this bound to 4d-2.