= Matrix Multiplication = '''Matrix multiplication''' is a fundamental operation corresponding to [[LinearAlgebra/LinearMapping|homomorphisms]]. See also [[Calculus/VectorOperations|vector operations]]. <> ---- == Dimensions == To multiply two matrices (i.e., '''''AB''' = '''C'''''), they must have a common dimension. '''''A''''' must be as wide as '''''B''''' is tall, and the product will be as wide as '''''B''''' and as tall as '''''A'''''. Alternatively: '''''A''''' has shape ''m x n'' (rows by columns), and '''''B''''' has shape ''n x p'', so the product '''''C''''' will have shape ''m x p''. This can be visualized as: {{{ ┌ ┐ │ 1 . │ │ 2 . │ │ 3 . │ │ 4 . │ ┌ ┐ <=> └ ┘ │ B │ ┌ ┐ ┌ ┐ └ ┘ │ 1 2 3 4 │ │ 30 . │ ┌ ┐ ┌ ┐ │ . . . . │ │ . . │ │ A │ │ C │ │ . . . . │ │ . . │ └ ┘ └ ┘ └ ┘ └ ┘ }}} Vectors are columns by convention, so a matrix can only be multiplied by a vector on the right (i.e., '''''A'''x = y''). The only workaround is to denote the [[LinearAlgebra/Transposition|transposed]] vector (i.e., ''x^T^'''A'''''). Violations of these dimensional requirements mean the product DNE. ---- == Description == The product of two matrices (i.e., '''''AB''' = '''C''''') is a linear combination of the rows of '''''A''''' according to the columns of '''''B''''', or a linear combination of the columns of '''''B''''' according to the rows of '''''A'''''. === Properties === Matrix multiplication is ''not'' commutative. Matrix multiplication is associative: ''('''AB''')'''X''' = '''A'''('''BX''')''. Furthermore, scalar multiplication is associative within matrix multiplication: ''r('''AB''') = (r'''A''')'''B''' = '''A'''(r'''B''')''. Matrix multiplication has distinct left and right distributive properties: '''''A'''('''B'''+'''C''') = '''AB''' + '''AC''''' and ''('''B'''+'''C''')'''A''' = '''BA''' + '''CA''''' respectively. ---- == Cell-wise Computation == A cell in a matrix is expressed as '''''A''',,ij,,'' where ''i'' is a row index and ''j'' is a column index. Indexing starts at 1. For '''''C''' = '''AB''''': '''''C''',,ij,,'' can be computed as the [[Calculus/VectorOperations#Dot_Product|dot product]] of row '''''A''',,i,,'' and column '''''B''',,j,,''. Referencing the complete solution above: {{{ julia> A[1, :] 2-element Vector{Int64}: 1 2 julia> B[:, 1] 2-element Vector{Int64}: 1 2 julia> using LinearAlgebra julia> dot(A[1, :], B[:, 1]) 5 }}} ---- == Column-wise Computation == Column '''''C''',,j,,'' is a linear combination of all columns in '''''A''''' taken according to the column '''''B''',,j,,''. Referencing the complete solution above and recall that '''''B''',,1,, = [1 2]'': {{{ C = 1*A + 2*A 1 1 2 C = 1*[1 0 0] + 2*[2 0 0] 1 C = [1 0 0] + [4 0 0] 1 C = [5 0 0] 1 }}} ---- == Row-wise Computation == Row '''''C''',,i,,'' is a linear combination of all rows in '''''B''''' taken according to the row '''''A''',,i,,''. Referencing the complete solution above and recall that '''''A''',,1,, = [1 2]'': {{{ C = 1*B + 2*B 1 1 2 C = 1*[1 0 0] + 2*[2 0 0] 1 C = [1 0 0] + [4 0 0] 1 C = [5 0 0] 1 }}} ---- == Block-wise Computation == Matrix multiplication can be evaluated in blocks. Suppose '''''A''''' and '''''B''''' are 20x20 matrices; they can be divided each into 10x10 quadrants. Using these matrices '''''A''''' and '''''B''''' as the building blocks: {{{ julia> A = [1 2; 3 4] 2×2 Matrix{Int64}: 1 2 3 4 julia> B = [1 0; 0 1] 2×2 Matrix{Int64}: 1 0 0 1 }}} Much larger matrices may be composed of these building blocks. {{{ julia> A_ = [A1 A2; A3 A4] 4×4 Matrix{Int64}: 1 2 1 2 3 4 3 4 1 2 1 2 3 4 3 4 julia> B_ = [B1 B2; B3 B4] 4×4 Matrix{Int64}: 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 }}} The entire product could be computed: {{{ julia> A_ * B_ 4×4 Matrix{Int64}: 2 4 2 4 6 8 6 8 2 4 2 4 6 8 6 8 }}} But if a specific block of the product is of interest, it can be solved like '''''C'''^1^ = '''A'''^1^'''B'''^1^ + '''A'''^2^'''B'''^3^''. {{{ julia> A1 * B1 + A2 * B3 2×2 Matrix{Int64}: 2 4 6 8 }}} ---- CategoryRicottone