Suppose we have a system of linear equations whose augmented matrix is row reduced to the following matrix in echelon form:[br][br][math]\left(\begin{array}{ccc|c} 2 & -1 & 3 & 0 \\0 & -2 & 1 & 3 \\ [br]0 & 0 & 3 & 5 \end{array}\right)[/math][br][br]We can write down the corresponding linear system as follows:[br][br][math]\left\{\begin{eqnarray} 2x_1-x_2+3x_3&=&0\\ -2x_2+x_3 &=&3 \\ 3x_3 &=&5\end{eqnarray}\right.[/math][br][br]This linear system can be solved by [b]back-substitution[/b]: Starting from the bottom equation, we get [br][math]x_3 = \frac53[/math]. Then substitute it into the equation above it, we get [math]-2x_2+\frac53=3 \Rightarrow x_2=-\frac23[/math]. Finally, we substitute the values of [math]x_2,x_3[/math] to the first equation and get [math]2x_1-\left(-\frac23\right)+3\left(\frac53\right)=0\Rightarrow x_1=-\frac{17}{18}[/math]. That is, the original linear system has a unqiue solution [math](x_1,x_2,x_3)=\left(-\frac{17}{18},-\frac23,\frac53\right)[/math].[br][br]

Take a look at the following augmented matrix in echelon form:[br][br][math]\left(\begin{array}{ccc|c} 3 & -8 & 2 & 1 \\0 & 5 & -2 & 1 \\ [br]0 & 0 & 0 & 2 \end{array}\right)[/math][br][br]Its corresponding linear system is as follows:[br][br][math]\left\{\begin{eqnarray} 3x_1-8x_2+2x_3&=&1\\ 5x_2-2x_3 &=&1 \\ 0 &=&2\end{eqnarray}\right.[/math][br][br]You can see that the last equation can never be satisfied and this implies that this linear system has [u]no solution[/u]. A linear system is said to be [b]inconsistent[/b] if it has no solution. More generally, we have the following theorem:[br][br][u]Theorem[/u]: A linear system is inconsistent if and only if its augmented matrix (not necessarily in echelon form) has a row of the form [math]\left[0 \ \cdots \ 0 \ | \ b\right] [/math] with [math] b\ne 0[/math], or equivalently, the rightmost column of the augmented matrix is a pivot column.[br][br][br]

Consider the following augmented matrix:[br][br][math]\left(\begin{array}{ccccc|c} 1 & -2 & 2 & 1 & 6 & 2 \\0 & 0 & -3 & 1 & 0 & 5 \\ [br]0 & 0 & 0 & 2 & -1 & 1 \end{array}\right)[/math][br][br]The corresponding linear system looks like this:[br][br][math]\left\{\begin{eqnarray} x_1-2x_2+2x_3+x_4+6x_5&=&2\\ -3x_3+x_4 \ \ \ \ \ \ \ \ &=&5 \\ 2x_4-x_5 &=&1\end{eqnarray}\right.[/math][br][br]Again, we will use the back-substitution to solve the linear system. But we observe that there are more variables than the equations in the system. Therefore, we expect that there will be more than one solution to the system. First, we classify the variables in the system into two types:[br][br][b]Basic variable[/b] - a variable corresponding to a pivot column[br][b]Free variable[/b] - a variable corresponding to a non-pivot column[br][br]In our example, [math]x_1,x_3,x_4[/math] are basic variables and [math]x_2,x_5[/math] are free variables. Free variables are the ones that we can assign any value to them (that’s why they are called “free” variables). We can use the back-substitution to express the basic variables in terms of the free variables as follows:[br][br]From the bottom equation, we have [math]x_4=\frac12+\frac12 x_5[/math]. Substituting it into the equation above it, we get [math]-3x_3+\left(\frac12+\frac12 x_5\right)=5\Rightarrow x_3=-\frac 32 +\frac 16x_5[/math]. Then we substitute the expressions for [math]x_4,x_3[/math] into the remaining equation and get [math] x_1-2x_2+2\left(-\frac 32 +\frac 16x_5 \right)+\left(\frac12+\frac12 x_5\right)+6x_5=2\Rightarrow x_1=\frac 92+2x_2-\frac{41}6 x_5[/math]. Usually, we express free variables as parameters in the solution: Let [math]s,t[/math] be real numbers such that [math]x_2=s,x_5=t[/math]. Then the solutions to the system can be written as follows:[br][br][math]\left\{\begin{eqnarray}x_1 & = & \frac 92+2s-\frac{41}6 t \\ x_2 & = & s \\ x_3 & = & -\frac 32 +\frac 16t \\ x_4 & = & \frac12+\frac12 t \\ x_5 & = & t\end{eqnarray}\right.[/math][br][br]where [math]s,t[/math] are any real numbers. Hence, this linear system has infinitely many solutions.[br][br][br]All in all, the general procedure for solving a system of linear equation is as follows:[br][br][list=1][*]Write down the augmented matrix of the given linear system[/*][*]Use the row reduction algorithm to transform the augmented matrix to the one in echelon form.[/*][*]If a row of the form [math]\left[0 \ \cdots \ 0 \ | \ b\right] [/math] with [math] b\ne 0[/math] appears in any row reduction step, we can stop the row reduction and conclude that the linear system is inconsistent i.e. no solution exists. [/*][*]If the row of the form described in step 3 does not appear in the matrix in echelon form, then the system is consistent.  [/*][*]Classify the variables into basic and free variables.[/*][*]Use back-substitution to find the solution(s) to the linear system. If there is no free variable, the linear system has a unique solution. If there exists at least one free variable, the linear system has infinitely many solutions, which can be expressed in terms of the parameter(s) assigned to the free variable(s).[/*][/list][br][u]Remark[/u]: If you obtain a matrix in reduced echelon form in step 2, then you can easily write down the solutions (if exist) without the need of back-substitution.[br][br]

Suppose a linear system has infinitely many solutions i.e. there exists at least one free variable when the corresponding augmented matrix is row reduced to the one in echelon form. We can express the solutions more elegantly in the so-called [b]parametric vector form[/b].[br][br]Let’s consider the previous example. We first express the linear system corresponding to the augmented matrix in echelon form as a matrix equation of the form [math]Ax=b[/math]:[br][br][math]\begin{pmatrix}1 & -2 & 2 & 1 & 6 \\ 0 & 0 & -3 & 1 & 0\\ 0 & 0 & 0 & 2 & -1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{pmatrix}=\begin{pmatrix}2 \\ 5 \\ 1 \end{pmatrix}[/math][br][br]Then we write the solutions to this matrix equation in vector form:[br][br][math] \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{pmatrix}= \begin{pmatrix}\frac92+2s-\frac{41}6t \\ s \\ -\frac32+\frac16 t \\ \frac12+\frac12 t \\ t \end{pmatrix}=\begin{pmatrix}\frac92 \\ 0 \\ -\frac32 \\ \frac12 \\ 0\end{pmatrix}+s\begin{pmatrix}2 \\ 1 \\ 0 \\ 0 \\ 0\end{pmatrix}+t\begin{pmatrix}-\frac{41}6 \\ 0 \\ \frac16 \\ \frac12 \\ 1\end{pmatrix}[/math][br][br]This is the parametric vector form of the solutions to the linear system.[br][br]We can take a closer look at the above solutions. For simplicity, we write the above solutions as [math]x=p+su+tv[/math], where [math]p[/math] is the first column vector, [math]u[/math] and [math]v[/math] are the column vectors scalar multiplied by the parameters [math]s[/math] and [math]t[/math] respectively. By definition, [math]Ax=b\Longrightarrow A\left(p+su+tv\right)=Ap+A\left(su+tv\right)=b[/math] for any [math]s[/math] and [math]t[/math]. In particular, we set [math]s=t=0[/math]. Then [math]Ap=b[/math]. We usually call the vector [math]p[/math] a [b]particular solution[/b] of [math]Ax=b[/math]. Hence, we have[br][br][math]b+A(su+tv)=b\Rightarrow A\left(su+tv\right)=0[/math][br][br]That is, for any [math]s[/math] and [math]t[/math], [math]su+tv[/math] is a solution to [math]Ax=0[/math]. Any matrix equation of the form [math]Ax=0[/math] is called a [b]homogeneous equation[/b]. Zero vector is always a solution to any homogeneous equation, which is usually called the [b]trivial solution[/b]. Any nonzero solution to a homogeneous equation is called a [b]nontrivial solution[/b]. In this example, [math]su+tv[/math] is certainly a nontrivial solution of [math]Ax=0[/math]. In fact, it can be shown that the set of solutions of [math]Ax=0[/math] is [math]\text{Span}\{u,v\}[/math] and any solution of [math]Ax=b[/math] can be written as the sum of a particular solution and a solution of the corresponding homogeneous equation [math]Ax=0[/math].[br]

Solve the following system of linear equations:[br][br][math]\left\{\begin{eqnarray}2x_1+2x_2-2x_3 &=& 8 \\ 2x_1+x_2+3x_3 &=& 0 \\ x_2-5x_3 &=& 8 \end{eqnarray}\right.[/math][br][br](You can make use of the result from the exercise in the previous page.)