Artificial Intelligence 🤖
Matrices
Gauss-Jordan method

Gauss-Jordan method

Calculating Inverses

When we have a nonhomogeneous system of equations Ax=bA \boldsymbol{x}=\boldsymbol{b}, where AA is non-singular, we wish to calculate A1bA^{-1} \boldsymbol{b}. One way to find A1A^{-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

x+2y+3z=4,x+3y+5z=2,x+5y+12z=6.\begin{aligned} x+2 y+3 z & =4, \\ x+3 y+5 z & =2, \\ x+5 y+12 z & =6 . \end{aligned}

We express these in matrix form as follows,

(1231351512)(xyz)=(100010001)(427)\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 5 \\ 1 & 5 & 12 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)\left(\begin{array}{l} 4 \\ 2 \\ 7 \end{array}\right)

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

(123012039)(xyz)=(100110101)(427)\left(\begin{array}{lll} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 3 & 9 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{array}\right)\left(\begin{array}{l} 4 \\ 2 \\ 7 \end{array}\right)

The idea is as follows; the solution to Ax=bA \boldsymbol{x}=\boldsymbol{b} is given by x=A1b\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 AA ) becomes the identity matrix multiplying x\boldsymbol{x} then the matrix on the RHS must turn into the inverse of AA. Performing (R12R2)(R1)\left(R_{1}-2 R_{2}\right) \rightarrow\left(R_{1}\right) followed by (R33R2)(R3)\left(R_{3}-3 R_{2}\right) \rightarrow\left(R_{3}\right) gives,

(101012003)(xyz)=(320110231)(427)\left(\begin{array}{ccc} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 3 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{ccc} 3 & -2 & 0 \\ -1 & 1 & 0 \\ 2 & -3 & 1 \end{array}\right)\left(\begin{array}{l} 4 \\ 2 \\ 7 \end{array}\right)

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

(100010001)(xyz)=(11/331/37/332/32/311/3)(427).\left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{ccc} 11 / 3 & -3 & 1 / 3 \\ -7 / 3 & 3 & -2 / 3 \\ 2 / 3 & -1 & 1 / 3 \end{array}\right)\left(\begin{array}{l} 4 \\ 2 \\ 7 \end{array}\right) .

The matrix on the RHS is therefore A1A^{-1}. To solve for x\boldsymbol{x}, we need to calculate A1bA^{-1} \boldsymbol{b} which gives x=11,y=8x=11, y=-8, and z=3z=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 xx 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 AA given by

A=(121251382)A=\left(\begin{array}{ccc} 1 & 2 & -1 \\ 2 & 5 & 1 \\ 3 & 8 & -2 \end{array}\right)

using the Gauss-Jordan method.

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

(121100251010382001)\left(\begin{array}{ccc|ccc} 1 & 2 & -1 & 1 & 0 & 0 \\ 2 & 5 & 1 & 0 & 1 & 0 \\ 3 & 8 & -2 & 0 & 0 & 1 \end{array}\right)

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

(121100013210021301)\left(\begin{array}{ccc|ccc} 1 & 2 & -1 & 1 & 0 & 0 \\ 0 & 1 & 3 & -2 & 1 & 0 \\ 0 & 2 & 1 & -3 & 0 & 1 \end{array}\right)

We continue with (R12R2)(R1)\left(R_{1}-2 R_{2}\right) \rightarrow\left(R_{1}\right) and (R32R2)(R3)\left(R_{3}-2 R_{2}\right) \rightarrow\left(R_{3}\right),

(107520013210005121)\left(\begin{array}{ccc|ccc} 1 & 0 & -7 & 5 & -2 & 0 \\ 0 & 1 & 3 & -2 & 1 & 0 \\ 0 & 0 & -5 & 1 & -2 & 1 \end{array}\right)

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

(1075200107/51/53/5005121)\left(\begin{array}{ccc|ccc} 1 & 0 & -7 & 5 & -2 & 0 \\ 0 & 1 & 0 & -7 / 5 & -1 / 5 & 3 / 5 \\ 0 & 0 & -5 & 1 & -2 & 1 \end{array}\right)

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

(1001854575010751535001152515).\left(\begin{array}{cccccc} 1 & 0 & 0 & \frac{18}{5} & \frac{4}{5} & \frac{-7}{5} \\ 0 & 1 & 0 & \frac{-7}{5} & \frac{-1}{5} & \frac{3}{5} \\ 0 & 0 & 1 & \frac{-1}{5} & \frac{2}{5} & \frac{-1}{5} \end{array}\right) .

The matrix that appears on the RHS is A1A^{-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,

(1231351512)(xyz)=(427).\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 5 \\ 1 & 5 & 12 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{l} 4 \\ 2 \\ 7 \end{array}\right) .

We undertake (R2R1)(R2)\left(R_{2}-R_{1}\right) \rightarrow\left(R_{2}\right) and (R3R1)(R3)\left(R_{3}-R_{1}\right) \rightarrow\left(R_{3}\right) as before so that we obtain zeros in the a21a_{21} and a31a_{31} positions, as follows

