Solving a matrix of ones and zeros

[JesseJC]

Homework Statement

_ _
|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 |

Homework Equations

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

 

[SteamKing]

Homework Statement

_ _
|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 |

Homework Equations

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

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:

|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 |

 

[Ray Vickson]

Homework Statement

_ _
|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 |

Homework Equations

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

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.

 

[JesseJC]

Thanks, I would've been staring at that problem for hours