Understanding Matrix Multiplication and Linear Combinations
Dive into the world of matrix multiplication, inner product calculations, and linear combinations through detailed explanations and visual aids. Learn how to perform matrix operations, derive results, and interpret the outcomes efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Matrix Multiplication Hung-yi Lee
Reference Textbook: Chapter 2.1
Inner Product (What you have learned in high school)
Matrix Multiplication Given two matrices A and B, the (i, j)-entry of AB is the inner product of row i of A and column j of B B A ??? ? = ??
Matrix Multiplication Given two matrices A and B, the (i, j)-entry of AB is the inner product of row i of A and column j of B 1 3 5 2 4 6 ? = 1 1 2 ? = 3 1 1 + 3 2 1 1 + 2 2 ? = ?? = 1 3 + 3 4 1 3 + 2 4 1 5 + 3 6 1 5 + 2 6
Matrix Multiplication Given two matrices A and B, the (i, j)-entry of AB is the inner product of row i of A and column j of B B (i,j)-entry A AB
Matrix Multiplication 4 ways Given two matrices A and B, the (i, j)-entry of AB is the inner product of row i of A and column j of B 1 3 1 2 B 5 1 3 5 2 4 6 AB A 17
Linear Combination of Columns and Rows
Matrix Multiplication Linear combination of columns ?? ?? = ? ?1 ?2 ??? = ??1 ??2 ?1 ?2 ?? ?1 ?2 ?? + + + + = ?21 ?11 ?22 ?12 ?2? ?1? ?1 ?1 ?? ?? ?2 ?2 The first column The second column
Matrix Multiplication 4 ways Linear combination of columns 1 3 5 2 4 6 ?? ?? = ? ?1 ?2 1 3 1 2 ??? = ??1 ??2 1 3 5 2 4 6 1 3 5 2 4 6 1 + 3 1 + 2 = The second column The first column
Matrix Multiplication - Meaning Multiple Input ? = ?? b2 = c1 A A b1 b1 bp = c2 A b2 c2 cp = c1 ?? ?? = ? ?1 ?2 = cp A bp ??? = ??1 ??2
Matrix Multiplication - Meaning Composition Given two functions ? and g, the function ? ? . composition g f. is the ? = ? ? ? = ? ? ? g f g f ? = ? ? ? ? Matrix multiplication is the composition of two linear functions.
Matrix Multiplication - Meaning Composition ? ? ? ? ? ? A ? B ? = ?? ? = ?? ? C ? ? ?
Matrix Multiplication - Meaning 1 0 0 The first column of B ? ? ? ? ?1= ?1 A ??1 B ? = ?? ? = ?? 1 0 0 Input standard matrix The first column of C C ?1 ?1= ? ?
Matrix Multiplication - Meaning 0 1 0 The second column of B ? ? ? ? ?2= ?2 A ??2 B ? = ?? ? = ?? 0 1 0 Input standard matrix The second column of C C ?2 ?2= ? ?
? ? A ? B ? = ?? ? = ?? ? ? = ?? C ? The composition of A and B is ???= ?? ? = ??1 ??2 Matrix Multiplication
Example 1 0 0 = 1 0 1 1 0 0 1 0 1 reflection about the x-axis rotation by 180 R2 R2 R2 1 0 0 1 0 0 ? ? ? 1 1 ? = ?? ? = ?? 1 0 0 1 ? ? reflection about the y-axis
Matrix Multiplication Linear combination of rows ?+ ?12?2 ? + ?1??? ? ?11?1 ? ? ?1 ?2 ?+ ?22?2 ? + ?2??? ?1 ?2 ? ?21?1 ? ? = ? ?? ? ?? ?+ ??2?2 ? + ????? ? ??1?1
Matrix Multiplication 4 ways Way 3: Linear combination of rows 1 1 1 + 2 3 2 The first row 1 3 5 2 4 6 1 3 1 2 3 1 1 + 4 3 2 = The second row 5 1 1 + 6 3 2 The third row
Matrix Multiplication Summation of matrices ? ?1 ?2 ?3 ? ? ?1 ?2 ?3 ?? ? ?? ?+ ?2?2 ?+ + ???? ? = ?1?1 matrices
Matrix Multiplication Summation of matrices 1 3 5 1 x 2 2 4 6 1 3 5 2 4 6 1 3 2 x 1 1 2 + = 3 2 1 1 1 x 1 1 3 5 Rank = ? 1 3 5 6 4 8 + 12 18 Rank = ? = 12 Block Multiplication (Section 2.5)
Augmentation and Partition Augment: the augment of A and B is [A B] Partition: 3 7 2 4 8 1 1 5 4 2 6 3 3 7 2 4 8 1 1 5 4 2 6 3 ? = ? = 3 7 2 4 8 1 1 5 4 2 6 3 3 7 2 4 8 1 1 5 4 2 6 3 ? = ? =
Block Multiplication 3 0 2 1 1 1 2 0 0 2 1 0 1 3 5 0 4 2 ? = ? = 1 3 6 1 3 1 ?11 ?21 ?12 ?22 ?11 ?21 ?12 ?22 ? = ? = ?11 ?21 ?12 ?22 ?11 ?21 ?12 ?22 Multiply as the small matrices are scalar ?? = ?11?11+ ?12?21 ?21?11+ ?22?21 ?11?12+ ?12?22 ?21?12+ ?22?22 = Don t switch the order
Block Multiplication 3 0 2 1 1 1 2 0 0 2 1 0 1 3 5 0 4 2 ? = ? = 1 3 6 1 3 1 2 x 2 2 x 2 + + 2 X 2 2 X 1 ?? = 2 x 2 + + 1 X 2 1 X 1
Block Multiplication 1 0 6 0 1 0 0 5 0 0 0 0 5 ?2 ? ? 5?2 6 8 9 ? = ? = ? = 8 9 7 7 ?2 ? ? 5?2 ?2 ? ? 5?2 ?2 6? ? = = ?2 25?2 ?2 ? ? 5?2 ?2 6? ? ?2 ? ?3= ??2 = = 25?2 31? 125?2
Not Communicative ?? ??
Not Communicative ? ? n ? ? ? A ? B B ? ? A ? n ? ? ? If A and B are matrices, then both AB and BA are defined if and only if A and B are square matrices?
Properties Let A and B be k x m matrices, C be an m x n matrix, and P and Q be n x p matrices For any scalar s, s(AC) = (sA)C = A(sC) (A + B)C = AC + BC C(P+Q)=CP+CQ IkA = A = AIm The product of any matrix and a zero matrix is a zero matrix Power of square matrices: A Mn n, Ak= A A A (k times), and by convention, A1= A, A0= In.
Properties ???: n X k ??: k X n Let A be kxm matrices, C be an mxn matrix, ???=? ???? ???? ???? m X k n X m n X m m X k n X k
Special Matrix Diagonal Matrix Symmetric Matrix ??= ? AATand ATA are square and symmetric ????= ?????= ??? ??? ?= ?????= ???
Practical Issue Let A and B be k x m matrices, C be an m x n matrix, and P and Q be n x p matrices A(CP) = (AC)P p n n m m X n X p Multiplication count:
m=1000 k=1 Practical Issue n=1 p=1000 Let A and B be k x m matrices, C be an m x n matrix, and P and Q be n x p matrices A(CP) = (AC)P C A C A P P k X m n X p m X n X p m X n k X m n X p k X m X n m X n 103 106 P A AC CP k X m X p k X n X p k X m m X p n X p k X n 106 103
Practical Issue - GPU 10000 10000 10000 Multiplying two 10000 X 10000 matrices CPU: 21.2 (GTX 980 Ti) GPU: 0.84 More than 20 times faster
