Matrix Multiplication

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 Cij where i is a row index and j is a column index.

Multiplication

Cell-wise

In a multiplication of matrices A and B, cell Cij is solved as (row i of A)(column j of B).

Consider the following: 

┌    ┐┌    ┐   ┌    ┐
│ 1 2││ 1 0│   │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└    ┘└    ┘   └    ┘

cell (1,1) = (row 1 of A)(column 1 of B)
           = [1 2][1 0]
           = (1 * 1) + (2 * 0)
           = 1

cell (1,2) = (row 1 of A)(column 2 of B)
           = [1 2][0 1]
           = (1 * 0) + (2 * 1)
           = 2

cell (2,1) = [3 4][1 0]
           = 3

cell (2,2) = [3 4][0 1]
           = 4

Row-wise

In a multiplication of matrices A and B, row i of C is a linear combination of the columns of B.

Consider the following: 

┌    ┐┌    ┐   ┌    ┐
│ 1 2││ 1 0│   │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└    ┘└    ┘   └    ┘

row 1 = 1(column 1 of B) + 2(column 2 of B)
      = 1[1 0] + 2[0 1]
      = [1 0] + [0 2]
      = [1 2]

row 2 = 3(column 1 of B) 4(column 2 of B)
      = 3[1 0] + 4[0 1]
      = [3 0] + [0 4]
      = [3 4]

Column-wise

In a multiplication of matrices A and B, column j of C is a linear combination of the rows of A.

Consider the following: 

┌    ┐┌    ┐   ┌    ┐
│ 1 2││ 1 0│   │ 1 2│
│ 3 4││ 0 1│ = │ 3 4│
└    ┘└    ┘   └    ┘

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

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. 

      ┌    ┐┌    ┐        ┌    ┐
      │ 1 2││ 1 0│        │ 1 2│
      │ 3 4││ 0 1│      = │ 3 4│
      └    ┘└    ┘        └    ┘

┌  ┐┌    ┐   ┌  ┐┌    ┐   ┌    ┐
│ 1││ 1 0│   │ 2││ 0 1│   │ 1 2│
│ 3│└    ┘ + │ 4│└    ┘ = │ 3 4│
└  ┘         └  ┘         └    ┘

    ┌    ┐   ┌    ┐       ┌    ┐
    │ 1 0│   │ 0 2│       │ 1 2│
    │ 3 0│ + │ 0 4│     = │ 3 4│
    └    ┘   └    ┘       └    ┘

Block-wise

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. 

┌      ┐┌      ┐   ┌      ┐
│ A1 A2││ B1 B2│   │ C1 C2│
│ A3 A4││ B3 B4│ = │ C3 C4│
└      ┘└      ┘   └      ┘

C1 = A1B1 + A2B3

CategoryRicottone