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]$ has been replaced by the vector $\boldsymbol{b}$. Note that the components of the first column give the coefficients of $x$ when the equations are expanded

similarly, $\left(a_{12}, a_{22}, a_{32}\right)^{\top},\left(a_{13}, a_{23}, a_{33}\right)^{\top}$ are the coefficients of $y$ and $z$, respectively. With the above observations, we may use Cramer's rule (10.59) to find the value of $x, y$, and $z$ separately via the following relations,

Example 10.9 Use Cramer's rule in order to determine what the value of $x$ is in the solution of,

Solution Starting from Cramer's rule we have

where $A$ is the coefficient matrix in the matrix equation $(10.68)$ and $\boldsymbol{b}=(8,-2,-2)^{\top}$. To determine $x$, we use

where $\Delta_{x}$ is the determinant of matrix $A$ with the first column replaced by $\boldsymbol{b}$ and $\Delta$ is the determinant of $A$,

Using row transformations or by direct calculation, we find that $\Delta_{x}=\Delta=-16$ hence $x=1$.

While Cramer's rule is useful in obtaining a single value of the unknown vector without knowing any of the other vector values, it can get computationally expensive with larger matrices. Further, if $\Delta=0$, we know that the system of equations we are trying to solve admits either no solutions or infinitely many solutions; however, a different technique must be used to obtain the solutions.

In this section we have discussed the Gauss-Jordan method, Gaussian elimination, and Cramer's rule for solving linear systems. The Gauss-Jordan method is used when we want to fully invert a matrix. To solve a system of equations, we may use Gaussian elimination to obtain an upper triangular matrix by undertaking row operations; then the last row gives us the $n^{\text {th }}$ component of an $n \times 1$ matrix $\boldsymbol{x}$ and through back substitution we can solve for the remaining $n-1$ components. Finally, if we wish to obtain a single component of an unknown vector $\boldsymbol{x}$ (like the $x$-component in Example 10.9), we may use Cramer's rule.

Exercises

1. Find the inverse matrix of

2. Find the solution of the following system of equations using Gaussian elimination,

3. Find the value of $x$ using Cramer's rule in the following system of equations,