Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
    
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
1  
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-Alvarez May 11 '12 at 21:27
1  
(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-Alvarez May 11 '12 at 21:51
show 11 more comments

1 Answer

up vote 0 down vote accepted

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).$

share|improve this answer
    
Ops. I forgot to ask: are solving this over $\mathbb R$ or over $\mathbb Z$? –  user2468 May 11 '12 at 21:34
    
Z. Good answer. How to convert this form (a1+a5-b3+4) to sparse matrix for Maple or Octave? –  user93200 May 11 '12 at 21:45
    
Do you have the equations (ai + aj - bk + Ci = 0) stored somewhere in a file or so? –  user2468 May 11 '12 at 22:55
    
Yes............ –  user93200 May 12 '12 at 20:25
    
Okay. For Maple, you need to write a program (or a shell script) to convert your equations from its current format into Matrix Market format. Matrix Market can represent sparse matrices. Maple can read Matrix Market with ImportMatrix command. For Octave, you can either use this or whatever described here. –  user2468 May 12 '12 at 20:32
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.