Given a system of linear equations:[br][br][math] \left\{\begin{eqnarray} a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n & = & b_1 \\[br]a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n & = & b_2 \\[br]\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots & \cdots & \\[br]a_{m1}x_1+a_{m2}x_2+\cdots+a_{mn}x_n & = & b_m \end{eqnarray} \right.[/math],[br][br]where [math]a_{ij}, \ i=1,\ldots,m, \ j=1,\ldots,n[/math] are real numbers. We want to find an efficient way to solve the system for the solution(s). Let us first consider a very simple example:[br][br][math]\left\{\begin{eqnarray}x_1-2x_2 &=& -1 \\ -2x_1+6x_2&=&6\end{eqnarray}\right.[/math][br][br]In high school, we already learned how to solve this system: We can multiple the first equation by 2 and add to the second equation to eliminate the variable [math]x_1[/math]. Then we get[br][br][math]\left\{\begin{eqnarray}x_1-2x_2 &=& -1 \\ 2x_2&=&4\end{eqnarray}\right.[/math][br][br]The solution to the system can be easily obtained by first solving the second equation for [math]x_2[/math] and then substitute the value of [math]x_2[/math] to the first equation to find the value of [math]x_1[/math]. Hence the solution is [math]\left(x_1,x_2\right)=\left(3,2\right)[/math].[br][br]This variable-eliminating process can be vastly generalized to deal with any system of linear equations of any size. Such generalization is called [b]Gaussian elimination[/b]. The action of using one equation to eliminate a variable in another equation is a special case of the so-called [b]elementary row operation[/b]. And the system in the last step that we can easily solve for the solution is said to be in [b]echelon form[/b]. This is the "workhorse algorithm" that all students must learn well when studying linear algebra because almost every problem in linear algebra involving computation is about solving a linear system of some kind. [br]

For a system of linear equations, all the essential information is contained in the coefficients [math]a_{ij}[/math] and the constants [math]b_i[/math]. Therefore, we can compactly represent the system as a matrix. First of all, we have[br][br][math]A=\begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ [br]\vdots & \vdots & \ldots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}[/math][br][br][math]A[/math] is called the [b]coefficient matrix[/b] of the system. The [math]j^{\text{th}}[/math] column contains all the coefficients of the variable [math]x_j[/math] in all the linear equations, where [math]j=1,\ldots,n[/math]. Then we can add the column of constant [math]b_i[/math] to the right in the coefficient matrix and separate it from the coefficients by a vertical line to form the [b]augmented matrix[/b] of the system:[br][br][math]\left(\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ [br]\vdots & \vdots & \ldots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m\end{array}\right)[/math][br][br]([u]Note[/u]: The vertical line may not be drawn in augmented matrices in some textbooks.)[br][br]Gaussian elimination is an algorithm of transforming an augmented matrix into the one in echelon form.[br][br]