1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solving a matrix of ones and zeros

  1. Jun 5, 2015 #1
    1. The problem statement, all variables and given/known data
    _ _
    |1 0 0 0 -1 0 0 | 700 |
    |0 1 0 0 -1 0 0 | 500 |
    |0 0 1 0 0 0 0 0 | 150 |
    |0 0 0 1 0 1 0 | 1200 |
    |0 0 0 0 1 0 0 | -650 |
    |0 0 0 0 0 0 1 | -600 |

    2. Relevant equations


    3. The attempt at a solution
    This is driving me up the wall, am I missing something obvious here? It's a network flow problem and I've been working at it for a while now, I've tried my best to get it into reduced row echelon form and it's so close, but I can't seem to figure out how to find x4 and x6. if anyone could smack some sense into me here that'd be good
     
  2. jcsd
  3. Jun 5, 2015 #2

    SteamKing

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper

    Your matrix of coefficients contains 6 rows x 7 columns. If you are looking for a unique solution, one may not be available.

    If you want to show something like a matrix,without using Latex, you can cheat and use [*code*] tags instead:

    Code (Text):

    |1 0 0 0 -1 0 0 |  700 |
    |0 1 0 0 -1 0 0 |  500 |
    |0 0 1 0  0 0 0 |  150 |
    |0 0 0 1  0 1 0 | 1200 |
    |0 0 0 0  1 0 0 | -650 |
    |0 0 0 0  0 0 1 | -600 |
     
     
  4. Jun 5, 2015 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You have 6 equations in 7 unknowns, so generally (and truly, in this case) there will be infinitely many solutions. In the context of something like linear network optimization, we would look for basic solutions, obtained by setting one of the variables to 0 and then solving for the other 6 from the 6 equations. Of course, we must choose 6 linearly-independent columns on the left; that is, we must choose a solvable 6 × 6 system.

    Never mind echelon forms---they do not really help you here, and they just get in the way and obscure what is going on. Basically, you have some equations, and they are not difficult to deal with in this case. Equation 6 says ##x_7 = -600##, equation 5 says ##x_5 = -650## and equation 3 says ##x_3 = 150##. Besides those, we have:
    [tex]
    \begin{array}{rl} \text{eq.}\:1: &x_1 - x_5 = 700 \\
    \text{eq.} \; 2: &x_2 - x_5 = 500\\
    \text{eq.} \: 4: & x_4 + x_6 = 1200
    \end{array}
    [/tex]
    Since we already know ##x_5## we can get ##x_2## from eq. 2 and ##x_1## from eq. 1. We are left with the single equation in two unknowns:
    [tex] x_4 + x_6 = 1200 [/tex]
    The two basic solutions of the system would be obtained by setting ##x_4 = 0## and solving for ##x_6##, or by setting ##x_6 = 0## and solving for ##x_4##.

    For more on basic solutions, see, eg.,
    http://math.stackexchange.com/questions/209655/what-does-basic-solution-mean
    or http://crow.academy.ru/algebra/lectures_/lect_11_/lect_11eng.pdf .
    See, also, almost any textbook on operations research, which would typically discuss all this in the chapters on linear programming.
     
  5. Jun 5, 2015 #4
    Thanks, I would've been staring at that problem for hours
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Solving a matrix of ones and zeros
  1. Solve This One (Replies: 1)

  2. Solving for a Matrix (Replies: 4)

  3. Matrix solving (Replies: 1)

  4. Solving a Matrix (Replies: 2)

Loading...