행렬 곱셈과 행렬 거듭제곱

개념

행렬은 값을 행과 열로 배치한 것입니다. $R\times K$ 행렬과 $K\times C$ 행렬을 곱하면 $R\times C$ 행렬을 얻습니다. 앞 행렬의 열 수와 뒤 행렬의 행 수가 같아야 합니다.

행렬 곱셈

결과의 한 원소는 앞 행렬의 행과 뒤 행렬의 열에서 같은 위치의 값을 곱해 더합니다.

$C_{ij}=\sum_{k=0}^{K-1} A_{ik}B_{kj}.$

일반적으로 $AB$ 와 $BA$ 는 다르므로 곱하는 순서를 지켜야 합니다. 행렬 곱셈에는 결합법칙이 성립하므로 $(AB)C=A(BC)$ 입니다.

예를 들어 다음 두 행렬의 곱에서 첫 행·첫 열의 값은 $1\times5+2\times7=19$ 입니다. 첫 행·둘째 열의 값은 $1\times6+2\times8=22$ 입니다.

$\begin{pmatrix}1&2\\3&4\end{pmatrix}\begin{pmatrix}5&6\\7&8\end{pmatrix}=\begin{pmatrix}19&22\\43&50\end{pmatrix}.$

결과 행렬의 원소 하나를 구할 때 앞 행렬의 한 행과 뒤 행렬의 한 열에서 같은 개수의 원소를 짝지어야 하므로, 앞의 열 수와 뒤의 행 수가 같아야 합니다.

행렬 거듭제곱

정사각행렬 $A$ 를 반복해서 곱한 $A^B$ 도 지수를 절반으로 나누어 계산합니다. $A^{2k}=A^kA^k$ , $A^{2k+1}=A^kA^kA$ 입니다.

지수 $0$ 의 결과는 항등행렬입니다. 항등행렬은 대각 원소가 $1$ , 나머지가 $0$ 이며 $AI=IA=A$ 를 만족합니다.

같은 규칙을 여러 단계 적용하는 계산을 행렬로 표현할 수 있으면 행렬 거듭제곱을 사용할 수 있습니다. 예를 들어 두 수 $(x,y)$ 를 한 단계마다 $(x+y,x)$ 로 바꾸는 규칙은 다음과 같습니다.

$\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}x+y\\x\end{pmatrix}.$

$(1,0)$ 에서 시작하면 $(1,1)\to(2,1)\to(3,2)$ 가 됩니다. 같은 행렬을 세 번 곱하면 세 단계의 결과를 얻으므로, $B$ 단계의 결과는 행렬의 $B$ 제곱으로 계산합니다. 결합법칙에 따라 곱셈을 묶을 수 있어 지수를 절반으로 줄여 구한 행렬을 제곱하는 방법이 성립합니다. 상태의 개수에 해당하는 행렬 크기는 작고, 반복 단계 수는 큰 문제에 적합합니다.

복잡도

정사각행렬의 한 변 크기를 $N$ , 지수를 $B$ 라고 합니다.

연산	시간복잡도	공간복잡도
행렬 곱셈	$O(N^3)$	결과 행렬 $O(N^2)$
재귀 빠른 거듭제곱	$O(N^3\log(B+1))$	중간 행렬·재귀 $O(N^2\log(B+1))$

예제

문제

정사각행렬의 $B$ 제곱을 구하여라.

입력

첫째 줄에 행렬의 크기 $N$ 과 지수 $B$ 가 공백을 사이에 두고 주어진다. $1\le N\le3$ ; $0\le B\le8$ 이다.

다음 $N$ 개 줄에 행렬의 각 행을 이루는 정수 $N$ 개가 공백을 사이에 두고 주어진다. 각 원소는 $0$ 이상 $2$ 이하이다.

출력

결과 행렬을 $N$ 개 줄에 출력한다. 같은 행의 값은 공백으로 구분한다.

예제 코드

C++20

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<int>> a, t;

vector<vector<int>> mul(const vector<vector<int>>& a, const vector<vector<int>>& b) {
    int i, j, k;
    vector<vector<int>> c(n, vector<int>(n));

    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            for (k = 0; k < n; ++k) {
                // a의 i행과 b의 j열에서 같은 위치의 곱을 누적
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

vector<vector<int>> power(const vector<vector<int>>& a, int b) {
    int i;
    vector<vector<int>> t;

    // 행렬의 0제곱은 대각 원소가 1인 항등행렬
    if (b == 0) {
        t.assign(n, vector<int>(n));
        for (i = 0; i < n; ++i) {
            t[i][i] = 1;
        }
        return t;
    }
    // 절반 지수의 결과를 한 번 계산하여 재사용
    t = power(a, b / 2);
    t = mul(t, t);
    // 홀수 지수에서 제곱 후 남은 행렬 a를 한 번 곱함
    if (b % 2 == 1) t = mul(t, a);
    return t;
}

int main() {
    int b, i, j;

    cin >> n >> b;
    a.assign(n, vector<int>(n));
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    // 절반 지수의 결과를 한 번 계산하여 재사용
    t = power(a, b);

    for (const auto& row : t) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

Java 17

import java.util.*;

public class Main {
    static int n;

    static int[][] mul(int[][] a, int[][] b) {
        int i, j, k;
        int[][] c;

        c = new int[n][n];
        for (i = 0; i < n; ++i) {
            for (j = 0; j < n; ++j) {
                for (k = 0; k < n; ++k) {
                    // a의 i행과 b의 j열에서 같은 위치의 곱을 누적
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return c;
    }

    static int[][] power(int[][] a, int b) {
        int i;
        int[][] t;

        // 행렬의 0제곱은 대각 원소가 1인 항등행렬
        if (b == 0) {
            t = new int[n][n];
            for (i = 0; i < n; ++i) {
                t[i][i] = 1;
            }
            return t;
        }
        // 절반 지수의 결과를 한 번 계산하여 재사용
        t = power(a, b / 2);
        t = mul(t, t);
        // 홀수 지수에서 제곱 후 남은 행렬 a를 한 번 곱함
        if (b % 2 == 1) t = mul(t, a);
        return t;
    }

    public static void main(String[] args) {
        Scanner in;
        int b, i, j;
        int[][] a, t;

        in = new Scanner(System.in);
        n = in.nextInt();
        b = in.nextInt();
        a = new int[n][n];
        for (i = 0; i < n; ++i) {
            for (j = 0; j < n; ++j) {
                a[i][j] = in.nextInt();
            }
        }
        // 절반 지수의 결과를 한 번 계산하여 재사용
        t = power(a, b);

        for (int[] row : t) {
            for (int x : row) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
}

Python 3

def mul(a, b):
    c = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                # a의 i행과 b의 j열에서 같은 위치의 곱을 누적
                c[i][j] += a[i][k] * b[k][j]
    return c


def power(a, b):
    # 행렬의 0제곱은 대각 원소가 1인 항등행렬
    if b == 0:
        t = [[0] * n for _ in range(n)]
        for i in range(n):
            t[i][i] = 1
        return t
    # 절반 지수의 결과를 한 번 계산하여 재사용
    t = power(a, b // 2)
    t = mul(t, t)
    # 홀수 지수에서 제곱 후 남은 행렬 a를 한 번 곱함
    if b % 2 == 1:
        t = mul(t, a)
    return t


n, b = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
# 절반 지수의 결과를 한 번 계산하여 재사용
t = power(a, b)

for row in t:
    print(*row)

2.10.3 Matrix Multiplication & Power

개념

행렬 곱셈

행렬 거듭제곱

복잡도

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드