# How to solve a system of equations (100 in number) using a program?

Form: $x_i+x_j-x_k-C_i=0$

To clarify, it might have been better to write this here as: $x_i+x_j-y_k-C_i=0$, since $x_i$ and $x_j$ come from a single set of unknowns. $y_k$ are considered different.

All are constants (but dependent mostly) but only $C_i$ are known. The problem is, it's not in matrix form. I have a set of equations, n in number, with all the different $x_k$ being exactly n in number, while $x_i$ and $x_j$ added together are fewer than n in number. I want to elucidate the dependent variables, but doing it by hand takes too long. How to express this as input to a (preferably free) pc program, to get solution e.g., as an upper triangular matrix?

Update: This seems easy at the moment (although I haven't tested yet whether this is correct), but the format of the problem made getting here difficult: I need to make a mostly sparse matrix with +/-1's for the three types of unknowns. One side would be as long as the sum of their indices, an additional column for $C_i$, and the number of rows equal to the number of equations. If this is correct, then what remains is either to find a text parser to convert plain text equations to matrix form, or to just fill in the matrix by hand.

$A$, in sparse format (row, col, value):

1 1 1
2 1 1
3 2 1
4 3 1
5 3 1
6 4 1
7 4 1
8 4 1
9 5 1
10 5 1
11 6 1
12 6 1
13 7 1
14 9 1
15 9 1
16 10 1
17 11 1
18 12 1
19 12 1
20 13 1
21 13 1
22 14 1
23 14 1
24 14 1
25 15 1
26 15 1
27 16 1
28 17 1
29 17 1
30 17 1
31 18 1
32 19 1
33 20 1
34 20 1


Coefficients:

30
27
26
26
24
25
25
20
17
21
13
14
17
18
17
13
14
13
12
12
11
6
2
3
3
2
4
2
3
0
2
1
4
4

• You can use GNU Octave, a freely available system similar to Matlab: homepages.math.uic.edu/~hanson/Octave/OctaveLinearAlgebra.html Or you could use Sage: sagemath.org/doc/tutorial/tour_linalg.html – dls May 11 '12 at 17:18
• Please be specific, how to convert my equations to the proper input? What kind of solution will I obtain? – user93200 May 11 '12 at 17:19
• Well, your equations aren't completely specified. What are the relations among $i$, $j$ and $k$? Just saying "upper triangular" doesn't exactly pin down what the matrix looks like. Also, did you look at the links? There are very good examples on each page telling you how to enter matrices. – dls May 11 '12 at 17:20
• What do you mean by "I suppose that's right"? If you don't know and are only supposing, who does know? – Mariano Suárez-Álvarez May 11 '12 at 21:27
• (if you have a few hundred equations, insisting that the representation of the matrix be done by a sparse matrix is pointless: will almost sure certainty, the background image of the desktop of your computer screen needs more memory to store than the matrix you would otherwise get...) – Mariano Suárez-Álvarez May 11 '12 at 21:51

Ok, I assume you know how to convert a set of linear equations into matrix form (if not, please check out this wikipedia page). So, what you have is a system of the form: $$A \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_m \\ y_1 \\ y_2 \\ \vdots \\ y_n \end{pmatrix} = \begin{pmatrix} C_1 \\ C_2 \\ \vdots \\ C_n \end{pmatrix} \tag{1}$$ where $A$ is an $n \times (m+n)$ matrix with entries: $\{ 0, +1, -1 \}.$ The system $(1)$ is underdetermined linear system, i.e., you have more variables than the number of equations. In general, there is not unique solution to this system.
Among the infinitely many solution vectors $v$ to $Av = C,$ you should decided a criteria to narrow down which $v$ you are looking for. If you are looking for sparsest $v$ then you can solve this problem with $\ell_1$ minimization: $$\text{min } \| v \|_1 \text{ subject to } Av = C.$$ or if you're looking for shortest $v$ in the Euclidean sense, then you can solve the the $\ell_2$ minimization problem: $$\text{min } \| v \|_2 \text{ subject to } Av = C.$$
Either ways, it's a convex optimization problem solvable in about $\mathcal O(n^2m).$
• Ops. I forgot to ask: are solving this over $\mathbb R$ or over $\mathbb Z$? – user2468 May 11 '12 at 21:34