Matrix Multiplication

Introduction

Matrices are multiplied non-commutatively. The m rows of A are multiplied by the p rows of B. A must be as tall as B is wide.

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

A cell in a matrix is expressed as c_ij where i is a row index and j is a column index.

Computation

Cell-wise

In a multiplication of matrices A and B, cell c_ij of the new matrix C is the dot product of row A_i and column B_j.

julia> [1 2; 3 4] * [1 0; 0 1]
2×2 Matrix{Int64}:
 1  2
 3  4

Row-wise

Row i of C is a linear combination of the columns of B.

Solving for each row as:

row 1 = 1(column 1 of B) + 2(column 2 of B)
      = 1[1 0] + 2[0 1]
      = [1 0] + [0 2]
      = [1 2]

row 2 = 3(column 1 of B) 4(column 2 of B)
      = 3[1 0] + 4[0 1]
      = [3 0] + [0 4]
      = [3 4]

Column-wise

Column j of C is a linear combination of the rows of A.

Solving for each column as:

column 1 = 1(row 1 of A) + 0(row 2 of A)
         = 1[1 2] + 0
         = [1 2]

column 2 = 0(row 1 of A) + 1(row 2 of A)
         = 0 + 1[3 4]
         = [3 4]

Summation

C can be evaluated as a summation of the columns of A by the rows of B.

julia> [1; 2] * [1 0]
2×2 Matrix{Int64}:
 1  0
 2  0

julia> [3; 4] * [0 1]
2×2 Matrix{Int64}:
 0  3
 0  4

julia> [1; 2] * [1 0] + [3; 4] * [0 1]
2×2 Matrix{Int64}:
 1  3
 2  4

Block-wise

C can be evaluated block-wise. 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, as in:

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 as C¹ = A¹B¹ + A²B³.

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

CategoryRicottone