112 NUMERIC ALGORITHMS
4.2 Matrix Multiplication
A matrix is a mathematical structure of numbers arranged in rows and columns
that is equivalent to a two-dimensional array. Two matrices can be added or
subtracted element by element if they are the same size. Two matrices can be
multiplied if the number of columns in the first is equal to the number of rows
in the second. The resulting matrix will have the same number of rows as the
first matrix and the same number of columns as the second. If we multiply a 3
4 matrix by a 4 7 matrix, we will get a 3 7 matrix as our answer.
Matrix multiplication is not commutative, so if two matrices, called A and B,
are square, we could calculate the products AB or BA, but those two resulting
matrices may not be equal. (Notice that because multiplication of numbers is
commutative, if A and B are numbers, AB will always equal BA.)
Two matrices are multiplied by taking each row of the first and multiplying
it, element by element, with each column of the second. The sum of each of
these products is taken and that becomes the value in the corresponding loca-
tion of the result. Figure 4.3 shows the result of multiplying two matrices.
If you look at Fig. 4.3, you will count 24 multiplications and 16 additions.
In general, the standard matrix multiplication algorithm will do a*b*c mul-
tiplications and a* (b 1) *c additions for two matrices of sizes ab and b
c. This general algorithm for multiplying matrix G (size ab) and matrix H
(sizebc) to get resulting matrix R (size ac) is given by
for i = 1 to a do
for j = 1 to c do
Ri,j = 0
for k = 1 to b
Ri,j = Ri,j + Gi,k* Hk,j
end for k
end for j
end for i
It would seem that this is the minimum work that is required to successfully
multiply two matrices. But researchers could not prove that this amount of■FIGURE 4.3
Multiplication of a
2 3 matrix and a
3 4 matrixabc
defABCD
EFGH
IJKLaA bE cI++aB bF cJ++aC bG cK++aD bH cL++
dA eE fI++dB eF fJ++dC eG fK++ dD eH fL++=