Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

When using Gaussian elimination to solve a system of linear equations , we can add a multiple of one equation to another and have an equivalent equation

In other words , If we have a system of three linear equations L1 , L2 and L3 we can multiply L1 by a nonzero multiple and add it to L2 to get an equivalent equation to L2

why is that valid ?

share|improve this question
    
Proof is easy, show soloution of one system is also soloution of other. Have you tried it ? –  pritam Sep 23 '12 at 13:22
4  
You do not generally get an equation that is equivalent to $L_2$. The system of equations, however, is equivalent to the original system. –  David Mitra Sep 23 '12 at 13:26
    
@Akram Please do not write comments as answers. –  Bill Dubuque Sep 24 '12 at 2:27
add comment

4 Answers

If we have two equations $A$ and $B$, multiplying $A$ by $k$ and adding it to $B$ gives the equation $kA+B$. Conversely, if we have $A$ and $kA+B$, then subtracting $kA$ from $kA+B$ gives $B$. This means that the system with equations $A$ and $B$ and the system with equations $A$ and $kA+B$ are equivalent. Note that this argument works even when $k=0$, in which case there is no change.

For example, if $A$ is $a_1x_1+...+a_nx_n=x$ and $B$ is $b_1x_1+...+b_nx_n=y$, then $A+kB$ is simply $(a_1+kb_1)x_1+...+(a_n+kb_n)x_n=x+ky$.

share|improve this answer
    
[[If we have two equations A and B, multiplying A by k and adding it to B gives the equation kA+B. Conversely, if we have A and kA+B, then subtracting kA from kA+B gives B. This means that the system with equations A and B and the system with equations A and kA+B are equivalent ]] WHY ??? –  Akram Hassan Sep 23 '12 at 23:11
add comment

Say $x$ is such that $f(x) = g(x) = 0$ i.e. $x$ solves the equations $f$ and $g$. Let $h = f + \lambda g$ be a linear combination of the two equations. Notice that $h(x) = 0 + \lambda0 = 0$. This proves that every solution of $f, g$ is also a solution of $h, g$. Finally notice that $f = h - \lambda g$ and thus, by the same argument, every solution of $h, g$ is also a solution of $f, g$.

share|improve this answer
    
can you explain more ? –  Akram Hassan Sep 23 '12 at 22:52
    
By definition, systems of equations are equivalent if they have the same roots. That is what I prove. You'll have to point out what exactly is unclear. –  Karolis Juodelė Sep 24 '12 at 5:03
add comment

If $f(x) = a$ and $g(x) = b$, then $c g(x) = c \cdot b$, and $$\begin{align*}f(x) + c g(x) &= a + c g(x) \\&= a + c\cdot b,\end{align*}$$ by nothing more than substitution. As to equivalence, this follows from the fact that you can just "re-subtract" the equation $cg(x) = cb$ again.

share|improve this answer
    
by nothing more than substitution. As to equivalence, this follows from the fact that you can just "re-subtract" the equation cg(x) = cb ... what does that mean ? –  Akram Hassan Sep 23 '12 at 22:52
    
Instead of adding $cg(x) = cb$, simply subtract $cg(x)=cb$. The result will once again be the equation $f(x)=a$. –  Niel de Beaudrap Sep 23 '12 at 23:22
add comment

Let's consider the system $$ \begin{pmatrix} 1 & 1 \\ 2 & 3\end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 5 \\ 8\end{pmatrix}.$$

The shortcut step in Gaussian elimination tells you to subtract 2 times the first row from the second, yielding $$ \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 5 \\ -2\end{pmatrix}.$$

It's not so hard to see that this system is equivalent, but what are we actually doing behind the handwaving?

What's really happening is that we're left multiplying both sides of the equation by a new matrix:

$$\begin{pmatrix} 1 & 0 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 2 & 3\end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} 5 \\ 8\end{pmatrix}.$$

You might notice that in this case, the new matrix is lower triangular, and when we carry out the Gaussian elimination step, the resulting matrix is upper triangular.

In the $2 \times 2$ case, there is a single sub-diagonal element in any matrix. You may also notice that the Gaussian elimination requires only a single "step". If we extend this to $3 \times 3$ matrices, you will notice that you need to do 3 computations -- and there happen to be three sub-diagonal elements in any $3\times 3$ matrix. This is not a coincidence. It turns out, in fact, that Gaussian elimination is innately linked to LU decomposition -- the transformation of a full-rank square matrix into the product of lower and upper triangular matrices. This is very useful, because triangular matrices are spectacularly easy to invert.

The shorthand method for Gaussian elimination gives you the following system: $$LAx = Lb.$$

But we could just as easily obtain $$Ax=b \Longrightarrow LUx = b \Longrightarrow Ux = L^{-1}b.$$

The key difference as to which operation to choose is whether you're trying to invert $A$ or solve $Ax=b$. For solving $Ax=b$, the shorthand Gaussian elimination turns out to be easiest.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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