행렬의 모양·덧셈·곱셈

수를 직사각형 모양으로 늘어놓은 표를 행렬(matrix)이라고 합니다. 사진은 픽셀의 밝기를 늘어놓은 행렬이고, 연립방정식의 계수도 행렬로 적으며, 인접 행렬은 그래프의 연결을 행렬로 나타낸 것이었습니다. 다항식이 인덱스 하나로 계수의 뜻을 정했다면, 행렬은 행과 열이라는 인덱스 두 개로 칸의 뜻을 정합니다. 이 글에서는 행렬을 Python의 중첩 리스트로 나타내고, 행렬의 덧셈과 곱셈을 구현합니다. 특히 행렬 곱셈은 같은 칸끼리 곱하는 것이 아니라 행과 열을 짝지어 계산하는데, 왜 그렇게 정의하는지를 예로 확인합니다.

모양과 표현

가로줄을 행(row), 세로줄을 열(column)이라 하고, 행이 m개이고 열이 n개인 행렬을 m × n 행렬이라고 합니다. 이 m × n을 행렬의 모양(shape)이라고 하겠습니다. Python에서는 행 하나를 리스트로, 행렬 전체를 행들의 리스트로 나타냅니다. [[1, 2, 3], [4, 5, 6]]은 행이 2개, 열이 3개인 2 × 3 행렬이고, i행 j열의 값은 matrix[i][j]로 읽습니다.

중첩 리스트는 행마다 길이가 달라도 만들 수 있으므로, 행렬로 쓰기 전에 모든 행의 길이가 같은지 확인해야 합니다. 아래의 matrix_shape는 모양을 돌려주면서 이것을 검사합니다. 빈 리스트 []는 행도 열도 없는 0 × 0 행렬로 받지만, [[]]처럼 길이가 0인 행이 있거나 행의 길이가 서로 다른 입력은 거절합니다.

행렬을 새로 만들 때는 인접 행렬에서 본 것처럼 [[0] * n] * m을 쓰면 안 됩니다. 모든 행이 같은 리스트를 가리켜서 한 칸을 바꾸면 모든 행이 함께 바뀌기 때문입니다. 이 글의 코드는 리스트 컴프리헨션으로 행을 하나씩 따로 만듭니다.

덧셈: 같은 칸끼리

모양이 같은 두 행렬을 더할 때는 같은 위치의 칸끼리 더합니다. 결과도 같은 모양이고, i행 j열의 값은 두 행렬의 i행 j열의 값을 더한 것입니다. 모양이 다르면 짝이 맞지 않는 칸이 생기므로 더할 수 없습니다.

곱셈: 행과 열을 짝지어 곱한다

행렬 곱셈은 덧셈과 전혀 다르게 정의됩니다. A가 m × k 행렬이고 B가 k × n 행렬일 때, 곱 AB는 m × n 행렬이고 그 i행 j열의 값은 A의 i행과 B의 j열을 짝지어 계산합니다. A의 i행에 있는 k개의 값과 B의 j열에 있는 k개의 값을 앞에서부터 하나씩 짝지어 곱한 뒤 모두 더하는 것입니다. 이렇게 같은 길이의 두 수열을 짝지어 곱해 더한 값을 내적(dot product)이라고 합니다. A의 행과 B의 열이 같은 길이 k여야 짝이 맞으므로, A의 열 수와 B의 행 수가 같을 때만 곱할 수 있습니다.

A = [[1, 2], [3, 4]]와 B = [[5, 6], [7, 8]]의 곱을 칸마다 계산하면 다음과 같습니다.

왜 이렇게 곱할까

행렬 곱셈이 이렇게 정의된 이유는 실제로 이런 계산이 자주 필요하기 때문입니다. 과일 가게에서 날마다 사과와 배를 판 개수를 행렬 A로, 과일마다 판매 가격과 원가를 행렬 B로 적었다고 해 봅시다.

첫날의 매출은 사과 3개 × 500원 + 배 1개 × 800원 = 2300원입니다. 이것은 A의 첫날 행 [3, 1]과 B의 판매 가격 열 [500, 800]을 짝지어 곱해 더한 값, 곧 AB의 0행 0열입니다. 같은 방식으로 첫날의 원가는 3 × 300 + 1 × 500 = 1400원으로 AB의 0행 1열이 됩니다. 행렬 곱 AB는 "날마다의 판매 가격 합계와 원가 합계"를 한꺼번에 계산한 표입니다. A의 열인 과일 종류와 B의 행인 과일 종류가 같은 것을 가리켜야 짝을 지을 수 있다는 것이, 앞 행렬의 열 수와 뒤 행렬의 행 수가 같아야 한다는 조건의 뜻입니다.

