Matrix Multiplication

Matrix multiplication is a fundamental operation.

See also 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., Ax = y). The only workaround is to denote the transposed vector (i.e., x^TA).

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) = (rA)B = A(rB).

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 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