User:Jim.belk/Draft:Row reduction

In linear algebra, row reduction is a method for solving systems of linear equations. The system is converted to an augmented matrix, and elementary row operations are applied until the matrix reaches some simplified form (such as row echelon form or reduced row echelon form). The most common algorithms for row reduction are Gaussian elimination and Gauss-Jordan elimination.

Row reduction has many other applications throughout linear algebra. It can be used to determine a basis for the row space of a matrix, and hence determine the rank. Row reduction is involved in computing the determinant of a square matrix, and can be used to find the inverse if the matrix is nonsingular. Row and column reduction are also important in abstract algebra, especially in the study of linear groups, the theory of abelian groups and modules, and in homological algebra.

Elementary row operations

An elementary row operation is any one of the following moves:

1. Swap two rows of a matrix.
2. Multiply a row of a matrix by a nonzero constant.
3. Add to one row of a matrix some multiple of another row.

Row reduction is the process of simplifying the form of a matrix through the application of elementary row operations. Any matrix obtained through row reduction is row equivalent to the original.

Solving linear systems

Row reduction is most commonly used to solve systems of linear equations. Given a system:

${\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&b_{m}\\\end{alignedat}}$

we write the corresponding augmented matrix:

$\left[{\begin{array}{cccc|c}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{array}}\right]{\text{.}}$

Applying an elementary row operations to this matrix corresponds to performing algebraic manipulations on the linear system. Specifically:

1. Swapping two rows of the matrix corresponds to changing the order of the equations.
2. Multiplying a row by a constant corresponds to multiplying both sides of an equation by a constant.
3. Adding a multiple of one row to another corresponds to adding a multiple of one equation to another.

The goal is to perform row reductions until the system takes on a particularly simple form.

Example

Consider the following linear system:

${\begin{alignedat}{5}x&&\;+\;&&2y&&\;=\;&&3\\-2x&&\;+\;&&3y&&\;=\;&&8\end{alignedat}}$

We write this system as an augmented matrix, and perform a certain sequence of elementary row operations:

$\left[\!{\begin{array}{rr|r}1&2&3\\-2&3&8\\\end{array}}\!\right]\sim \left[\!{\begin{array}{rr|r}1&2&3\\0&7&14\\\end{array}}\!\right]\sim \left[\!{\begin{array}{rr|r}1&2&3\\0&1&2\\\end{array}}\!\right]\sim \left[\!{\begin{array}{rr|r}1&0&-1\\0&1&2\\\end{array}}\!\right]$

The operations used in this calculation were (1) Add twice the first row to the second (2) Multiply the second row by 1/7 (3) Add –2 times the second row to the first. The result is an augmented matrix that represents a much simpler system of equations:

$x=-1\;\;\;\;{\text{and}}\;\;\;\;y=2{\text{.}}$

Algorithms

Gaussian elimination

Main article: Gaussian elimination

Gauss-Jordan elimination

Main article: Gauss-Jordan elimination