TOPICS
Search

Vector Balancing


Vector balancing is the problem of assigning signs to a given collection of vectors so that their signed sum has a small prescribed vector norm. A permutation variant also allows the coordinates of each vector to be independently permuted (Niles-Weed et al. 2026).

The Komlós conjecture asks for a bound independent of the number of vectors and the dimension when their Euclidean norms are at most 1 and the signed sum is measured in the infinity norm. Guo et al. (2026) report a bound less than 3sqrt(2pi), and Karingula and Lovett (2026) give an elementary proof with bound 36. These statements concern the final signed sum with signs alone.

The Beck-Fiala conjecture concerns the incidence matrix case with rows indexed by sets, columns by elements, and bounded column sums. six standard deviations suffice theorem gives another signing bound for n×n matrices whose entries are real numbers of absolute value at most 1 (Spencer 1985).

Niles-Weed et al. (2026) proved that, for any vectors v_1, v_2, ..., v_m in R^n with Euclidean norm at most 1, there are signs epsilon_i in {-1,1} and coordinate permutations sigma_i such that

 max_(1<=k<=m)||sum_(i=1)^kepsilon_isigma_i(v_i)||_infty<=(sqrt(n-1)+1)/(sqrt(n)),

where ||·||_infty is the infinity norm. The choices can be made online, using only the vectors seen so far. The bound tends to 1 as n->infty and is asymptotically optimal, since a single coordinate unit vector forces a bound of at least 1. The result concerns the variant with permutations, not sign choices alone.


See also

Beck-Fiala Conjecture, Euclidean Norm, Infinity Norm, Komlós Conjecture, Permutation, Six Standard Deviations Suffice Theorem, Vector Norm

Explore with Wolfram|Alpha

References

Guo, S.; Fang, E. X.; and Lu, J. "Vector Balancing via Directional Total Variation." 10 Sep 2026. https://arxiv.org/abs/2609.11189.Karingula, S. R. and Lovett, S. "An Elementary Proof of the Komlós Conjecture." 17 Sep 2026. https://arxiv.org/abs/2609.20979.Niles-Weed, J.; Sadovsky, S.; and Shkrob, J. "An Optimal Constant for Vector Balancing with Permutations." 1 Oct 2026. https://arxiv.org/abs/2610.02127.Spencer, J. "Six Standard Deviations Suffice." Trans. Amer. Math. Soc. 289, 679-706, 1985. https://doi.org/10.1090/S0002-9947-1985-0784009-0.

Cite this as:

Weisstein, Eric W. "Vector Balancing." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/VectorBalancing.html

Subject classifications