2.2 Matrix Multiplication - La Jolla Country Day School
Download
Report
Transcript 2.2 Matrix Multiplication - La Jolla Country Day School
2.3 Matrix Multiplication
Background Example
• We return to our Sweatshirt store example:
– We wish to find the value of the inventory by size
– Smalls - $10, Med - $11, Large - $12, XL - $13
...s.........m........l........ xl
100 200 300 400
200
100
100
300 100
250 100
40
20
200
200
100
• How would we set up the mult. to do this?
Matrix Multiplication Algorithm
• The mtx mult algorithm is defined to do just that:
...s.........m........l........ xl
100 200 300 40010 10(100) 11(200) 12(300)13(400)
200
100
100
300 100
250 100
40
20
20011 10(200)11(300) 12(100) 13(200)
200
12 10(100) 11(250)12(100) 13(250)
100
13 10(100) 11(40) 12(20) 13(100)
• (i,j): multiply entries in row i of first mtx by the
corresponding entries in col j of second mtx, and then add
terms.
- Note that this is the dot product of row i and col j
A few things to note
• Given the way that the algorithm is defined, what must
be true about the dimensions of the matrices in order for
multiplication to work?
– # of entries in each row of first matrix must equal # of
entries in each column of second matrix
– (i.e. number of columns of first matrix must equal the
number of rows of second matrix)
– So if multiplying matrices of following order: (a x b)
x (c x d), b = c
• Note: order of solution mtx is:
axd
Example
• Given matrices A and B, find the results of the
following if possible:
– A2
1 1
2
– B2
, B
A
– AB
2
3
3
– BA
Example#2
• Given the matrices A and B, find AB and BA:
1 1 0
1 0 0
A 2 3 1 , B 0 1 0
2 1 1
0 0 1
•
B is the identity matrix, I3, since AB = BA = A
• The identity is always a square matrix with 1’s on the
main diagonal and 0’s elsewhere.
•
I is only the identity for a matrix of the same size.
Properties of Mtx Multiplication
1
2
3
4
5
6
IA = A, BI = B
A(BC) = (AB)C
A(B+C) = AB + AC, A(B-C) = AB - AC
(B+C)A = BA + CA, (B - C)A = BA - CA
k(AB) = (kA)B = A(kB)
(AB)T = BTAT
- Note: commutativity does not hold (AB ≠ BA in
most cases).
- Therefore the order of the factors in a product of
matrices makes a difference!
Helpful Notation
• To help us prove the properties, it is useful to understand
the following notation for matrix multiplication.
• A = [aij] is m x n, B = [bij] is n x p
b1j
• ith row of A is [ ai1 ai2 …… ain]
b2 j
• jth column of B is: --------------------->
...
b
nj
• ij entry of prod mtx is dot prod of rown i of A and col j
of B: a b a b ... a b
a b
i1 1 j
i2 2 j
in nj
k 1
ik kj
Proving Property 3 (also in book)
• Property 3: A(B + C) = AB + AC
• A is m x n, B is n x p, C is n x p
• B + C = [bij + cij]
n
n
n
n
k 1
k 1
k 1
k 1
A(B C) aik (bkj ckj ) (aik bkj aik ckj ) aik bkj aik ckj
• This is just the (i,j) entry of AB + the (i,j) entry of AC
• Therefore A(B + C) = AB + AC
•
Matrix form of linear system
• Try to write the following system as a single matrix
equation: 2x 3x x 6
1
2
3
x1 2x2 x3 4
x1
2 3 1 6
x2 AX
1 2 1 4
x 3
B
• A is coefficient mtx, X is solution mtx, B is
constant mtx
Precursor to Theorem 2
• If X1 is a sol’n to AX=B and X0 is a sol’n to the related
homogeneous system AX = 0, then:
– X1 + X0 is a solution to AX = B:
A(X1 X0 ) AX1 AX 0 B 0 B
• Theorem 2 is a converse of this.
Theorem 2
• If X1 is a sol’n to AX=B, then every solution, X2, to
AX=B is of the form:
– X2 = X1 + X0 where X0 is a solution to the associated
homogeneous system AX=0.
Proof of Theorem 2
• If X2 and X1 are both sol’ns to AX=B,
– So AX1 = B and AX2 = B:
– say X0 = X2 - X1 so X2 = X0+X1
– AX0 = A(X2 - X1) = AX2 - AX1= B - B = 0
– Therefore, X0 is a solution to the associated
homogeous system AX = 0. •
Example
• Express every solution to the following system as the
sum of a specific solution plus a solution to the
associated homogeneous system.
x 2y 4z 10
2x y 2z 5
x y 2z 7
Solution
1 0 0 4
x 4 4 0
0 1 2 3 so...X y 2t 3 3 t 2
x t 0 1
0 0 0 0
• If we take t=0, we get a specific solution, X1
• Therefore, if t≠0, the solution, X2 = X1 + X0 where X0 is
a solution to the associated homogeneous stm: AX = 0
0
• So,
gives all sol’ns to assoc. hom. System
t 2 X
• (Show) 0
1
Example
1 2 1
1 1 2 0
A 0 1 2,...,B 1 3 2 1
1 1 2
0 2 0 1
• Find row 3 and column 2 of AB.
• In many situations, it is helpful to write a matrix as a
column of rows or as a row of columns:
R1
A R2 ,...B C1 C2 C3 C4
R3
Simplifying Notation
• So then we can use the following notation in mtx mult:
R1
R1 X
R2
R2 X
AX X
...
...
R
R X
m
m
A further simplification
• We can partition a matrix into smaller blocks:
1
0
A
1
0
0
0 I2 O23
2 3 1 1 X Y
2 3
2 1 2 3
0 0 0
1 0 0
4 1
W
B 0 1
2 1 Z
2 3
Continuing the Example
I2
AB
X
2 3
O23 W W 4 1
Y Z XW YZ 6 12
10 4
• We need to make sure that the way we partition the
matrices allows us to multiply matrices which match up
appropriately by dimension. (show)
Another Block Multiplication Ex.
• Go through ex. 11 with finding powers of mtx:
1 1 0
X
A 1 1 0
Y
1 1 2
• Find A8
O
Z
Example continued
X OX
2
A
Y Z Y
O X2
0 X 2
2
Z
YX
ZY
Z
0
• This was convenient since we have a 0 matrix
2
X
A 4 (A2 ) 2
0
0 X 2
2
Z
0
0 X 4
2
Z
0
0
4
Z
X 4
A8 (A 4 )2
0
0 X 4
4
Z
0
0 X 8
4
Z
0
0
8
Z
• This was convenient since we had a diagonal matrix
0
Z 2
Finally...
Z8 2 8 256
X 2 2X
so...X 4 (2X) 2 4X 2 4(2 X) 8X
so...X 8 (8X) 2 64X 2 64(2X) 128X
128X
A
0
8
1 1 0
X 0
0
128
1281 1 0
256
0 2
0 0 2
Other topics in homework
• Trace: sum of elements on main diagonal of square mtx
• Idempotent: square mtx,P, is idempotent if P2 = P