Proof of elementary row operations for matrices?

Question

I'm taking a Linear Algebra course, and we just started talking about matrices. So we were introduced to the elementary row operations for matrices which say that we can do the following:

1. Interchange two rows.
2. Multiply a row with a nonzero number.
3. Add a row to another one multiplied by a number.

Now I understood from the lecture in class how to use these and all, but I want to understand the logic behind number 3. Is there a mathematical proof that shows that by adding row $R_1$ to row $R_2$ we are not changing the system of equations?

Thanks in advance

Answer 1

We are changing the system of equations, what we are not changing is the set of solutions to the system of equations.

The following figure shows the equations \begin{align*} -x+2y &= 2 \\ x-y &= 0 \end{align*} and what happens after we add the first equation to the second, i.e., the system of equations \begin{align*} -x+2y &= 2 \\ y &= 2. \end{align*}

We can see that the system of equations has indeed changed, but the set of solutions (in this case $\{(2,2)\}$) is preserved.

---

To prove this: If $\mathbf{x}$ satisfies equations $E_1$ and $E_2$, then it satisfies equations $E_1$ and $E_1+E_2$. Conversely, if $\mathbf{x}$ satisfies equation $E_1$ and $E_1+E_2$, then it satisfies equations $E_1$ and $(E_1+E_2)-E_1$ (which is $E_2$).

We conclude that $\mathbf{x}$ satisfies equations $E_1$ and $E_2$ if and only if $\mathbf{x}$ satisfies equations $E_1$ and $E_1+E_2$.

Thus the set of solutions is preserved.

Answer 2

When you have a system of equations, let's say, lines. If you graph them, you'll see that the lines intercept at a common point. This point is the solution of the system. So, when you create another equation based on the equations of your original system, like, adding one to another, you're creating a totally new line, but the solution will be the same.

Think about this system:

$$2x + 4y = 14$$ $$5x + 2y = 19$$

(The system can be viewed as something like this 'matrix')

It has a solution $S\{x=3, y=2\}$

Now, let's say you get the second line and replace it by the second line minus the first line, so, you know that the second line is $$5x + 2y = 19$$

Both sides of equation show a mode of writing the number $19$. So, let's say you add $19$ to both sides of equation $1$:

$$2x + 4y + \color{Red}{19} = 14 + \color{Red}{19}$$

Well, I can do it, right? So, $19$ can also be written as $5x + 2y$ (in our system), so let's replace the $19$ of the first side of the equation by $5x + 2y$:

$$2x + 4y + \color{Red}{5x + 2y} = 14 + \color{Red}{19}$$

Now by adding the equal therms we have a third equation to our system:

$$7x + 6y = 33$$

You see? You added one equation to another! :)

That also share the solution $S\{x=3, y=2\}$. Of course, this will be a new line, but in the system of equations you only care about the solutions to the system. It doesn't matters if it will be a different line. You've just found another line that intercepts your system at the solution.

So you changed your system by replacing the second line by the second line plus the first line

If you multiply the two sides of a row, it will still work, because you're getting another equation that also shares the same solution, as I shown here.

When you work in Linear Algebra, you don't solve directly on systems, but I think you're seeing it as something like a matrix. This is just a way to work with systems without having to write the $x, y, ...$ coefficients all the time.

So you had this system of lines:

Then you created a new system with the third equation:

But all them has the same solution

Answer 3

Examples with only $2\times 2$ linear systems may be misleading, albeit illuminating.

Consider, for simplicity, only rows $R_1$ and $R_2$ of a matrix $A$ representing a linear system. When you change $R_2$ with the result of adding to it $R_1$ multiplied by $d$, the linear system changes, clearly every solution of the old system is a solution of the new one. Indeed, if $x_1$, $x_2$, $\dots$, $x_n$ are numbers such that

$$ a_{11} x_1 + a_{12} x_2 + \dots + a_{1n} x_n = c_1 $$ and $$ a_{21} x_1 + a_{22} x_2 + \dots + a_{2n} x_n = c_2 $$ then $$ (a_{21}+da_{11}) x_1 + (a_{22}+da_{12}) x_2 + \dots + (a_{2n}+da_{1n}) x_n = c_2 + dc_1 $$ Now, call $B$ the new matrix and apply to it the operation “sum to its second row the first one multiplied by $-d$”. Then the same reasoning applies and any solution of the system represented by $B$ is also a solution of the system represented by the resulting matrix.

But what's the resulting matrix? It's precisely $A$.

Thus the two systems have the same solution set.

The same reasoning applies when you do this in general, with the limitation of using two distinct rows. Otherwise you could end up with summing to a row its opposite, which is the same as multiplying the row by $0$, which is not a legal row operation.

For the same reasons, also the other two types of row operations don't change the solution set: they are reversible.

You'll learn that doing an elementary row operation on a matrix $A$ is the same as multiplying the matrix by a suitable invertible matrix, so the operation can be reversed simply by multiplying the resulting matrix by the inverse of the “elementary matrix” used beforehand.

This has the consequence that a matrix $A$ can be represented written as product of “simpler” matrices: some people write this as $$ A=P^TLU $$ where $P$ is a “permutation matrix” (corresponding to the swap row operations needed to bring $A$ in row echelon form), $L$ is lower triangular and $U$ is the row echelon form. Both $P$ and $L$ are invertible and it's really easy to write down their inverses. Such a decomposition has many applications because $P$, $L$ and $U$ carry information about $A$ in a easily usable format.

Answer 4

I don't know the mathematical proof off hand, but it helped me to think of things with an analogy. Let's take the equations $4x+3y=24$ and $3x+4y=25.$ Assume that $x$ and $y$ each represent set quantities of apples. We can represent equations with $3$ piles, a pile of the first term (say, $4x$ apples), a pile of the second term (say, $3y$ apples), and the total amount of apples you would have if you combined the piles ($24$ apples). Now let's say we want to add together these $2$ equations. We have a pile of $4x$ apples, a pile of $3y$ apples, a pile of $3x$ apples and a pile of $4y$ apples. If we combine the $4x$ and $3x$ piles, and the $3y$ and $4y$ piles, we've essentially added the $2$ equations together. If you then combine these $2$ new piles, even if you don't know the values of $x$ and $y$, you know to a certainty that the new pile must contain $24+25$ apples. You've essentially added everything together, so $(4x+3y)+(3x+4y) = 24+25$.

I hope this helps!