# Minimise simultaneous equation remainder

I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = [1,4,5,6,3,1,4,5,6,7,...7]

and I have a set of other vectors for example: a1 = [0,0,0,0,0,1,2,3,0,0,...0] a2 = [0,0,0,0,1,2,5,0,0,0,...0] a3 = [0,0,0,2,2,3,0,0,0,0,...0] a4 = [0,0,1,1,1,0,0,0,0,0,...0] ... an = [0,0,1,1,1,0,0,0,0,0,...0]

I want to find out what linear combination of the vectors is closest to v. I define the distance of two vectors to be the sum of the absolute differences of each of its elements. For example the distance between [1,2,3] and [2,2,2] is abs(1-2) + abs(2-2) + abs(3-2) = 2.

Does such an algorithm exist? If it doesn't exist, are there any algorithms that could get me close to a solution?

Ideally I would like an integer multiple of each vector, does such a solution exist with integer multiples?

If you require integer multiples the problem is (strongly) $NP$-complete. There is a very easy reduction from 1-in-3-SAT. Let the dimension of the vectors be equal to the number of clauses, let the target vector be $(1,\ldots,1)$ and for every variabele create a vector $a_i$ that for each clause it appears in has a $1$ in that position (and a $0$ otherwise). You can achieve distance $0$ if and only if the formula is satisfiable.