Matrix Multiplication

 If A, B are two matrices are in the order of p x q, q x r then the resultant matix C will be in
the order of p x r.
 To multiply two matrices A, B, it should satisfy the rule :
Number of Columns in Matrix A = Number of Rows in Matrix B
Example:

1 8 9 1 8
A = 7 6 -1 B = 7 6
5 5 6 5 5

1x1 + 8x7 + 9x5 1x8 + 8x6 + 9x5

C = AB 7x1 + 6x7 + (-1)x5 7x8 + 6x6 + (-1)x5
5x1 + 5x7 + 6x5 5x8 + 5x6 + 6x5

102 101
C = AB 44 87
70 100

 The order of Matrix A = 3 x 3 , The order of Matrix B = 3 x 2.

Therefore the order of Matrix C = 3 x 2.
 The Number of multiplications required to compute C = AB is equal to 3 x 3 x 2 .
 i.e., If A, B are two matrices are in the order of p x q, q x r then The Number of
multiplications required to compute C = AB is equal to p x q x r.
 If A, B, C are two matrices are in the order of p x q, q x r, r x s respectively then The
Number of multiplications required to compute ( AB)C and A(BC) are as follows:
Number of multiplications for (AB)C = mult[(AB)C] = p x q x r + p x r x s
Number of multiplications for A(BC) = mult[A(BC)] = q x r x s + p x q x s

Example :
Let p = 5, q = 4, r = 6 and s = 2 then
Number of multiplications for (AB)C = mult[(AB)C] = p x q x r + p x r x s
= 5x4x6 + 5x6x2
= 120 + 60
= 180
 Number of multiplications for (AB)C = mult[A(BC)] = q x r x s + p x q x s
= 4x6x2 + 5x4x2
= 48 + 40
= 88
 Matrix multiplication is Associative ( AB)C = A(BC)
 But the Sequence or parenthesization of multiplication will increase the number of
multiplications.
 From the above example it is increased from 88 to 180.
 The Chain of Matrix multiplication problem is to determine the sequence that
minimizes the number of scalar multiplications in computing A1. A2. A3. …. An
 i.e., Determine how to parenthesize the multiplications.
A1. A2. A3. A4 = (A1. A2) . (A3. A4 )
= A1.( A2 . (A3. A4 ))
= A1.(( A2 . A3 ). A4 ))
= ((A1. A2) . A3 ). A4 )
= (A1.( A2 . A3 )). A4 )
 Number of trees can be constructed to represent above multiplications are
T(n) = 2n C n / (n +1)
Number multiplications between A1 to A4 are n = 3
 T(3) = 6 C 3 / (4) = 6 ! / 3! . 3! . 4 = 6 * 5 * 4 * 3 * 2* 1 / 6 * 6 * 4 = 5

Example : Given chain of 4 matrices A1, A2, A3, A4 with the following orders.
The order of Matrix A1 = 5 x 4 = p0 x p1 => p0 = 5, p1 = 4
The order of Matrix A2 = 4 x 6 = p1 x p2 => p1 = 4, p2 = 6
The order of Matrix A3 = 6 x 2 = p2 x p3 => p2 = 6, p3 = 2
The order of Matrix A4 = 2 x 7 = p3 x p4 => p3 = 2, p4 = 7
m [1,1] = 0 A1 Selected Matrix A1 No multiplications involved. m [I, j]
1 2 3 4
m [2,2] = 0 A2 Selected Matrix A2 . No multiplications involved.
1 0
m [3,3] = 0 A3 Selected Matrix A3 . No multiplications involved. 2 0
3 0
m [4,4] = 0 A4 Selected Matrix A4. No multiplications involved. 4 0

The order of Matrix A1 S [I, j]

= 5x4 1 2 3 4 m [I, j]
The order of Matrix A2
1 1 1 2 3 4
m [1,2]
= 120 A1 x A 2 = 4x6 1 0 120
Number of 2
3 2 0
multiplications
= 5 x 4 x 6 =120 4 3 0
4 0

Order of Matrix A2 =
4x6 m [I, j]
Order of Matrix A3 = 1 2 3 4
m [2,3]
= 48 A2 x A 3 6x2 m [2,3] = 48 1 0 120
Number of
2 0 48
multiplications
= 4 x 6 x 2 =48 3 0
4 0

Order of Matrix A3 =
6x2 m [I, j]
Order of Matrix A3 = 1 2 3 4
m [3,4]
= 84 A3 x A 4 2x7 m [3,4] = 84 1 0 120
Number of
2 0 48
multiplications
= 6 x 2 x 7 =84 3 0 84
4 0
m [1,3] =
A1 .(A2 . A3 ) m [1,1] +m [2,3]+ p0p1p3
= 0 + 48 + 5x4x2 = 88 S [I, j] m [I, j]
m [1,3] = 1 2 3 4 1 2 3 4
min
{88,180} m [1,3] =
1 1 1 1 0 120 88
= 88 (A1 .A2 ). A3 2 2 2 0 48
m [1,2]+m [3,3] + p0p2p3
= 120+0+ 5x6x2 = 180 3 3 3 0 84
4 4 0
m [2,4] =
A2 .(A3 . A4 ) m [2,2] +m [3,4]+ p1p2p4
m [2,4] = = 0+84 + 4x6x7 S [I, j] m [I, j]
min = 252 1 2 3 4 1 2 3 4
{252,104} 1 1 1 1 0 120 88
= 104 m [2,4] =
(A2 .A3 ). A4 m [2,3]+m [4,4] + p0p2p3 2 2 3 2 0 48 104
= 48+0+ 4x2x7 3 3 3 0 84
= 104
4 4 0
m [1,4] =
A1(A2(A3.A4 )) m [1,1] +m [2,4]+ p0p1p4
= 0+104 + 5x4x7 m [I, j]
m [1,4] = = 244 1 2 3 4
min m [1,4] = 1 0 120 88 158
{244,414, (A1.A2)(A3.A4) m [1,2] +m [3,4]+ p0p2p4 S [I, j]
158} 1 2 3 4 2 0 48 104
= 120+ 84 + 5x6x7
= 158 = 414 1 1 1 3
3 0 84
m [1,4] = 2 2 3
4 0
(A1.A2.A3).A4 m [1,3] +m [4,4]+ p0p3p4
= 88+ 0 + 5x2x7 3 3
= 158 4
 m [i,j] = min { m [i,k] + m [k+1,j] + pi-1pkpj }

S [I, j]
1 2 3 4
(A1.A2.A3). A4
1 1 1 3
A1. (A2.A3). A4
2 2 3 A1. (A2.A3). A4
3 3
4

The Minimum numbers of multiplications are possible with the sequence of A1. (A2.A3). A4

A1 A2 A3 A4

Time Complexity:

m [I, j]
1 2 3 4
1 0 120 88 158 1
2 0 48 104 2
3 0 84
3
4 0
.
1 + 2+ 3 + ….. (n-1) = n(n-1)/2 . n = n3 = Ɵ (n3 )
Table can be simplified as follows: