# Prove equivalence of elementary operations in Gauss Algorithm

1. Oct 27, 2013

### 4Fun

1. The problem statement, all variables and given/known data

Prove that replacing one equation in a system of linear equations by a non-zero multiple of itself does not change the solution of the system.

3. The attempt at a solution

I'm still relatively new to proofs, so this is what I have come up with:

Let S be a system of n equations and n unknowns and assume that S has a unique solution(is this assumption too strong?). Also assume that the other two elementary operations do not change the solution of S.
Let j be an arbitrary row and multiply row j by a non-zero constant k.
Now during the elimination process: Let i be the row that includes the current pivot element. Assume i<j, so that the element in the column of the pivot element in row j has to be eliminated. Assume that prior to multiplying row j by the constant k, you would have had to add a-times the i-th row to row j to eliminate the specific element. Since row j was multiplied by k, you now have to add a*k-times row i to row j in order to eliminate that element.

Well now I'm wondering wether this is basically sufficient to prove equivalence, or whether I should use induction to prove that this is valid for all elimination steps?

2. Oct 27, 2013

### brmath

You are doing quite well -- your proof is basically fine. You need not assume that S has a unique solution; if it doesn't multiplication of a row won't change that. You wrote one thing you didn't quite mean (it's really more like a typo) at the bottom of the second paragraph; you have to add a*k... I'm sure you meant multiply.

You were quite right to say that you were assuming the other elementary operations do not affect the solution. You do not need induction because you did not reference the size of the system in your proof.

One way to make these proofs clearer is to write as much as you can in mathematical notation. You can say -- let's consider the case that n = 3, without loss of generality. Write that the jth row is qx + ry + sz = t and after multiplication by k you have qkx+ rky+ skz = tk. Then say whatever you have to say about the ith row, again in mathematical notation.

If you are nervous about writing "without loss of generality" because you aren't sure whether that is the case, you write that the jth row is $a_1x_1 + a_2x_2 + ... + a_nx_n = y_j$.