Matrix Multiplication

Contents

  1. Matrix Multiplication
    1. Properties
    2. Cell-wise Computation
    3. Column-wise Computation
    4. Row-wise Computation
    5. Block-wise Computation

Properties

Two matrices are multiplied as linear combinations; the rows of A and the columns of B.

Two matrices can only be multiplied if their shape is compatible; A must be as tall as B is wide. If A has shape m rows by n columns, then B must have shape p rows by m columns. (The relation between n and p does not matter.)

Order matters. The multiplication is not commutative. 

julia> A = [1 2; 0 0; 0 0]
3×2 Matrix{Int64}:
 1  2
 0  0
 0  0

julia> B = [1 0 0; 2 0 0]
2×3 Matrix{Int64}:
 1  0  0
 2  0  0

julia> A * B
3×3 Matrix{Int64}:
 5  0  0
 0  0  0
 0  0  0

julia> B * A
2×2 Matrix{Int64}:
 1  2
 2  4

Cell-wise Computation

A cell in a matrix is expressed as Aij where i is a row index and j is a column index. Indexing starts at 1.

For C = AB: Cij can be computed as the dot product of row Ai and column Bj.

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 Cj is a linear combination of all columns in A taken according to the column Bj.

Referencing the complete solution above and recall that B1 = [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 Ci is a linear combination of all rows in B taken according to the row Ai.

Referencing the complete solution above and recall that A1 = [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 C1 = A1B1 + A2B3. 

julia> A1 * B1 + A2 * B3
2×2 Matrix{Int64}:
 2  4
 6  8

CategoryRicottone