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 
  • 0
    You can use GNU Octave, a freely available system similar to Matlab: http://homepages.math.uic.edu/~hanson/Octave/OctaveLinearAlgebra.html Or you could use Sage: http://www.sagemath.org/doc/tutorial/tour_linalg.html2012-05-11
  • 0
    Please be specific, how to convert my equations to the proper input? What kind of solution will I obtain?2012-05-11
  • 0
    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.2012-05-11
  • 0
    For a given $i$, the $j,k$ must be functions of $i$ in some way, you need to elaborate this relationship...2012-05-11
  • 0
    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.2012-05-11
  • 0
    "All are constants (but dependent mostly)" What on earth does this mean? Are $x_i$ $x_j$ the unknowns or not? Perhaps you should write down a few of these equations2012-05-11
  • 0
    By saying constants are mostly dependent I meant that there a few $x_i$ that occur in only one equation. Thus I would consider looking to express the solution in terms of those unknowns. The best way I can characterize the unknowns is by saying that their values are determined by these equations.2012-05-11
  • 0
    How would the equations look when $n=5$?2012-05-11
  • 0
    a1+a5-b3+4=0; a2+a5-b3+3=0; ... There are exactly n (=5) different b's, while number of unique a's can be arbitrary in this example.2012-05-11
  • 0
    So far what I understand: $n$ is the number of equations, $n$ is also the number of $b$'s and $m$ is the number of $a$'s. So this is a linear system with $n$ equations in $n + m$ variables?!2012-05-11
  • 0
    I suppose that's right.2012-05-11
  • 0
    If your question is how to convert the equations into the specific format for Maple or Octave or whatever, you should tell us exactly what the equatins are. In any case, learning about the exact way of giving systems of equations to various CAS is best done elsewhere!2012-05-11
  • 0
    "what remains is either to find a text parser to convert plain text equations to matrix form, or to just fill the matrix by hand." ... or to do some text search/replace :-)2012-05-11
  • 1
    What do you mean by "I suppose that's right"? If you don't *know* and are only supposing, who does know?2012-05-11
  • 0
    a1+a5-b3+4 How to convert these to sparse matrix for Maple or Octave?2012-05-11
  • 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
    Ops. I forgot to ask: are solving this over $\mathbb R$ or over $\mathbb Z$?2012-05-11
  • 0
    Z. Good answer. How to convert this form (a1+a5-b3+4) to sparse matrix for Maple or Octave?2012-05-11
  • 0
    Do you have the equations (ai + aj - bk + Ci = 0) stored somewhere in a file or so?2012-05-11
  • 0
    Okay. For Maple, you need to write a program (or a shell script) to convert your equations from its current format into [Matrix Market](http://math.nist.gov/MatrixMarket/) format. Matrix Market can represent sparse matrices. Maple can read Matrix Market with [ImportMatrix command](http://www.maplesoft.com/support/help/Maple/view.aspx?path=ImportMatrix). For Octave, you can either use [this](http://math.nist.gov/MatrixMarket/mmio/matlab/mmiomatlab.html) or [whatever described here](http://octave.1599824.n4.nabble.com/ASCII-file-format-for-sparse-matrices-td3518638.html).2012-05-12
  • 0
    @user93200 comment above.2012-05-12
  • 0
    I only have Octave installed but your link "this" (http://math.nist.gov/MatrixMarket/mmio/matlab/mmiomatlab.html) refers to matlab, so I'm unsure how to use it. But in the other link it says I just need a 3 col format where I would put my coefficients and coordinates spmat = spconvert (load ("File")); Would that work?2012-05-12
  • 0
    It should work.2012-05-12
  • 0
    In Octave, how do I specify that the solution should be over Z?2012-05-13
  • 0
    @user93200 I'm not sure how. I never did it on Octave. May be you should post another question so users with more Octave knowledge can answer?2012-05-13
  • 0
    I posted the question: http://math.stackexchange.com/questions/144638/in-octave-how-do-i-specify-that-the-solution-to-a-matrix-equation-should-be-ove. What software do you know how to do it on?2012-05-13
  • 0
    @user93200 Maple has a command to solve $Ax = b$ over $\mathbb{Z}$: `IntegerLinearSolve`.2012-05-13
  • 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