# Rearrange vectors so partial sums are all non-negative

Consider we are given a collection of $$n$$ vectors in $$d$$ dimensions, we want to decide if they can be rearranged into $$v_1,\ldots,v_n$$ such that $$\sum_{i=1}^j v_i\geq \textbf{0}$$ for all $$j\in [n]$$. Here $$a \geq \textbf{0}$$ if and only if all coordinates is at least $$0$$.

Have this problem been studied before?

I don't know if it has an official name, but it is NP complete; I give a reduction idea from Exact Cover from 3-Sets:

Given $$n = 3q$$, $$X = \{x_1,...,x_{n}\}$$ and $$C_1,C_2,...,C_m$$ a collection of 3 elements subsets.

Use the following set of $$3q + 2$$ dimensions vectors:

$$v_{fill} = [1_1, 1_2, ... ,1_{3q}, \; q_z ,\; 0_b]$$ (the subscripts are just labels to show the element "column" position)

For each $$C_i = \{ x_{i1}, x_{i2}, x_{i3} \}$$

$$v_{C_i} = [ 0,...,0, -1_{i1},0,...,0,-1_{i2},0,-1_{i3},0,...,0, \; -1_{z}, \; 1_{b} ]$$

$$v_{clean} = [ m, m, ..., m, m_{z}, -q_{b} ]$$

Starting from $$[0,0,...,0,\; 0_{z}, \; 0_{b}]$$ the only vector that doesn't contain negative elements is $$v_{fill}$$ so it must be the first of the sum.

Then in order to be able to add $$v_{clean}$$ that has a $$-q$$ in column $$b$$; we must add exactly $$q$$ vectors $$v_{C_i}$$ that contains $$[....,1_{b}]$$; we cannot add more than $$q$$ otherwisee the column $$z$$ becomes negative.

Furthermore we cannot add two $$C_i$$ that has the same element in the first $$3q$$ columns, otherwise it would become negative.

At this point $$v_{clean}$$ can be added; and, finally, the remaining $$v_{C_i}$$ can be added ("cleaned")

Example:

n = 3q = 6; q=2; m = 3
C_1={1,2,3}, C_2={ 4,5,6}, C_3={1,2,4}
v_fill = [ 1, 1, 1, 1, 1, 1, 2, 0 ]
v_C_1  = [ 1, 1, 1, 0, 0, 0,-1, 1 ]
v_C_2  = [ 0, 0, 0, 1, 1, 1,-1, 1 ]
v_C_3  = [ 1, 1, 0, 1, 0, 0,-1, 1 ]
v_clear= [ 3, 3, 3, 3, 3, 3, 3,-2 ]

Sum: v_fill + v_C_1 + v_C_2 + v_clear + v_C_3