Teaching Kids Programming – Matrix Power Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a square Matrix we can compute its power. The result matrix will be of same dimension. Similar to the Integer Power Algorithm, we can achieve the Matrix Multiplication in O(LogN) time.

def matrix_pow(a: List[List[int]], n: int) -> List[List[int]]:
    rows = len(a)
    cols = len(a[0])
    assert rows == cols
    ret = [[0 for _ in range(cols)] for _ in range(rows)]
    for r in range(rows):
        ret[r][r] = 1
    while n > 0:
        if n & 1:
            ret = multiply(ret, a)
        n >>>= 1
        a = multiply(a, a)
    return ret

At the begining, the result Matrix will be set to Identify Matrix with all diagonals set to one and all zeros otherwise. Then, if n is even, we square the base, otherwise we multiply once to the result.

–EOF (The Ultimate Computing & Technology Blog) —