A8 Linear algebra problems 591
The method used for this problem is straightforward. We use the fact that the rows
ofAcan be interchanged if the corresponding elements ofbare also interchanged,
and it is also allowed to replace a row ofAby a linear combination of that row
and another, provided similar transformations are performed to the elements ofb.
These properties can now be used to transformAinto an upper triangular matrix.
This is done proceeding step by step from the left column ofAto the right one,
making the elements below the diagonal for each column equal to zero. Suppose
we have zeroed the lower parts of columns 1 through tom−1. The equation now
looks as follows:
a′ 11 a′ 12 ··· a′1,m− 1 a′ 1 m ··· a′ 1 N
0 a′ 22 ··· a′2,m− 1 a′ 2 m ··· a′ 2 N
..
.... ... ..
.
..
.
..
.
0
...
a′m−1,m− 1 a′m−1,m ··· a′mN
0 ··· ··· 0 a′mm ··· a′mN
0 ··· ··· 0 a′m+1,m ··· a′m+1,N
..
...
.
..
.
..
.
0 ··· ··· 0 a′Nm ··· a′NN
x 1
x 2
..
.
..
.
.
..
.
..
.
xN
=
b′ 1
b′ 2
..
.
..
.
..
.
..
.
..
.
b′N
(A.111)
Now we must treat column numberm. To do this, we take rowsi=m+1toNof
A′,a′mi/a′mmtimes themth row ofA′and subtract, which causes all elementsa′im,
that is, the elements of themth column below the diagonal, to vanish.
Obviously, there is a problem whena′m,mis equal to zero. In that case we have to
search from this diagonal element downward until we find an elementa′i,m,i>m,
which is nonzero. We then interchange rowsmandiand we proceed in the same
way as described above. The calculation takes a number ofm^2 steps for column
m. Summing overm, we obtain a total number ofO(N^3 )steps. Unfortunately, for
a generic matrix which does not contain many zeroes, theN^3 scaling cannot be
altered by using other methods.
Finally, we are left with an upper triangular matrixA′′(and a right hand sideb′′)
with elementsa′′ij(bi′′):
a′′ 11 a′′ 12 ··· a′′1,N− 1 a′′ 1 N
0 a′′ 22 ··· a′′2,N− 1 a′′ 2 N
..
...
.
... ..
.
..
.
00 ··· a′′N−1,N− 1 a′′N−1,N
00 ··· 0 a′′NN
x 1
x 2
..
.
..
.
xN
=
b′′ 1
b′′ 2
..
.
..
.
b′′N