코드로 옮기기

def matrix_shape(matrix):
    if not matrix:
        return 0, 0
    columns = len(matrix[0])
    if columns == 0 or any(len(row) != columns for row in matrix):
        raise ValueError("행의 길이가 모두 같고 0보다 커야 합니다")
    return len(matrix), columns


def matrix_add(first, second):
    if matrix_shape(first) != matrix_shape(second):
        raise ValueError("두 행렬의 모양이 같아야 합니다")
    return [[a + b for a, b in zip(row_a, row_b)] for row_a, row_b in zip(first, second)]


def matrix_multiply(first, second):
    rows, shared = matrix_shape(first)
    other_rows, columns = matrix_shape(second)
    if shared != other_rows:
        raise ValueError("앞 행렬의 열 수와 뒤 행렬의 행 수가 같아야 합니다")
    return [[sum(first[i][k] * second[k][j] for k in range(shared))
             for j in range(columns)] for i in range(rows)]


a = [[1, 2], [3, 4]]
b = [[5, 6], [7, 8]]
print(matrix_add(a, b))
print(matrix_multiply(a, b))
print(matrix_multiply(b, a))
print(matrix_multiply([[3, 1], [2, 4]], [[500, 300], [800, 500]]))
try:
    matrix_multiply([[1, 2, 3], [4, 5, 6]], [[1, 2], [3, 4]])
except ValueError as error:
    print("오류:", error)

[[6, 8], [10, 12]]
[[19, 22], [43, 50]]
[[23, 34], [31, 46]]
[[2300, 1400], [4200, 2600]]
오류: 앞 행렬의 열 수와 뒤 행렬의 행 수가 같아야 합니다

matrix_add의 zip은 두 행렬에서 같은 번째 행을, 다시 두 행에서 같은 번째 값을 짝지어 줍니다. 모양을 먼저 검사했으므로 짝이 모자라는 일이 없습니다. matrix_multiply의 중첩 리스트 컴프리헨션은 바깥쪽이 결과의 행 i를, 안쪽이 열 j를 돌며, sum이 k마다의 곱을 모두 더해 한 칸을 만듭니다. 마지막 예는 2 × 3 행렬과 2 × 2 행렬을 곱하려 해서 거절된 것입니다.

곱하는 순서를 바꾸면 결과가 달라진다

출력에서 AB는 [[19, 22], [43, 50]]이지만 BA는 [[23, 34], [31, 46]]입니다. 수의 곱셈과 달리 행렬 곱셈에서는 일반적으로 AB와 BA가 같지 않습니다. AB는 A의 행과 B의 열을, BA는 B의 행과 A의 열을 짝짓는 서로 다른 계산이기 때문입니다. 모양이 맞지 않으면 아예 한쪽만 계산할 수 있습니다. 2 × 3 행렬과 3 × 4 행렬은 곱할 수 있어 2 × 4가 되지만, 순서를 바꾸면 3 × 4 행렬의 열 4와 2 × 3 행렬의 행 2가 달라서 곱할 수 없습니다.

반면 세 행렬을 곱할 때 어느 둘을 먼저 곱하든 결과는 같습니다. 곧 (AB)C = A(BC)라는 결합법칙은 성립합니다. 또 대각선이 1이고 나머지가 0인 정사각 행렬 I는 어느 쪽에서 곱해도 상대 행렬을 바꾸지 않아, 수의 곱셈에서 1과 같은 역할을 합니다. 이것을 단위 행렬(identity matrix)이라고 합니다. 피보나치 수를 행렬 거듭제곱으로 구할 때 결과를 단위 행렬에서 시작한 것도 이 때문입니다.

비용

모양이 m × n인 두 행렬의 덧셈은 칸마다 한 번씩 더하므로 O(mn)입니다. m × k 행렬과 k × n 행렬의 곱셈은 결과의 mn개 칸마다 k번 곱하고 더하므로 O(mkn)이고, 두 n × n 행렬이라면 O(n³)입니다. 결과를 저장하는 공간은 O(mn)입니다.

