Teaching Kids Programming – Matrix Add, Subtraction and Multiplication Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

Matrix Add and Subtraction Function

We can add or subtract two matrices if and only if there are of the same sizes (same number of rows and columns).

1
2
3
4
5
6
7
8
9
def add(A, B):
  R = len(A)
  assert R > 0
  C = len(A[0])
  assert C > 0 and R == len(B) and C == len(B[0])
  for r in range(R):
    for c in range(C):
      A[r][c] += B[r][c]  # use -= for subtraction
  return A
def add(A, B):
  R = len(A)
  assert R > 0
  C = len(A[0])
  assert C > 0 and R == len(B) and C == len(B[0])
  for r in range(R):
    for c in range(C):
      A[r][c] += B[r][c]  # use -= for subtraction
  return A

The above algorithm adds two matrix in place in O(RC) time i.e. R is the number of rows and C is the number of columns – the result Matrix is updated using A matrix and thus O(1) space. If we allocate a new matrix for return:

1
2
3
4
5
6
7
8
9
10
def add(A, B):
  R = len(A)
  assert R > 0
  C = len(A[0])
  assert C > 0 and R == len(B) and C == len(B[0])
  M = [[0 for _ in range(C)] for _ in range(R)]
  for r in range(R):
    for c in range(C):
      M[r][c] = A[r][c] + B[r][c]  # use - for subtraction.
  return A
def add(A, B):
  R = len(A)
  assert R > 0
  C = len(A[0])
  assert C > 0 and R == len(B) and C == len(B[0])
  M = [[0 for _ in range(C)] for _ in range(R)]
  for r in range(R):
    for c in range(C):
      M[r][c] = A[r][c] + B[r][c]  # use - for subtraction.
  return A

The time complexity is O(RC) and space complexity is also O(RC)

Matrix Multiply Algorithm

The Identify Matrix (noted as I) is a square matrix with all ones at diagonals and zeros at other places. For example the following is a 3×3 Identity Matrix.

1
2
3
| 1 0 0 |
| 0 1 0 |
| 0 0 1 |
| 1 0 0 |
| 0 1 0 |
| 0 0 1 |

The result of Matrix A multiplied by B will be valid as long as the number of columns of A is equals to the number of rows B. Let’s say A is size of R*X, and B is size of X*C. The result will be R*C.

The top-left of the result Matrix at [0][0] will be the dot product of first row of A and first column of B. That is Result[x][y] will be the dot product of Row x of A and column Y of B.

A matrix A times its Identify matrix will be the same that is tex_962327813bb5b330f8b3e3eb1cbf1f56 Teaching Kids Programming - Matrix Add, Subtraction and Multiplication Algorithm math python teaching kids programming youtube video . tex_d866fb421799ffd9586b9b970253de82 Teaching Kids Programming - Matrix Add, Subtraction and Multiplication Algorithm math python teaching kids programming youtube video is the inverse of matrix A as long as tex_a4673b38edbfc2cb317e90c213fc4044 Teaching Kids Programming - Matrix Add, Subtraction and Multiplication Algorithm math python teaching kids programming youtube video

Let’s see the following Matrix Multiplication implementation in Python.

1
2
3
4
5
6
7
8
9
10
11
12
def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
    rows_a, rows_b = len(a), len(b)
    assert rows_a > 0 and rows_b > 0
    cols_a, cols_b = len(a[0]), len(b[0])
    assert cols_a > 0 and cols_b > 0
    assert cols_a == rows_b
    c = [[0 for _ in range(cols_b)] for _ in range(rows_a)]
    for i in range(rows_a):
        for j in range(cols_b):
            for k in range(cols_a): # or cols_b
                c[i][j] += a[i][k] * b[k][j]
    return c    
def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
    rows_a, rows_b = len(a), len(b)
    assert rows_a > 0 and rows_b > 0
    cols_a, cols_b = len(a[0]), len(b[0])
    assert cols_a > 0 and cols_b > 0
    assert cols_a == rows_b
    c = [[0 for _ in range(cols_b)] for _ in range(rows_a)]
    for i in range(rows_a):
        for j in range(cols_b):
            for k in range(cols_a): # or cols_b
                c[i][j] += a[i][k] * b[k][j]
    return c    

The time complexity is O(R*X*C) and the space complexity is O(R*C).

See also: How to Multiply Two Matrices in C++?

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
739 words
Last Post: Teaching Kids Programming - Compute the Dot Product using Zip Function in Python
Next Post: Teaching Kids Programming - Matrix Power Algorithm

The Permanent URL is: Teaching Kids Programming – Matrix Add, Subtraction and Multiplication Algorithm

Leave a Reply