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 . is the inverse of matrix A as long as
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) —
loading...
Last Post: Teaching Kids Programming - Compute the Dot Product using Zip Function in Python
Next Post: Teaching Kids Programming - Matrix Power Algorithm