O(n³)보다 빠른 곱셈 방법도 있습니다. 1969년 Volker Strassen은 2 × 2 블록의 곱셈을 여덟 번이 아니라 일곱 번으로 할 수 있음을 보였고, 이것을 되풀이하면 n의 약 2.807제곱에 비례하는 시간이 됩니다. 실제 수치 계산에서는 NumPy처럼 메모리를 읽는 순서까지 다듬어 C나 Fortran으로 구현한 라이브러리를 쓰며, 이 글의 함수는 계산의 원리를 확인하기 위한 것입니다.

더 깊이: 인접 행렬을 곱하면 길의 개수가 나온다

방향 그래프의 인접 행렬 A를 자기 자신과 곱하면 재미있는 일이 생깁니다. A²의 i행 j열은 A의 i행과 A의 j열의 내적, 곧 모든 정점 k에 대해 A[i][k] × A[k][j]를 더한 값입니다. 이 곱은 i→k와 k→j가 모두 있을 때만 1이므로, 합은 i에서 정확히 간선 두 개로 j에 가는 길의 개수가 됩니다.

def matrix_multiply(first, second):
    return [[sum(first[i][k] * second[k][j] for k in range(len(second)))
             for j in range(len(second[0]))] for i in range(len(first))]


adjacency = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0],
]
for row in matrix_multiply(adjacency, adjacency):
    print(row)

[0, 0, 1, 2]
[0, 0, 0, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]

간단히 하려고 모양 검사는 뺐습니다. 정점 0, 1, 2, 3과 간선 0→1, 0→2, 1→2, 1→3, 2→3에서, 0행 3열의 2는 0에서 3으로 간선 두 개로 가는 길이 0→1→3과 0→2→3의 두 가지라는 뜻입니다. 같은 방식으로 Aᵏ의 칸은 간선 k개로 가는 길의 개수입니다. 여기서 세는 길은 같은 정점이나 간선을 다시 지나도 되는 보행이라서, 사이클이 있는 그래프에서는 같은 정점을 두 번 지나는 길도 함께 셉니다. 이 곱셈에서 곱을 and로, 합을 or로 바꾸면 개수 대신 간선 두 개로 갈 수 있는지만 알려 주는 부울 곱이 됩니다. Warshall 알고리즘의 갱신식도 같은 and와 or를 쓰지만, 행렬을 거듭 곱하는 대신 중간 정점 k를 가장 바깥 반복에 두고 표 하나를 고쳐 가며 간선 개수에 상관없이 갈 수 있는지를 한꺼번에 구합니다. 부울 곱의 거듭제곱으로 구하는 방법과 Warshall 알고리즘의 비교는 이산수학의 관계와 그래프를 계산하는 행렬에서 다룹니다.

정리

• 행렬은 수를 행과 열로 늘어놓은 표이며, 중첩 리스트로 나타내고 모든 행의 길이가 같은지 먼저 검사합니다. 행이 m개, 열이 n개이면 모양이 m × n입니다.
• 덧셈은 모양이 같은 두 행렬의 같은 칸끼리 더합니다.
• 곱셈 AB는 A의 열 수와 B의 행 수가 같을 때만 정의되며, i행 j열은 A의 i행과 B의 j열을 짝지어 곱해 더한 내적입니다.
• 행렬 곱셈은 일반적으로 AB와 BA가 다르지만, 결합법칙은 성립하고 단위 행렬은 곱해도 상대를 바꾸지 않습니다.
• 덧셈은 O(mn), 곱셈은 O(mkn)이며, 인접 행렬의 k제곱은 간선 k개로 가는 길의 개수를 알려 줍니다.

연습 문제

1. 곱할 수 있는 모양

2 × 3 행렬과 3 × 4 행렬의 곱은 가능한가요? 가능하다면 결과의 모양은 무엇이고, 결과의 한 칸을 계산할 때 곱셈을 몇 번 하나요?

2. AB와 BA

본문의 출력에서 AB와 BA를 비교하세요. 행렬 곱셈에서 AB와 BA가 늘 같다고 말할 수 있나요?

3. 가게 예제 읽기

본문의 과일 가게 예제에서 AB의 1행은 [4200, 2600]입니다. 이 두 수는 무엇을 뜻하며, 둘째 날의 이익은 얼마인가요?

다음 장은 선택 심화입니다. 선택 심화: Shell 정렬과 간격으로 정렬을 더 깊이 다루거나, 핵심 내용을 복습하려면 종합: 지도 요구에서 경로와 검사까지로 먼저 넘어가도 됩니다.