Differences between revisions 6 and 7

Matrix Multiplication

Contents

Matrix Multiplication

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 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-09-25 15:49:50 by DominicRicottone)

-  ⇤ ← Revision 6 as of 2023-10-30 18:01:59 → 
  Size: 3078
  Editor: DominicRicottone
  Comment: Made notation consistent
+   ← 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 9:
-== Introduction ==
+== Properties ==
 Line 11:
-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''.
+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.
-Line 14:
+Line 18:
-julia> A = [1 2
            0 0
            0 0]
+julia> A = [1 2; 0 0; 0 0]
-Line 22:
+Line 24:
-julia> B = [1 0 0
            2 0 0]
+julia> B = [1 0 0; 2 0 0]
-Line 33:
+Line 34:
+julia> B * A
2×2 Matrix{Int64}:
 1  2
 2  4
-Line 34:
+Line 40:
-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 45:
-== 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 74:
-=== Cell-wise ===
+== Column-wise Computation ==
-Line 47:
+Line 76:
-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 81:
-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 93:
+----
-Line 58:
+Line 98:
-=== Row-wise ===
+== Row-wise Computation ==
-Line 60:
+Line 100:
-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 102:
-Solving for each row as:
+Referencing the complete solution above and recall that '''''A''',,1,, = [1 2]'':
-Line 65:
+Line 105:
-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 108:
-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 117:
+----
-Line 78:
+Line 122:
-=== Column-wise ===
+== Block-wise Computation ==
-Line 80:
+Line 124:
-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 158:
-The entire product could be computed, as in:
+The entire product could be computed:
-Line 166:
+Line 169:
-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"