Matrix Multiplication

Matrix multiplication is a fundamental operation.

See also vector operations.

Dimensions

To multiply a matrix by another matrix as 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 rows by n columns, and B has shape n rows by p columns, so the product C will have m rows and p columns.

This can be visualized as:

                              ┌      ┐
                              │  1 . │
                              │  2 . │
                              │  3 . │
                              │  4 . │
       ┌   ┐ <=>              └      ┘
       │ B │     ┌         ┐  ┌      ┐
       └   ┘     │ 1 2 3 4 │  │ 30 . │
┌   ┐  ┌   ┐     │ . . . . │  │  . . │
│ A │  │ C │     │ . . . . │  │  . . │
└   ┘  └   ┘     └         ┘  └      ┘

To multiply a matrix by a vector as Ax = y, the vector can be seen as a matrix with n rows and 1 column. The product will also have 1 column, i.e. be a vector.

To multiply a vector by a matrix, the vector must be transposed so that it has n columns and 1 row. In other words, the multiplication is as x^TA = y^T. Alternatively, the multiplication is as (A^Tx)^T = y^T.

Properties

Matrix multiplication is taking linear combinations of the rows of A according to the columns of B, or vice versa.

Matrix 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

Matrix multiplication is however associative: (AB)X = A(BX). The above non-commutativity is necessary for this to hold. The interpretation should be that X is transformed linearly by B then A.

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

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

CategoryRicottone