454 Appendix
• Subtract multiples of the pivot row from rows below it to
get zeroes below the diagonal.
The pivoting, though not absolutely necessary, avoids possible
numerical difficulties. Note that once a column is zeroed below
the diagonal, we do not have to think about it any more.
For an illustration of this method, called Gaussian elimination with partial pivoting, consider solving the system of
equations
x 1 + x 2 = 5,
4x 1 + x 2 + x 3 = 4,
2x 1 + 2x 2 + 2x 3 = 3.
(42)
This can be expressed in matrix form as
1 1 0
4 1 1
2 2 2
5
4
3
1
2
3
,
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
=
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
x
x
x
(43)
and solved by triangularizing the augmented matrix
1 1 0 5
4 1 1 4
2 2 2 3
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
.
(44)
To get zeroes below the diagonal in the first column, we first
move 4, the element with the largest absolute value in the first
column, to the diagonal by interchanging rows
4 1 1 4
1 1 0 5
2 2 2 3
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
.
(45)
We then subtract 1/4 times the first row from second, and 1/ 2
times the first row from third, leaving
4 1
1
4
0 0 75 0 25 4
0 1 5
1 5 1
.
.
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(46)
Next, to zero the elements below the diagonal in the second column, we interchange rows to get the pivot for this column, 1.5,
on the diagonal:
4 1
1
4
0 1 5
1 5 1
0 0 75 0 25 4
.
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(47)
and subtract 0.75/1.5 = 0.5 times the second row from the third
4 1
1
4
0 1 5 1 5 1
0 0
1
3 5
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(48)
to complete the triangularization. We then solve the equations
for x, beginning with the bottom one, as in Eqns 34–6.
A similar procedure can be used to invert a matrix. This
method uses the idea that two vector–matrix equations
Ax = b and Ay = c
(49)
can be combined into one by forming an augmented matrix
from each pair of vectors,
X = (x, y), B = (b, c),
(50)
and writing the matrix equation
AX = B.
(51)
Because x, the solution to Ax = b, is not changed by elementary
row operations on the augmented matrix (A, b), the corresponding solution to AX = B is unaffected by elementary row
operations on the augmented matrix (A, B).
To apply this to matrix inversion, consider a special case
AX = I,
(52)
whose solution X = A −1 is the inverse of the n × n matrix A. X
is unaffected by elementary row operations that convert the
augmented matrix
( , )
. .
. .
. . . .
. . . .
. . . .
. . . .
. .
. .
A I
a
a
a
a
n
n
n n
=
⎛
⎝
⎜
⎜
⎜ ⎜
⎞
⎠
⎟
⎟
⎟ ⎟
11
1
1
1
0
0
1
(53)
to one whose left side is the identity
( , )
. .
. .
. . . .
. . . .
. . . .
. . . .
. .
. .
,
I B
b
b
b
b
n
n
n n
=
⎛
⎝
⎜
⎜
⎜ ⎜
⎞
⎠
⎟
⎟
⎟ ⎟
1
0
0
1
11
1
1
(54)
so the corresponding equation
IX = B
(55)
shows that the right side of the matrix gives B = X = A −1 , the inverse of A. The sequence of operations used to diagonalize the
left (A) side of the augmented matrix (A, I) are similar to those
that triangularize a matrix.
A.5 Vector transformations
In seismology, we often apply two types of transformations
to vectors. In the first, the same vector is expressed in two
• Subtract multiples of the pivot row from rows below it to
get zeroes below the diagonal.
The pivoting, though not absolutely necessary, avoids possible
numerical difficulties. Note that once a column is zeroed below
the diagonal, we do not have to think about it any more.
For an illustration of this method, called Gaussian elimination with partial pivoting, consider solving the system of
equations
x 1 + x 2 = 5,
4x 1 + x 2 + x 3 = 4,
2x 1 + 2x 2 + 2x 3 = 3.
(42)
This can be expressed in matrix form as
1 1 0
4 1 1
2 2 2
5
4
3
1
2
3
,
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
=
⎛
⎝
⎜
⎜
⎜
⎞
⎠
⎟
⎟
⎟
x
x
x
(43)
and solved by triangularizing the augmented matrix
1 1 0 5
4 1 1 4
2 2 2 3
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
.
(44)
To get zeroes below the diagonal in the first column, we first
move 4, the element with the largest absolute value in the first
column, to the diagonal by interchanging rows
4 1 1 4
1 1 0 5
2 2 2 3
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
.
(45)
We then subtract 1/4 times the first row from second, and 1/ 2
times the first row from third, leaving
4 1
1
4
0 0 75 0 25 4
0 1 5
1 5 1
.
.
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(46)
Next, to zero the elements below the diagonal in the second column, we interchange rows to get the pivot for this column, 1.5,
on the diagonal:
4 1
1
4
0 1 5
1 5 1
0 0 75 0 25 4
.
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(47)
and subtract 0.75/1.5 = 0.5 times the second row from the third
4 1
1
4
0 1 5 1 5 1
0 0
1
3 5
.
.
.
−
⎛
⎝
⎜
⎜
⎞
⎠
⎟
⎟
(48)
to complete the triangularization. We then solve the equations
for x, beginning with the bottom one, as in Eqns 34–6.
A similar procedure can be used to invert a matrix. This
method uses the idea that two vector–matrix equations
Ax = b and Ay = c
(49)
can be combined into one by forming an augmented matrix
from each pair of vectors,
X = (x, y), B = (b, c),
(50)
and writing the matrix equation
AX = B.
(51)
Because x, the solution to Ax = b, is not changed by elementary
row operations on the augmented matrix (A, b), the corresponding solution to AX = B is unaffected by elementary row
operations on the augmented matrix (A, B).
To apply this to matrix inversion, consider a special case
AX = I,
(52)
whose solution X = A −1 is the inverse of the n × n matrix A. X
is unaffected by elementary row operations that convert the
augmented matrix
( , )
. .
. .
. . . .
. . . .
. . . .
. . . .
. .
. .
A I
a
a
a
a
n
n
n n
=
⎛
⎝
⎜
⎜
⎜ ⎜
⎞
⎠
⎟
⎟
⎟ ⎟
11
1
1
1
0
0
1
(53)
to one whose left side is the identity
( , )
. .
. .
. . . .
. . . .
. . . .
. . . .
. .
. .
,
I B
b
b
b
b
n
n
n n
=
⎛
⎝
⎜
⎜
⎜ ⎜
⎞
⎠
⎟
⎟
⎟ ⎟
1
0
0
1
11
1
1
(54)
so the corresponding equation
IX = B
(55)
shows that the right side of the matrix gives B = X = A −1 , the inverse of A. The sequence of operations used to diagonalize the
left (A) side of the augmented matrix (A, I) are similar to those
that triangularize a matrix.
A.5 Vector transformations
In seismology, we often apply two types of transformations
to vectors. In the first, the same vector is expressed in two