(123012039)(xyz)=(423).\left(\begin{array}{lll} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 3 & 9 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{c} 4 \\ -2 \\ 3 \end{array}\right) .

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

(123012003)(xyz)=(429).\left(\begin{array}{lll} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 3 \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{c} 4 \\ -2 \\ 9 \end{array}\right) .

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

y+2z=2y=8y+2 z=-2 \Rightarrow y=-8

and from the first row,

x+2y+3z=4x=11.x+2 y+3 z=4 \Rightarrow x=11 .

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 (R3R1R2)(R3)\left(R_{3}-R_{1}-R_{2}\right) \rightarrow\left(R_{3}\right),

(341c11210004c)\left(\begin{array}{ccc|c} 3 & 4 & 1 & c \\ -1 & 1 & 2 & 1 \\ 0 & 0 & 0 & 4-c \end{array}\right)

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

(341c0773+c0004c).\left(\begin{array}{ccc|c} 3 & 4 & 1 & c \\ 0 & 7 & 7 & 3+c \\ 0 & 0 & 0 & 4-c \end{array}\right) .

We see from the last row that for consistency, we need c=4c=4. We again let z=λz=\lambda the parameter for the under-determined equation and we have 7y=77λ7 y=7-7 \lambda, so that y=1λy=1-\lambda in the second equation and in the first equation, we have 3x=3λ3 x=3 \lambda so that x=λ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,
2x+ay2z=1xyz=b3x+2y+z=1\begin{array}{r} 2 x+a y-2 z=1 \\ -x-y-z=b \\ 3 x+2 y+z=1 \end{array}

giving different cases for aa and bb.

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 Ax=bA \boldsymbol{x}=\boldsymbol{b} is given by

x=A1b\boldsymbol{x}=A^{-1} \boldsymbol{b}

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

x=A1b=1detA(adjA)b.\boldsymbol{x}=A^{-1} \boldsymbol{b}=\frac{1}{\operatorname{det} A}(\operatorname{adj} A) \boldsymbol{b} .

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×22 \times 2 matrix equation,

(abcd)(xy)=(ef)\left(\begin{array}{ll} a & b \\ c & d \end{array}\right)\left(\begin{array}{l} x \\ y \end{array}\right)=\left(\begin{array}{l} e \\ f \end{array}\right)

Solving for xx and yy from the system of equations, i.e.

ax+by=e and cx+dy=f,a x+b y=e \text { and } c x+d y=f,

we obtain

x=edbfadbc,y=afecadbc.x=\frac{e d-b f}{a d-b c}, \quad y=\frac{a f-e c}{a d-b c} .

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

x=ΔxΔ,y=ΔyΔx=\frac{\Delta_{x}}{\Delta}, \quad y=\frac{\Delta_{y}}{\Delta}

where,

Δ=abcd,Δx=ebfd,Δy=aecf.\Delta=\left|\begin{array}{ll} a & b \\ c & d \end{array}\right|, \quad \Delta_{x}=\left|\begin{array}{ll} e & b \\ f & d \end{array}\right|, \quad \Delta_{y}=\left|\begin{array}{ll} a & e \\ c & f \end{array}\right| .

Note that in the expression for Δx\Delta_{x}, the coefficients of xx i.e. (a,c)(a, c)^{\top} are replaced by b\boldsymbol{b} and, similarly, in Δy\Delta_{y}, the coefficients of yy i.e. (b,d)(b, d)^{\top} are replaced by b\boldsymbol{b} where b=(e,f)\boldsymbol{b}=(e, f)^{\top}. The unique solution to Eqs. (10.60) is given by Eqs. (10.62) provided Δ0\Delta \neq 0. If Δ=0\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 (adjA)b(\operatorname{adj} A) \boldsymbol{b} can be expressed in a neat way by writing it out in component form,

(adjAb)i=k=1nAkibk(\operatorname{adj} A \boldsymbol{b})_{i}=\sum_{k=1}^{n} A_{k i} b_{k}

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

detA=k=1nakiAki\operatorname{det} A=\sum_{k=1}^{n} a_{k i} A_{k i}

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

Consider now the following 3×33 \times 3 matrix,

(a11a12a13a21a22a23a31a32a33)(xyz)=(b1b2b3).\left(\begin{array}{lll} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array}\right)\left(\begin{array}{l} x \\ y \\ z \end{array}\right)=\left(\begin{array}{l} b_{1} \\ b_{2} \\ b_{3} \end{array}\right) .

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

(adjAb)1=A11b1+A21b2+A31b3;detA=a11A11+a21A21+a31A31.(\operatorname{adj} A \boldsymbol{b})_{1}=A_{11} b_{1}+A_{21} b_{2}+A_{31} b_{3} ; \quad \operatorname{det} A=a_{11} A_{11}+a_{21} A_{21}+a_{31} A_{31} .

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