s
Section 5.7 Matrices
453
The computational steps done in this algorithm are multiplications and additions, one multiplication and one addition each time the statement C3i, j 4 5
C3i, j 4 + a3i, k 4 * b3k, j 4 is executed. This statement occurs within a triply nested
loop and will be executed npm times. (Although this is quite obvious, it can also
be justified by the multiplication principle as the number of possible outcomes of
choosing indices i, j, and k.) If a and b are both n × n matrices, then there are
Θ(n
3
) multiplications and Θ(n
3
) additions required. The total amount of work is
therefore Θ(n
3
) + Θ(n
3
) = Θ(n
3
).
Given the definition of matrix multiplication, it is hard to see how one could
avoid Θ(n
3
) steps in computing the product of two n × n matrices, but a sufficiently clever approach does yield an improvement under certain conditions (see
Exercise 54).
gaussian elimination
In Example 63 we encountered the following system of two linear equations in
two unknowns:
x + y = 70
24x + 14y = 1180
The general form for a system of n linear equations in n unknowns is
a 11 x 1 + a 12 x 2 + c + a 1n x n = b 1
a 21 x 1 + a 22 x 2 + c + a 2n x n = b 2
(
a n1 x 1 + a n2 x 2 + c + a nn x n = b n
with a matrix of coefficients
≥
a 11 a 12 … a 1n
a 21 a 22 … a 2n
(
a n1 a n2 … a nn
¥
To solve this system of equations, we first form the augmented n × (n + 1)
matrix by adding the column of b’s to the matrix of coefficients:
≥
a 11 a 12 … a 1n b 1
a 21 a 22 … a 2n b 2
(
a n1 a n2 … a nn b n
¥
(The augmented matrix is simply a convenience to avoid having to write all the
unknowns.) The next step is to “transform” the augmented matrix into one where
the matrix-of-coefficients part is an upper triangular matrix, that is, all values
of this n × n matrix below the main diagonal are 0’s. The result will be a matrix
of the form
Section 5.7 Matrices
453
The computational steps done in this algorithm are multiplications and additions, one multiplication and one addition each time the statement C3i, j 4 5
C3i, j 4 + a3i, k 4 * b3k, j 4 is executed. This statement occurs within a triply nested
loop and will be executed npm times. (Although this is quite obvious, it can also
be justified by the multiplication principle as the number of possible outcomes of
choosing indices i, j, and k.) If a and b are both n × n matrices, then there are
Θ(n
3
) multiplications and Θ(n
3
) additions required. The total amount of work is
therefore Θ(n
3
) + Θ(n
3
) = Θ(n
3
).
Given the definition of matrix multiplication, it is hard to see how one could
avoid Θ(n
3
) steps in computing the product of two n × n matrices, but a sufficiently clever approach does yield an improvement under certain conditions (see
Exercise 54).
gaussian elimination
In Example 63 we encountered the following system of two linear equations in
two unknowns:
x + y = 70
24x + 14y = 1180
The general form for a system of n linear equations in n unknowns is
a 11 x 1 + a 12 x 2 + c + a 1n x n = b 1
a 21 x 1 + a 22 x 2 + c + a 2n x n = b 2
(
a n1 x 1 + a n2 x 2 + c + a nn x n = b n
with a matrix of coefficients
≥
a 11 a 12 … a 1n
a 21 a 22 … a 2n
(
a n1 a n2 … a nn
¥
To solve this system of equations, we first form the augmented n × (n + 1)
matrix by adding the column of b’s to the matrix of coefficients:
≥
a 11 a 12 … a 1n b 1
a 21 a 22 … a 2n b 2
(
a n1 a n2 … a nn b n
¥
(The augmented matrix is simply a convenience to avoid having to write all the
unknowns.) The next step is to “transform” the augmented matrix into one where
the matrix-of-coefficients part is an upper triangular matrix, that is, all values
of this n × n matrix below the main diagonal are 0’s. The result will be a matrix
of the form