4

I get why multiplying one equation by a constant, and swapping equations, preserves the solution set(s) in a system of equations.

But what I can't wrap my head around is why adding two rows in an augmented matrix preserves the solution set. Is there a proof/simply reasoning for this?

Each row in my matrix corresponds to a linear equation. In such a matrix,

$$ \left[ \begin {matrix} 1 & -2 & \;\;\;1 & \;\;\;0 \\ 0 & \;\;\;1 &-4 & \;\;\;4 \\ 0 &-3 &\;13 &-9 \\ \end {matrix} \right] $$

row one would be $x_1 + -2x_2 + x_3 = 0 $, and so on.

Gary Greenhorn
  • 43
  • Each row of your matrix corresponds to an equation in the system, and you're adding rows? Or is your setup such that each equation gives you a column and you're augmenting it by adding rows? – rschwieb Sep 19 '13 at 19:30
  • Each row in my matrix corresponds to a linear equation. – Gary Greenhorn Sep 19 '13 at 19:38
  • I'm assuming you're talking about adding two rows together, and replacing one of the rows in question with the new one, instead of inserting new rows altogether. Is that correct? – Henry Swanson Sep 19 '13 at 19:49
  • That is correct. For example, in the above matrix, I would multiply the second equation by 3 and add it to the third equation. The new equation would then be substituted for the third equation. What I don't understand is why the solution set is preserved after the addition. – Gary Greenhorn Sep 19 '13 at 19:58

2 Answers2

2

I'm assuming you have a matrix equation of the form $Ax = b$. A row of the augmented matrix corresponds to a linear equation with $x_1, x_2, \ldots, x_n$ as the unknowns.

Let the two rows you are adding be $[p_1~p_2~\cdots~p_n~c]$ and $[q_1~q_2~\cdots~q_n~d]$, where the $p_i$ and $q_i$ are from $A$, and $c$ and $d$ from $b$. These correspond to the equations:

$$p_1 x_1 + p_2 x_2 + \cdots + p_n x_n = c \qquad (1)$$ $$q_1 x_1 + q_2 x_2 + \cdots + q_n x_n = d \qquad (2)$$

If you add $k$ times the first row to the second, you get a new second row $[kp_1 + q_1~kp_2 + q_2~\cdots~kp_n + q_n~kc + d]$, which corresponds to this equation: $$ (kp_1 + q_1) x_1 + (kp_2 + q_2) x_2 + \cdots + (kp_n + q_n) x_n = kc + d \qquad (2^\prime)$$

The hardest part about this is justifying what exactly you need to check. We must show that $x$ satisfies $(1)$ and $(2)$ if and only if it satisfies $(1)$ and $(2^\prime)$. Checking that these are true just relies on a bunch of distributing and whatever the name for this theorem is: $u = v \textrm{ and } x = y \implies u + x = v + y$.

Forward direction: Assume $(1)$ and $(2)$ are true. Then $kp_1 x_1 + kp_2 x_2 + \cdots + kp_n x_n = kc$, because we can multiply both sides of an equation by a constant. Then, we can add $(2)$ to this, getting: $(kp_1 + q_1) x_1 + (kp_2 + q_2) x_2 + \cdots + (kp_n + q_n) x_n = kc + d$, which is exactly what we wanted to show, i.e. equation $(2^\prime)$.

Reverse direction is similar, see if you can work out the details.

Henry Swanson
  • 12,972
  • So how would I check that multiplying the second equation by 3 and adding it to the third equation would result in an equation with the same solution set? – Gary Greenhorn Sep 19 '13 at 20:04
  • It's a system of equations that you're looking at: you have to show that {row 2, row 3} has the same solution set as {row 2, row 3'}, where "row 3' " is "row 3 + 3row 2". As for proving that, because you know row 2 is true, you know 3row 2 is true. Then add that to row 3, to get row 3'. This shows row 3' is true. Then do the reverse, show that row 2 and row 3' together imply row 3. (I'm being a bit loose with terms, by "row n" I mean "the equation that row n corresponds to") – Henry Swanson Sep 19 '13 at 20:08
  • I just added the proof to my answer, because it's very messy in the comments. – Henry Swanson Sep 19 '13 at 20:14
1

In principal adding rows will change the solution set. The equations you add might increase the constraint on the solution set, making the solution set smaller. If the original matrix is just $[1,1\mid 0]$ and you add the row $[0,1\mid 0]$ then your solution space goes from matrices of the form $(x,-x)$ down to $(0,0)$.

On the other hand, if you're adding rows that are just linear combinations of the other rows, that would not change the solution set, since they don't add any more constraints.

rschwieb
  • 153,510
  • What do you mean by constraints? – Gary Greenhorn Sep 19 '13 at 19:52
  • Intuitively speaking, the more equations the solutions have to satisfy, the less solutions there are likely to be. Sometimes each equation in a system is called a "constraint" because it is a limitation on how the solution set must behave. – rschwieb Sep 19 '13 at 19:53
  • However, if you aren't careful about adding rows, you could accidentally remove a constraint and expand your solution set, because you are removing a row from your matrix. You need to be certain that your new row and old row, together with the remaining rows, are equivalent. – Henry Swanson Sep 19 '13 at 20:04
  • @GaryGreenhorn Think of it this way: the rows of the matrix carry information about the linear system. Adding this information together doesn't result in any new information (no tighter constraints). Sorry I see now that you literally meant adding rows together and keeping the number of rows the same. At first I thought you literally meant that you were increasing the number of rows. – rschwieb Sep 19 '13 at 20:07
  • It's okay, thank you very much for your effort. Unfortunately I can only accept one answer; I would accept both if I could. – Gary Greenhorn Sep 19 '13 at 20:21
  • @GaryGreenhorn You can upvote both, if you want :P – rschwieb Sep 19 '13 at 23:24