Differences between revisions 3 and 7 (spanning 4 versions)
⇤ ← Revision 3 as of 2021-09-14 16:43:42 →
Size: 3426
Editor: DominicRicottone
Comment:
← Revision 7 as of 2024-06-03 16:56:20 → ⇥
Size: 3263
Editor: DominicRicottone
Comment: Reorg
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
== Introduction ==

Matrices are multiplied non-commutatively.

The ''m'' rows of matrix A are multiplied by the ''p'' rows of matrix B. Therefore, note that A must be as tall as B is wide.

{{{
┌ ┐┌ ┐ ┌ ┐
│ 0 0││ 0 0 0│ │ 0 0 0│
│ 0 0││ 0 0 0│ = │ 0 0 0│
│ 0 0│└ ┘ │ 0 0 0│
└ ┘ └ ┘

  A x B = C

 mxn x nxp = mxp
}}}

A cell in a matrix is expressed as C,,ij,, where `i` is a row index and `j` is a column index.		 <<TableOfContents>>
Line 27: Line 9:
== Multiplication == == Properties ==
Line 29: Line 11:
=== Cell-wise === Two matrices are multiplied as linear combinations; the '''rows''' of '''''A''''' and the '''columns''' of '''''B'''''.
Line 31: Line 13:
In a multiplication of matrices A and B, cell C,,ij,, is solved as (row `i` of A)(column `j` 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.)
Line 33: Line 15:
Consider the following: Order matters. The multiplication is '''not''' commutative.
Line 36: Line 18:
┌ ┐┌ ┐ ┌ ┐
│ 1 2││ 1 0│ │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└ ┘└ ┘ └ ┘		 julia> A = [1 2; 0 0; 0 0]
3×2 Matrix{Int64}:
 1 2
 0 0
 0 0
Line 41: Line 24:
cell (1,1) = (row 1 of A)(column 1 of B)
           = [1 2][1 0]
           = (1 * 1) + (2 * 0)
           = 1		 julia> B = [1 0 0; 2 0 0]
2×3 Matrix{Int64}:
 1 0 0
 2 0 0
Line 46: Line 29:
cell (1,2) = (row 1 of A)(column 2 of B)
           = [1 2][0 1]
           = (1 * 0) + (2 * 1)
           = 2		 julia> A * B
3×3 Matrix{Int64}:
 5 0 0
 0 0 0
 0 0 0
Line 51: Line 35:
cell (2,1) = [3 4][1 0]
           = 3

cell (2,2) = [3 4][0 1]
           = 4		 julia> B * A
2×2 Matrix{Int64}:
 1 2
 2 4
Line 62: Line 45:
=== Row-wise === == Cell-wise Computation ==
Line 64: Line 47:
In a multiplication of matrices A and B, row `i` of C is a linear combination of the columns of B. 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.
Line 66: Line 49:
Consider the following: For '''''C''' = '''AB''''': '''''C''',,ij,,'' can be computed as the [[LinearAlgebra/VectorMultiplication#Dot_Product|dot product]] of row '''''A''',,i,,'' and column '''''B''',,j,,''.

Referencing the complete solution above:
Line 69: Line 54:
┌ ┐┌ ┐ ┌ ┐
│ 1 2││ 1 0│ │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└ ┘└ ┘ └ ┘		 julia> A[1, :]
2-element Vector{Int64}:
 1
 2
Line 74: Line 59:
row 1 = 1(column 1 of B) + 2(column 2 of B)
      = 1[1 0] + 2[0 1]
      = [1 0] + [0 2]
      = [1 2]		 julia> B[:, 1]
2-element Vector{Int64}:
 1
 2
Line 79: Line 64:
row 2 = 3(column 1 of B) 4(column 2 of B)
      = 3[1 0] + 4[0 1]
      = [3 0] + [0 4]
      = [3 4]		 julia> using LinearAlgebra

julia> dot(A[1, :], B[:, 1])
5
Line 89: Line 74:
=== Column-wise === == Column-wise Computation ==
Line 91: Line 76:
Column '''''C''',,j,,'' is a linear combination of all columns in '''''A''''' taken according to the column '''''B''',,j,,''.
Line 92: Line 78:
In a multiplication of matrices A and B, column `j` of C is a linear combination of the rows of A.

Consider the following:		 Referencing the complete solution above and recall that '''''B''',,1,, = [1 2]'':
Line 97: Line 81:
┌ ┐┌ ┐ ┌ ┐
│ 1 2││ 1 0│ │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└ ┘└ ┘ └ ┘		 C = 1*A + 2*A
 1 1 2
Line 102: Line 84:
column 1 = 1(row 1 of A) + 0(row 2 of A)
         = 1[1 2] + 0
         = [1 2]		 C = 1*[1 0 0] + 2*[2 0 0]
 1
Line 106: Line 87:
column 2 = 0(row 1 of A) + 1(row 2 of A)
         = 0 + 1[3 4]
         = [3 4]		 C = [1 0 0] + [4 0 0]
 1

C = [5 0 0]
 1
Line 115: Line 98:
=== Summation === == Row-wise Computation ==
Line 117: Line 100:
In a multiplication of matrices A and B, C can be evaluated as a summation of the columns of A by the rows of B. 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]'':
Line 120: Line 105:
      ┌ ┐┌ ┐ ┌ ┐
      │ 1 2││ 1 0│ │ 1 2│
      │ 3 4││ 0 1│ = │ 3 4│
      └ ┘└ ┘ └ ┘		 C = 1*B + 2*B
 1 1 2
Line 125: Line 108:
┌ ┐┌ ┐ ┌ ┐┌ ┐ ┌ ┐
│ 1││ 1 0│ │ 2││ 0 1│ │ 1 2│
│ 3│└ ┘ + │ 4│└ ┘ = │ 3 4│
└ ┘ └ ┘ └ ┘		 C = 1*[1 0 0] + 2*[2 0 0]
 1
Line 130: Line 111:
    ┌ ┐ ┌ ┐ ┌ ┐
    │ 1 0│ │ 0 2│ │ 1 2│
    │ 3 0│ + │ 0 4│ = │ 3 4│
    └ ┘ └ ┘ └ ┘		 C = [1 0 0] + [4 0 0]
 1

C = [5 0 0]
 1
Line 140: Line 122:
=== Block-wise === == Block-wise Computation ==
Line 142: Line 124:
In a multiplication of matrices A and B, C can be evaluated block-wise. Suppose A and B are 20x20 matrices; they can be divided each into 10x10 quadrants. 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:
Line 145: Line 129:
┌ ┐┌ ┐ ┌ ┐
│ A1 A2││ B1 B2│ │ C1 C2│
│ A3 A4││ B3 B4│ = │ C3 C4│
└ ┘└ ┘ └ ┘		 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
Line 151: Line 140:
C^1^ = A^1^B^1^ + A^2^B^3^ 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
}}}

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

LinearAlgebra/MatrixMultiplication (last edited 2026-01-21 16:22:47 by DominicRicottone)