1
$\begingroup$

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 
  • 3
    (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...)2012-05-11

1 Answers 1

1

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

  • 0
    I've included the matrix and coefficients in the question, so that you could try it on Maple and post the resulting vector.2012-05-14