1
$\begingroup$

Sorry if this is very simple, I just could not find a good explanation for this particular hangup on Gaussian elimination online.

Let's say that I am trying to solve a system of linear equations using a 3x3 matrix (let's call it $A$ ) and a vector $r$ corresponding to the equation's output values.

$A\\\begin{bmatrix}1&1&3\\1&2&4\\1&1&2\end{bmatrix}$ $s\\\begin{bmatrix}a\\b\\c\end{bmatrix}$ $r\\\begin{bmatrix}15\\21\\13\end{bmatrix}$

One method to do this is by first using Gaussian elimination to convert $A$ into echelon form, then use back substitution to find the values of $a$,$b$, and $c$.

When using reduction, we can add a row of $A, s, r$ onto another row, or multiply a row by a non 0 constant. My instructor has said that this "doesn't change" change the value of the system of equations. E.g.:

subtracting row 1 from row 3

$A\\\begin{bmatrix}1&1&3\\1&2&4\\0&0&-1\end{bmatrix}$ $s\\\begin{bmatrix}a\\b\\c\end{bmatrix}$ $r\\\begin{bmatrix}15\\21\\-2\end{bmatrix}$

multiplying row 3 by -1

$A\\\begin{bmatrix}1&1&3\\1&2&4\\0&0&1\end{bmatrix}$ $s\\\begin{bmatrix}a\\b\\c\end{bmatrix}$ $r\\\begin{bmatrix}15\\21\\2\end{bmatrix}$

How is it that we're not changing any values here? I understand if we're doing an operation on both sides of an equation it would still be true because the $=$ would still hold, but with matrices and vectors there's no = operator. It seems like we're basically making arbitrary changes to the matrix, which would scale the vector differently.

$\endgroup$
  • $\begingroup$ But there is an = operator! You should properly write the system as $As=r$. $\endgroup$ – Hans Lundmark May 10 '19 at 4:18
1
$\begingroup$

The reason it is valid here is because your $r$ vector is what would be on the other side of the equals sign. You've put it into a form that allows you to use a method that you understand (row reduction) to get your result. The $r$ actually does belong on the other side of the equals sign, because then you can perform matrix multiplication between $A$ and $s$ to get a 3x1 matrix, exactly like $r$, and then you can compare terms. I think the idea here is you've put it in this form simply because it's easier for you to row reduce this way.

$\endgroup$
  • 1
    $\begingroup$ This is not what the OP is asking. The question is why row reduction preserves solution sets. $\endgroup$ – symplectomorphic May 10 '19 at 3:31
  • $\begingroup$ This is exactly what OP is asking, you're row reducing an artificial matrix that HAS the solution. OP even says "I undestand if we did the same thing on the other side of the = sign, but we do not have one here" and I have clarified that we actually DO. $\endgroup$ – Kraig May 10 '19 at 12:25
1
$\begingroup$

Adding rows to other rows and multiplying a row by a nonzero scalar are just equivalent to doing these operations to the system of equations.

When we form an augmented matrix as you have, the entries in each row of the matrix correspond to the coefficients of each equation. Now, would you agree that we can add two simultaneous equations and get another, equivalent equation? Would you agree that we can multiply any of the equations by a constant? There may be no visual ‘$=$’ in the matrix, but when we have finished row reducing, we can always write it back out as a system of equations, so it’s exactly equivalent.

For example, if we have the system

$$x+y = 1$$ $$2x -y = 3$$

it should be fairly obvious that if we add the first to the last we get

$$3x = 4$$

for which the solutions (for $x$) are the same as the first two equations taken together.

Row reduction is just a natural extension of the kind of manipulation we could do by hand when solving linear simultaneous equations.

It is important to note that elementary row operations do fundamentally change the properties of matrices/vectors (the determinant being one example). It’s just that if you are using the matrix as a way of encoding a system of equations, it won’t change the solution set of the system.

$\endgroup$
1
$\begingroup$

This is not only linear algebra, but general concept of quality.

Interpret the three variables $x,y,x$ in an equation like $3x+4y + 5z=100$ as the prices of three different products. The coefficients as quantities of the products purchased. So this equation means total expenditure of 100 roubles is incurred in making these purchases.

If another person purchased 4 times the quantity of each of these products the equation of expenditure for him would be $12x + 16y + 20z= 400$. If a particular value of variables x,y,z makes the first equation valid it would make the second equation also valid (and vice versa).
This corresponds to the Gaussian operation of multiplying which does not change the solution.

Suppose third person bought one each of these product (with the same price) and incurred an expenditure of 21 roubles this would lead to an equation $x+y+z=21$.

Now subtracting third equation from first we get $2x+3y+4z=79$, this equation expresses the cost involved in the extra purchases made by the first person over the third person. SO all these equations are valid for the same values of $x,y,z$.

So Gaussian elimination uses these operations which do not alter the solutions, to arrive at an alternate set of equations admitting same solution, but with the advantage that many coefficients are zero making in easy to solve the newer system.

$\endgroup$
0
$\begingroup$

There are three elementary row operations: (1) swapping two rows, (2) multiplying a row by a nonzero scalar, and (3) adding a multiple of one row to another row.

It is obvious that the first operation does not change the solution set.

To see this for the second operation, note that every solution to $a=b$ is a solution to $ca=cb$ (where $c$ is a scalar), and conversely if $c$ is nonzero every solution to $ca=cb$ is a solution to $a=b$.

To see this for the third operation, it suffices to show that the system of equations $a=b$ and $c=d$ has the same solution set as the system $a+ec=b+ed$ and $c=d$. This is simple: the second system certainly follows from the first, and the first system follows from the second by substituting $c=d$ into the first equation and then subtracting $ec$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.