Solving a matrix of ones and zeros

1. Jun 5, 2015

JesseJC

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. Jun 5, 2015

SteamKing

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

3. Jun 5, 2015

Ray Vickson

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:
$$\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}$$
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:
$$x_4 + x_6 = 1200$$
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