Differences between revisions 6 and 9 (spanning 3 versions)

Matrix Multiplication

Matrix multiplication is a fundamental operation.

Contents

Matrix Multiplication

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 x^TA = y^T. Alternatively, the multiplication is as (A^Tx)^T = y^T.

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

LinearAlgebra/MatrixMultiplication (last edited 2025-03-28 03:00:49 by DominicRicottone)

-  ⇤ ← Revision 6 as of 2023-10-30 18:01:59 → 
  Size: 3078
  Editor: DominicRicottone
  Comment: Made notation consistent
+   ← 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 2:
+'''Matrix multiplication''' is a fundamental operation.
-Line 9:
+Line 11:
-== Introduction ==
+== Dimensions ==
-Line 11:
+Line 13:
-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''.
+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 '''''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.

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 14:
+Line 32:
-julia> A = [1 2
            0 0
            0 0]
+julia> A = [1 2; 0 0; 0 0]
-Line 22:
+Line 38:
-julia> B = [1 0 0
            2 0 0]
+julia> B = [1 0 0; 2 0 0]
-Line 33:
+Line 48:
+julia> B * A
2×2 Matrix{Int64}:
 1  2
 2  4
-Line 34:
+Line 54:
-A cell in a matrix is expressed as ''c,,ij,,'' where ''i'' is a row index and ''j'' is a column index.
-Line 41:
+Line 59:
-== Computation ==
+== 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 [[LinearAlgebra/VectorMultiplication#Dot_Product|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
}}}

----
-Line 45:
+Line 88:
-=== Cell-wise ===
+== Column-wise Computation ==
-Line 47:
+Line 90:
-In a multiplication of matrices '''''A''''' and '''''B''''', cell ''c,,ij,,'' of the new matrix '''''C''''' is the [[LinearAlgebra/VectorMultiplication#Dot_Product|dot product]] of row '''''A,,i,,''''' and column '''''B,,j,,'''''.
+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,, = [1 2]'':
-Line 50:
+Line 95:
-julia> [1 2; 3 4] * [1 0; 0 1]
2×2 Matrix{Int64}:
 1  2
 3  4
+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
-Line 55:
+Line 107:
+----
-Line 58:
+Line 112:
-=== Row-wise ===
+== Row-wise Computation ==
-Line 60:
+Line 114:
-Row ''i'' of '''''C''''' is a linear combination of the columns of '''''B'''''.
+Row '''''C''',,i,,'' is a linear combination of all rows in '''''B''''' taken according to the row '''''A''',,i,,''.
-Line 62:
+Line 116:
-Solving for each row as:
+Referencing the complete solution above and recall that '''''A''',,1,, = [1 2]'':
-Line 65:
+Line 119:
-row 1 = 1(column 1 of B) + 2(column 2 of B)
      = 1[1 0] + 2[0 1]
      = [1 0] + [0 2]
      = [1 2]
+C  = 1*B  + 2*B
 1      1      2
-Line 70:
+Line 122:
-row 2 = 3(column 1 of B) 4(column 2 of B)
      = 3[1 0] + 4[0 1]
      = [3 0] + [0 4]
      = [3 4]
+C  = 1*[1 0 0] + 2*[2 0 0]
 1

C  = [1 0 0] + [4 0 0]
 1

C  = [5 0 0]
 1
-Line 75:
+Line 131:
+----
-Line 78:
+Line 136:
-=== Column-wise ===
+== Block-wise Computation ==
-Line 80:
+Line 138:
-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.
+Matrix multiplication can be evaluated in blocks. Suppose '''''A''''' and '''''B''''' are 20x20 matrices; they can be divided each into 10x10 quadrants.
-Line 155:
+Line 172:
-The entire product could be computed, as in:
+The entire product could be computed:
-Line 166:
+Line 183:
-But if a specific block of the product is of interest, it can be solved as '''''C^1^''''' = '''''A^1^B^1^''''' + '''''A^2^B^3^'''''.
+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^''.

Diff for "LinearAlgebra/MatrixMultiplication"