Gaussian Elimination PDF

Gaussian elimination This is by far the most important algorithm we learned so far (everything else is based on this algorithm). It allows us to solve systems of linear equations by following these steps: 1. write the system as an augmented matrix 2. perform elementary operations (of one of th...

Gaussian elimination This is by far the most important algorithm we learned so far (everything else is based on this algorithm). It allows us to solve systems of linear equations by following these steps: 1. write the system as an augmented matrix 2. perform elementary operations (of one of the three types – switch two rows, multiply a row by a non-zero number, add to one row another row multiplied by a non-zero number) and bring the augmented matrix to a row echelon or a reduced row echelon form. 3. If you have a row [0, 0,... , 0|a] (where a is some non-zero number) in a row echelon form, the system has no solutions (inconsistent). 4. If you brought the matrix to a reduced row echelon form (RREF), you can just write down the solution by looking at the coefficients in the resulting RREF. If you brought a matrix to row echelon form (REF) you need to do back-substitution to get the solution. Some other facts you should remember: RREF of any matrix is unique. REF is not. Rank of a matrix is the number of leading ones in its RREF. It is also the number of leading ones in any REF (even though the REFs are not unique, they all have the same number of leading ones, so rank is well-defined). Homogeneous systems are the ones with the right-hand side equal to zero. They are always con- sistent (as the zero vector is always a solution – this is called the trivial solution). Homogeneous system of size m × n and rank r has n − r parameters and n − r basic solutions. Thus homogeneous system of size m × n and rank r has a unique solution (which is zero, or trivial) if and only if r = n. Interesting to remember: 1