Bárány, Imre; (2024) A matrix version of the Steinitz lemma. Journal für die reine und angewandte Mathematik (Crelles Journal) , 2024 (809) pp. 261-267. 10.1515/crelle-2024-0008.

Text Barany_10.1515_crelle-2024-0008.pdf Access restricted to UCL open access staff until 27 March 2025. Download (190kB)

Abstract

The Steinitz lemma, a classic from 1913, states that a 1 , … , a n , a sequence of vectors in R d with ∑ n i = 1 a i = 0 , can be rearranged so that every partial sum of the rearranged sequence has norm at most 2 d max ∥ a i ∥ . In the matrix version A is a k × n matrix with entries a j i ∈ R d with ∑ k j = 1 ∑ n i = 1 a j i = 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 40 d 5 max ∥ ∥ a j i ∥ ∥ (for every m). We improve this bound to ( 4 d − 2 ) max ∥ ∥ a j i ∥ ∥ . .

Download activity - last month

Export as XMLJSONCSV

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item