cp_library/math/linalg/mat/mat_pow_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/math/linalg/mat/mat_id_fn.py
• cp_library/math/linalg/mat/mat_mul_fn.py

Verified with

• test/library-checker/linear-algebra/pow_of_matrix_matpow.test.py

Code

import cp_library.__header__
import cp_library.math.__header__
import cp_library.math.linalg.__header__
import cp_library.math.linalg.mat.__header__

def mat_pow(A,K):
    R = A if K & 1 else mat_id(len(A))
    for i in range(1,K.bit_length()):
        A = mat_mul(A,A) 
        if K >> i & 1: R = mat_mul(R,A) 
    return R 

from cp_library.math.linalg.mat.mat_mul_fn import mat_mul
from cp_library.math.linalg.mat.mat_id_fn import mat_id

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''




def mat_pow(A,K):
    R = A if K & 1 else mat_id(len(A))
    for i in range(1,K.bit_length()):
        A = mat_mul(A,A) 
        if K >> i & 1: R = mat_mul(R,A) 
    return R 


def mat_mul(A,B):
    assert len(A[0]) == len(B)
    R = [[0]*len(B[0]) for _ in range(len(A))] 
    for i,Ri in enumerate(R):
        for k,Aik in enumerate(A[i]):
            for j,Bkj in enumerate(B[k]):
                Ri[j] = Bkj*Aik + Ri[j]  
    return R 

def mat_id(N):
    return [[int(i==j) for j in range(N)] for i in range(N)]

Back to top page