Introduction to the Mathematical and Statistical Foundations of Econometrics

The Gauss-Jordan Iteration for Inverting a Matrix

The Gaussian elimination of the matrix A in the first example in the previous section suggests that this method can also be used to compute the inverse of A as follows. Augment the matrix A in (I.22) to a 3 x 6 matrix by augmenting the columns of A with the columns of the unit matrix Ib :

Now follow the same procedure as in Example 1, up to (I.25), with A replaced

A pivot is an element on the diagonal to be used to wipe out the elements below that diagonal element.

by B. Then (I.25) becomes

for instance, where U* in (I.30) follows from (I.25) and

Now multiply (I.30) by elementary matrix E13(-1), that is, subtract row 3 from row 1:

( Еі, з(-1) Р2,з Ез, і(1/2) E2,i(-1/2) A, Еі, з(-1) Pi, з Ез, і(1/2) E2,i(-1/2))

multiply (I.32) by elementary matrix E12(-4/3), that is, subtract 4/3 times row 3 from row 1:

( Ei,2(-4/3) Еі, з(-1) Р2,з Ез, і(1/2) E2,i(-1/2) A, Ei,2(-4/3) Еі, з(-1) Р2,з Ез, і(1/2) Е2,і(-1/2))

and finally, divide row 1 by pivot 2, row 2 by pivot 3, and row 3 by pivot 2, or equivalently, multiply (I.33) by a diagonal matrix D* with diagonal elements 1/2, 1/3 and 1/2:

(D* Ei,2(-4/3) Еі, з(-1) Р2,з Ез, і(1/2) E2,i(-1/2) A,

D* Ei,2(-4/3) Еі, з(-1) Р2,з Ез, і(1/2) E2,i(-1/2))

= (із, D, Ei,2(-4/3)Еі, з(-1)Pi, зЕз, і(1/2)Е2,і(-1/2))

Observe from (I.34) that the matrix (A, I3) has been transformed into a matrix of the type (I3, A*) = (A*A, A*), where A* = D, E1j2(-4/3) x

E13(—1)P23E31(1/2)E2j1(—1/2) is the matrix consisting of the last three columns of (I.34). Consequently, A* = A—1.

This way of computing the inverse of a matrix is called the Gauss-Jordan iteration. In practice, the Gauss-Jordan iteration is done in a slightly different but equivalent way using a sequence of tableaux. Take again the matrix A in (I.22). The Gauss-Jordan iteration then starts from the initial tableau:

If there is a zero in a pivot position, you have to swap rows, as we will see later in this section. In the case of Tableau 1 there is not yet a problem because the first element of row 1 is nonzero.

The first step is to make all the nonzero elements in the first column equal to one by dividing all the rows by their first element provided that they are nonzero. Then we obtain

Tableau 2

12 1 1/200 1 2 3 0 1 0 .

1 —11 0 0 —1

Next, wipe out the first elements of rows 2 and 3 by subtracting row 1 from them:

Tableau 3

12 1 1/200

0 0 2 —1/2 1 0 .

0 —3 0 —1/2 0 —1

Now we have a zero in a pivot position, namely, the second zero of row 2. Therefore, swap rows 2 and 3:

Tableau 4

12 1 1/200

0 —3 0 —1/2 0 —1 .

0 0 2 —1/2 1 0

Divide row 2 by —3 and row 3 by 2:

The left 3 x 3 block is now upper triangular.

Next, we have to wipe out, one by one, the elements in this block above the diagonal. Thus, subtract row 3 from row 1:

Tableau 6

120 3/4 -1/2 0

0 10 1/6 0 1/3 .

0 0 1 -1/4 1/2 0

Finally, subtract two times row 2 from row 1:

This is the final tableau. The last three columns now form A-1.

Once you have calculated A-1, you can solve the linear system Ax = b by computing x = A-1 b. However, youcanalsoincorporatethelatterintheGauss - Jordan iteration, as follows. Again let A be the matrix in (I.22), and let, for example,

1

Insert this vector in Tableau 1:

and perform the same row operations as before. Then Tableau 7 becomes

This is how matrices were inverted and systems of linear equations were solved fifty and more years ago using only mechanical calculators. Nowadays of course you would use a computer, but the Gauss-Jordan method is still handy and not too time consuming for small matrices like the one in this example.