I will give a simple example of my question then the full one. Let's say I am trying to reconcile my bank account, and have no statement. I opened it with $0 exactly, and a small number of transactions later, I have a balance. The problem is, I have no receipts, just scraps of paper, each with an amount which either could have been deposited or withdrawn, or irrelevant. How can I use matrix solving to setup and solve this problem?
Easy example: The list of papers read (in ascending order):
$2.05, 6.32, 8.96, 19.37, \textrm{and } 25.00$
The current account balance is 7.68.
I started to set this up into a simple matrix/vector problem, ${\mathbf{A} x = \mathbf{B}}$, where
$\mathbf{A}=[2.05, 6.32, 8.96, 19.37, 25.00]$ $\mathbf{B}=7.68$ and $x=\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix}$
The problem only really requires $x_i \in \{-1, 0, 1\}$. This kind of constraint confuses me. I was able to solve this problem using Excel, and the SUMPRODUCT function with the Solver Tool, and it took about 10 minutes, and came up with the solution of $x=[1,0,0,-1,1]$ Mathematica took 30 minutes for a similar item list (although I used a For construct because I didn't know how to constrain the values of the coefficients).
I remember my college math teacher saying things about unique solutions, etc. It's possible that you could have multiple solutions to the problem I just posed, but because of the constraint on the coefficients, the possibility is extremely low and depends on the transaction amounts.
When this is extended to say 20 "transactions", that leaves the CAS or person to $3^{20}$ calculations. I know there are matrix algorithms, and especially special forms of working with matrices especially in Excel and Mathematica (both of which I have and use regularly).
Is there a way to define this problem in Mathematica so that its awesome Matrix manipulating powers can be put to good use? And an answer produced much more quickly than this recursive brute force method?