Given an augmented matrix of a system of m linear equations in n variables, we can do three elementary row operations on it. It turns out those operations can be regarded as the multiplication of some very specific n x n square matrices to the augmented matrix. Those n x n square matrices are called the [b]elementary matrices[/b].[br][br][br]Suppose the augmented matrix is [math]\left( A \ | \ b \right)[/math], where [math]A[/math] is the m x n coefficient matrix and [math]b[/math] is the column matrix formed by the constants on the right hand side of the linear equations in the system. We consider the three elementary row operations one by one as follows:[br][br][b]Interchange i[sup]th[/sup] and j[sup]th[/sup] rows[/b]:[br][br]Let [math]T_{i,j}=\begin{pmatrix}1 & & & & & & \\ & \ddots & & & & & \\ & & 0 & & 1 & & \\ & & & \ddots & & & \\ & & 1 & & 0 & & \\ & & & & &\ddots & \\ & & & & & & 1 \end{pmatrix} [/math], where the two off-diagonal "1"s are in the i[sup]th[/sup] and j[sup]th[/sup] rows. Then we multiply it to the augmented matrix as follows:[br][br][math]T_{i,j}\left( A \ | \ b \right)=\left( T_{i,j}A \ | \ T_{i,j}b \right)[/math][br][br]Then [math]\left( T_{i,j}A \ | \ T_{i,j}b \right)[/math] is the augmented matrix after interchanging i[sup]th[/sup] and j[sup]th[/sup] rows.[br][br][br][b]Multiply i[sup]th[/sup] row by a nonzero constant[math]k[/math][/b]:[br][br]Let [math]D_i(k)=\begin{pmatrix}1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & & & & \\ & & & k & & & \\ & & & & 1 & & \\ & & & & &\ddots & \\ & & & & & & 1 \end{pmatrix} [/math], where the "[math]k[/math]" is in the i[sup]th[/sup] row. Then we multiply it to the augmented matrix as follows:[br][br][math]D_i(k)\left( A \ | \ b \right)=\left( D_i(k)A \ | \ D_i(k)b \right)[/math][br][br]Then [math]\left( D_i(k)A \ | \ D_i(k)b \right)[/math] is the augmented matrix after multiplying the i[sup]th[/sup] row by [math]k[/math].[br][br][br][b]Replace i[sup]th[/sup] row by the sum of itself and [/b][math]k[/math][b] times j[sup]th[/sup] row[/b]:[br][br]Let [math]L_{i,j}(k)=\begin{pmatrix}1 & & & & & & \\ & \ddots & & & & & \\ & & 1 & & & & \\ & & & \ddots & & & \\ & & k & & 1 & & \\ & & & & &\ddots & \\ & & & & & & 1 \end{pmatrix} [/math], where the "[math]k[/math]" is in the [math](i,j)[/math]position. Then we multiply it to the augmented matrix as follows:[br][br][math]L_{i,j}(k)\left( A \ | \ b \right)=\left( L_{i,j}(k)A \ | \ L_{i,j}(k)b \right)[/math][br][br]Then [math]\left( L_{i,j}(k)A \ | \ L_{i,j}(k)b \right)[/math] is the augmented matrix after replacing i[sup]th[/sup] row by the sum of itself and [math]k[/math] times j[sup]th[/sup] row.[br][br][br][u]Remark[/u]: As we know, elementary row operations are reversible. Therefore, any elementary matrix is invertible and its inverse is also an elementary matrix.[br][br][br]In the applet below, you can use an elementary matrix [math]E[/math] to do various row operations on a 5 x 6 matrix [math]A[/math] by computing [math]EA[/math]. Find the elementary matrix for each of the following row operations:[br][br][list=1][*]Interchange 1st row and 3th row.[/*][*]Multiply 5th row by 2.[/*][*]Replace 2nd row by the sum of itself and 3 times 1st row.[br][/*][/list][br]

Given an augmented matrix of a linear system [math]\left( A \ | \ b\right)[/math], the corresponding matrix equation is [math]Ax=b[/math]. Whenever we do a row operation on the augmented matrix, there exists an elementary matrix [math]E[/math] such that the new augmented matrix is [math]\left(EA \ | \ Eb\right)[/math] and the new matrix equation is [math]EAx=Eb[/math].[br][br]If [math]x[/math] solves the matrix equation [math]Ax=b[/math], it certainly solves [math]EAx=Eb[/math]. Conversely, if [math]x[/math] solves [math]EAx=Eb[/math], then it solves [math]E^{-1}EAx=E^{-1}Eb[/math], which is [math]Ax=b[/math]. Therefore, both linear systems must have the same set of solutions.[br][br]Suppose the augmented matrix is row reduced to the one in echelon in r steps. Then there exists a sequence of elementary matrices [math]E_1, E_2, \ldots, E_r[/math] such that [math]\left( E_r \cdots E_1A \ | \ E_r \cdots E_1b \right)[/math] is in echelon form, and its corresponding matrix equation is [math] E_r \cdots E_1Ax=E_r \cdots E_1b[/math]. Using the above fact repeatedly, we can see that its set of solutions is the same as that of the original matrix equation [math]Ax=b[/math]. More generally, if two linear system are row equivalent, they have the same set of solutions. That is why Gaussian elimination works.