Differences between revisions 2 and 9 (spanning 7 versions)
⇤ ← Revision 2 as of 2021-09-14 16:13:05 →
Size: 3406
Editor: DominicRicottone
Comment:
← Revision 9 as of 2025-03-28 03:00:49 → ⇥
Size: 4045
Editor: DominicRicottone
Comment: Link
Deletions are marked like this. Additions are marked like this.
Line 3: Line 3:
== Introduction == '''Matrix multiplication''' is a fundamental operation.
Line 5: Line 5:
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 11:
== Multiplication == == Dimensions ==
Line 29: Line 13:
=== Cell-wise === 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.
Line 31: Line 15:
In a multiplication of matrices A and B, cell C,,ij,, is solved as (row `i` of A)(column `j` of B). To multiply '''a matrix by a vector''' as '''''A'''x = 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.
Line 33: Line 17:
Consider the following: To multiply '''a vector by a matrix''', the vector must be [[LinearAlgebra/MatrixTransposition|transposed]] so that it has ''n'' columns and 1 row. In other words, the multiplication is as ''x^T^'''A''' = y^T^''. Alternatively, the multiplication is as ''('''A'''^T^x)^T^ = y^T^''.

For multiplying vectors, see [[LinearAlgebra/VectorMultiplication|vector multiplication]].

----



== 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.
Line 36: Line 32:
┌ ┐┌ ┐ ┌ ┐
│ 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 38:
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 43:
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 49:
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 59:
=== Row-wise === == Cell-wise Computation ==
Line 64: Line 61:
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 63:
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 68:
┌ ┐┌ ┐ ┌ ┐
│ 1 2││ 1 0│ │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└ ┘└ ┘ └ ┘		 julia> A[1, :]
2-element Vector{Int64}:
 1
 2
Line 74: Line 73:
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 78:
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 88:
=== Column-wise === == Column-wise Computation ==
Line 91: Line 90:
Column '''''C''',,j,,'' is a linear combination of all columns in '''''A''''' taken according to the column '''''B''',,j,,''.
Line 92: Line 92:
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 95:
┌ ┐┌ ┐ ┌ ┐
│ 1 2││ 1 0│ │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└ ┘└ ┘ └ ┘		 C = 1*A + 2*A
 1 1 2
Line 102: Line 98:
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 101:
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 112:
=== Summation === == Row-wise Computation ==
Line 117: Line 114:
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 119:
      ┌ ┐┌ ┐ ┌ ┐
      │ 1 2││ 1 0│ │ 1 2│
      │ 3 4││ 0 1│ = │ 3 4│
      └ ┘└ ┘ └ ┘		 C = 1*B + 2*B
 1 1 2
Line 125: Line 122:
┌ ┐┌ ┐ ┌ ┐┌ ┐ ┌ ┐
│ 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 125:
    ┌ ┐ ┌ ┐ ┌ ┐
    | 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 136:
=== Block-wise === == Block-wise Computation ==
Line 142: Line 138:
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 143:
┌ ┐┌ ┐ ┌ ┐
│ 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 154:
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

Matrix multiplication is a fundamental operation.

Contents

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

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.

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 xTA = yT. Alternatively, the multiplication is as (ATx)T = yT.

For multiplying vectors, see vector multiplication.

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

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 2025-03-28 03:00:49 by DominicRicottone)