Gauss-Jordan method

Calculating Inverses

When we have a nonhomogeneous system of equations $A \boldsymbol{x}=\boldsymbol{b}$, where $A$ is non-singular, we wish to calculate $A^{-1} \boldsymbol{b}$. One way to find $A^{-1}$ is through Cramer's rule. However, this requires a lot of computation and it is easy to make mistakes. A more efficient method is the Gauss-Jordan method. This uses the row operations in matrices, which were explained previously in this chapter. This approach is illustrated by the following example; consider the system of equations

We express these in matrix form as follows,

where we have included the identity matrix on the RHS. We perform the following row operations $\left(R_{2}-R_{1}\right) \rightarrow\left(R_{2}\right)$ and $\left(R_{3}-R_{1}\right) \rightarrow\left(R_{3}\right)$ in Eq. (10.50) yielding,

The idea is as follows; the solution to $A \boldsymbol{x}=\boldsymbol{b}$ is given by $\boldsymbol{x}=A^{-1} \boldsymbol{b}$ as mentioned before. If we perform row operations such that the matrix on the LHS of (10.50) (i.e. matrix $A$ ) becomes the identity matrix multiplying $\boldsymbol{x}$ then the matrix on the RHS must turn into the inverse of $A$. Performing $\left(R_{1}-2 R_{2}\right) \rightarrow\left(R_{1}\right)$ followed by $\left(R_{3}-3 R_{2}\right) \rightarrow\left(R_{3}\right)$ gives,

Finally, we do $\left(R_{3} / 3\right) \rightarrow\left(R_{3}\right)$ followed by $\left(R_{1}+R_{3}\right) \rightarrow\left(R_{1}\right)$ and $\left(R_{2}-2 R_{3}\right) \rightarrow\left(R_{2}\right)$ which gives,

The matrix on the RHS is therefore $A^{-1}$. To solve for $\boldsymbol{x}$, we need to calculate $A^{-1} \boldsymbol{b}$ which gives $x=11, y=-8$, and $z=3$.

Note that the order in which one may carry out these row operations is not unique. Next we discuss some general principles that may help when applying this technique.

(i) Exchange rows and divide the first row by a scalar in order to get a one in the top lefthand corner;

(ii) Take away multiples of the first row from the other rows to remove dependence on $x$ in the other rows;

(iii) Repeat step (i), but for the second column and second row to ensure we have a one in position 22 ;

(iv) Take away multiples of the second row from the other rows to ensure that we have zeros elsewhere; (v) Repeat column by column.

Example 10.8 Find the inverse of matrix $A$ given by

using the Gauss-Jordan method.

Solution We start by writing the matrix and the identity matrix side by side as,

Next, we perform the row operations $\left(R_{2}-2 R_{1}\right) \rightarrow\left(R_{2}\right)$ and $\left(R_{3}-3 R_{1}\right) \rightarrow\left(R_{3}\right)$ which gives,

We continue with $\left(R_{1}-2 R_{2}\right) \rightarrow\left(R_{1}\right)$ and $\left(R_{3}-2 R_{2}\right) \rightarrow\left(R_{3}\right)$,

We then do $\left(5 R_{2}+3 R_{3}\right) \rightarrow\left(R_{2}\right)$ and divide the resulting $R_{2}$ by 5 ,

Finally, we do $\left(5 R_{1}-7 R_{3}\right) \rightarrow\left(R_{1}\right)$ and divide the resulting $R_{1}$ by 5 and $R_{3}$ by -5 , giving

The matrix that appears on the RHS is $A^{-1}$.

Gaussian elimination

We can solve a system of equations without necessarily obtaining the inverse matrix using Gaussian elimination. The method we follow is the same as in Subsec. 10.5.1 but we reduce the coefficient matrix to upper triangular form. We saw an example of an upper triangular matrix in Subsec. 10.1.2. Further, this approach works whether the matrix is singular or not. We use Eq. (10.50) as an example and in particular the following form,

We undertake $\left(R_{2}-R_{1}\right) \rightarrow\left(R_{2}\right)$ and $\left(R_{3}-R_{1}\right) \rightarrow\left(R_{3}\right)$ as before so that we obtain zeros in the $a_{21}$ and $a_{31}$ positions, as follows

To make the coefficient matrix in (10.55) upper triangular we need to have a zero in the $a_{32}$ position. We take $\left(R_{3}-3 R_{2}\right) \rightarrow\left(R_{3}\right)$ yielding,

Equation (10.56) gives us the equations to solve for $x, y$, and $z$. We see from the last row that $z=3$, from the second row,

and from the first row,

We now revisit the matrix equation in Eq. (10.43) where we know the coefficient matrix to be singular. We first eliminate the final row by taking $\left(R_{3}-R_{1}-R_{2}\right) \rightarrow\left(R_{3}\right)$,

We then let $\left(3 R_{2}+R_{1}\right) \rightarrow\left(R_{2}\right)$ which gives,

We see from the last row that for consistency, we need $c=4$. We again let $z=\lambda$ the parameter for the under-determined equation and we have $7 y=7-7 \lambda$, so that $y=1-\lambda$ in the second equation and in the first equation, we have $3 x=3 \lambda$ so that $x=\lambda$ as before. The process of solving upper triangular systems as above is referred to as back substitution. The process of obtaining the upper triangular form is known as forward elimination.

Exercises

1. Solve the system of equations,

giving different cases for $a$ and $b$.

Cramer's rule revisited

Recall that Cramer's rule relates the inverse of a matrix to its determinant and adjugate matrix [refer to Eq. (10.26)]. As previously mentioned, the solution to the matrix equation $A \boldsymbol{x}=\boldsymbol{b}$ is given by

Using Eq. (10.26), we can write the solution as,

Cramer's rule can be used to solve systems of equations via the calculation of determinants and their ratio. Let us look at a quick example before generalising the method. Consider the following $2 \times 2$ matrix equation,

Solving for $x$ and $y$ from the system of equations, i.e.

we obtain

Equations (10.61) can be expressed in terms of the following ratios of determinants

where,

Note that in the expression for $\Delta_{x}$, the coefficients of $x$ i.e. $(a, c)^{\top}$ are replaced by $\boldsymbol{b}$ and, similarly, in $\Delta_{y}$, the coefficients of $y$ i.e. $(b, d)^{\top}$ are replaced by $\boldsymbol{b}$ where $\boldsymbol{b}=(e, f)^{\top}$. The unique solution to Eqs. (10.60) is given by Eqs. (10.62) provided $\Delta \neq 0$. If $\Delta=0$, this method of obtaining the solution cannot be used. Now let us go back to Cramer's rule and Eq. (10.59) to generalise. We realise that evaluating $(\operatorname{adj} A) \boldsymbol{b}$ can be expressed in a neat way by writing it out in component form,

The formula for the determinant of a matrix (summing over columns) is given by

where $i$ represents the index column, i.e. $i=1$ if we expand along the first column, $i=2$ if we expand along the second, etc. Equation 10.65 holds for an $n \times n$ square matrix.

Consider now the following $3 \times 3$ matrix,

Suppose now we were to expand Eqs. (10.64) and (10.65) for column 1 (i.e. $i=1$ ) for the matrix equation (10.66). This yields,

It follows, that Eq. (10.64) gives the determinant of the matrix when the $i^{\text {th }}$ column [i.e. for column 1 , we have $\left.\left(a_{11}, a_{21}, a_{31}\right)^{\top}\right]$