행렬의 연산과 행렬식

여러 관계가 있는지 없는지를 표로 적거나, 여러 상품의 수량과 가격을 표로 적어 두면 한꺼번에 계산할 수 있습니다. 이런 수의 표에 덧셈과 곱셈의 규칙을 정한 것이 행렬입니다. 이 장은 선택 심화입니다. 관계를 읽은 뒤 8장의 그래프로 먼저 넘어가도 되지만, 관계와 그래프를 행렬로 계산하는 방법을 이해하려면 이 장부터 읽는 것이 좋습니다. 이 글에서는 행렬의 기본 연산과, 정사각행렬에 수 하나를 대응시키는 행렬식을 다룹니다. 여기서 다루는 수는 실수이고, 계산 예에서는 오차가 없도록 정수와 분수를 씁니다.

행렬의 크기와 기본 연산

행이 m개, 열이 n개인 행렬 A를 m × n 행렬이라 하고, i행 j열의 원소를 $a_{ij}$로 씁니다. 크기가 같은 두 행렬은 같은 자리의 원소끼리 더해 $A+B$를 만들고, 수 c를 곱한 $cA$는 모든 원소에 c를 곱한 것입니다. 행과 열을 맞바꾼 행렬을 전치행렬(transpose)이라 하고 $A^T$로 씁니다. 원래 i행 j열에 있던 원소가 전치행렬에서는 j행 i열에 있습니다.

행렬의 곱셈

A가 m × n 행렬이고 B가 n × p 행렬이면 곱 AB는 m × p 행렬이고, i행 j열의 원소는 A의 i행과 B의 j열을 짝지어 곱한 뒤 더한 값입니다.

A의 행과 B의 열이 같은 길이 n이어야 짝이 맞으므로, 곱하려면 A의 열 수와 B의 행 수가 같아야 합니다. 합 기호가 낯설면 수의 체계에서 k에 1부터 n까지를 차례로 넣어 더하는 방법을 복습하면 됩니다. 행렬 곱셈이 왜 이렇게 정의되는지는 알고리즘 교재의 행렬에서 판매량과 가격의 예로 설명했습니다.

def multiply(left, right):
    return [[sum(x * y for x, y in zip(row, column)) for column in zip(*right)] for row in left]


A = [[1, 2], [3, 4]]
B = [[2, 0], [1, 1]]
print(multiply(A, B), multiply(B, A))
print([list(column) for column in zip(*[[1, 2, 3], [4, 5, 6]])])

[[4, 2], [10, 4]] [[2, 4], [4, 6]]
[[1, 4], [2, 5], [3, 6]]

zip(*right)는 행렬 right의 열들을 차례로 내놓으므로, A의 각 행과 B의 각 열을 짝지어 같은 자리의 수끼리 곱해 더한 값, 곧 내적(dot product)을 계산할 수 있습니다. 같은 zip(*m)으로 전치행렬도 만들 수 있습니다. AB의 2행 1열은 A의 둘째 행 (3, 4)와 B의 첫째 열 (2, 1)의 내적 $3\cdot2+4\cdot1=10$입니다. AB와 BA가 다르므로 행렬 곱셈은 일반적으로 순서를 바꿀 수 없습니다. 대각선이 모두 1이고 나머지가 0인 정사각행렬을 단위행렬 I라 하며, 어떤 행렬과 곱해도 $AI=IA=A$입니다.

더 깊이: 곱셈 여덟 번을 일곱 번으로 줄이는 방법

정의대로 n × n 행렬 두 개를 곱하면 결과의 $n^2$개 칸마다 곱셈을 n번 하므로 곱셈이 모두 $n^3$번 듭니다. 2 × 2 행렬이라면 8번입니다. 1969년 Strassen은 2 × 2 행렬의 곱을 덧셈과 뺄셈을 더 쓰는 대신 곱셈 7번만으로 구하는 식을 찾았습니다. 예를 들어 결과의 오른쪽 위 칸은 $A_{11}(B_{12}-B_{22})$와 $(A_{11}+A_{12})B_{22}$를 더하면 $A_{11}B_{12}+A_{12}B_{22}$가 되는 식으로, 일곱 개의 곱을 더하고 빼서 네 칸을 모두 만듭니다.

이 식은 행렬의 칸이 수가 아니라 작은 행렬이어도 그대로 성립하므로, 큰 행렬을 네 덩어리로 나누어 같은 방법을 재귀로 쓸 수 있습니다. 크기가 절반인 곱셈 7번과 덧셈 몇 번으로 일을 줄이면, MathWorld의 설명처럼 곱셈의 수가 $n^{\log_2 7}$에 비례하게 됩니다. 이 지수 $\log_2 7$은 약 2.807로 3보다 작습니다. 그 뒤로도 지수를 2.38 아래까지 낮춘 방법들이 나왔습니다. 다만 같은 설명은 Strassen의 방법이 수치적으로 약하게만 안정하다고 적어 두므로, 부동소수로 계산할 때는 줄어든 곱셈의 수와 함께 오차도 따져야 합니다.

행들이 서로 독립이라는 것

행렬의 한 행을 수의 묶음, 곧 행벡터로 봅시다. 행벡터 $r_1,\ldots,r_m$에 수 $c_1,\ldots,c_m$을 곱해 더한 $c_1r_1+\cdots+c_mr_m$을 선형결합(linear combination)이라고 합니다. 같은 자리의 수끼리 곱하고 더하며, 모든 자리가 0인 벡터를 0으로 씁니다.

선형결합이 0이 되는 계수가 $c_1=\cdots=c_m=0$뿐이면 그 행들은 선형 독립(linearly independent)이라 하고, 0이 아닌 계수가 하나라도 있는데 선형결합을 0으로 만들 수 있으면 선형 종속(linearly dependent)이라고 합니다. 선형 종속은 어떤 행을 나머지 행들로 만들어 낼 수 있다는 뜻입니다. 예를 들어 (2, 1)과 (4, 2)는 서로 다르지만 $-2\cdot(2,1)+(4,2)=(0,0)$이므로 종속입니다. 둘째 행이 첫째 행의 두 배라서 새로운 정보를 주지 않는 것입니다. 행이 셋 이상이면, 어느 두 행도 서로 배수가 아닌데 셋째 행이 앞의 두 행의 합인 경우처럼 더 찾기 어려운 종속도 있습니다.

정사각행렬의 행들이 종속이면, 그 행렬로 섞은 정보를 원래대로 되돌릴 수 없습니다. 이것을 수 하나로 알려 주는 것이 행렬식입니다.

행렬식

정사각행렬에 대응하는 수 하나를 행렬식(determinant)이라 하고 $\det A$로 씁니다. 2 × 2 행렬에서는 다음과 같습니다.

앞의 A는 $1\cdot4-2\cdot3=-2$입니다. 실수 정사각행렬에서 행렬식이 0이면 행들이 선형 종속이고 역행렬이 없으며, 0이 아니면 행들이 선형 독립이고 역행렬이 있습니다. 행렬식은 행렬이 아니라 수 하나라는 점도 기억해 두어야 합니다.

3 × 3 이상에서는 여인수 전개(cofactor expansion)로 계산합니다. 행렬에서 i행과 j열을 지운 작은 행렬의 행렬식을 그 자리의 소행렬식(minor)이라 하고, 소행렬식에 부호 $(-1)^{i+j}$를 곱한 것을 여인수(cofactor) $K_{ij}$라고 합니다. 부호는 1행 1열을 +로 시작해 체스판처럼 번갈아 바뀝니다.

한 행을 골라, 그 행의 원소마다 여인수를 곱해 모두 더하면 행렬식이 됩니다. $C=\begin{pmatrix}1&2&0\\0&1&3\\2&0&1\end{pmatrix}$를 첫 행으로 전개하면 다음과 같습니다.

둘째 항을 자세히 보면, 1행 2열의 원소 2에 대해 1행과 2열을 지운 $\begin{pmatrix}0&3\\2&1\end{pmatrix}$의 행렬식이 -6이고, 부호 -를 곱한 여인수가 6이며, 원소 2와 곱해 12를 보탭니다.

크기에 상관없이 재귀로 정의하기

여인수 전개는 n × n 행렬의 행렬식을 (n - 1) × (n - 1) 행렬의 행렬식들로 나타내므로, 1 × 1에서 $\det(a)=a$로 시작하면 어떤 크기의 행렬식이든 재귀로 정의할 수 있습니다. i행과 j열을 지운 행렬을 $A^{(i\mid j)}$라 하면 다음과 같습니다.

4 × 4 행렬은 3 × 3 행렬 네 개로, 그것들은 다시 2 × 2와 1 × 1로 줄어듭니다. 이 정의는 재귀 함수로 그대로 옮길 수 있습니다.

def minor(m, i, j):
    return [row[:j] + row[j + 1:] for k, row in enumerate(m) if k != i]


def det(m):
    if len(m) == 1:
        return m[0][0]
    return sum((-1) ** j * m[0][j] * det(minor(m, 0, j)) for j in range(len(m)))


C = [[1, 2, 0], [0, 1, 3], [2, 0, 1]]
print(det([[1, 2], [3, 4]]), det(C), det([[2, 1], [4, 2]]))
print(det([[2, 0, 1, 3], [1, 1, 0, 2], [0, 3, 1, 1], [4, 0, 2, 1]]))

-2 13 0
-25

minor는 i행을 빼고, 남은 행마다 j번째 원소를 잘라 낸 행렬을 만듭니다. 코드의 행과 열 번호는 0부터 시작하므로 부호가 $(-1)^{j}$입니다. 첫 행으로 전개하는 이 방법은 이해하기 쉽지만, n × n 행렬에서 호출이 n!에 가깝게 늘어나 큰 행렬에는 쓸 수 없습니다. 큰 행렬의 행렬식은 다음 글의 소거법으로 계산합니다.

첫 행이 아닌 다른 행이나 열로 전개해도 같은 값이 나온다는 것이 알려져 있습니다. 행렬식은 행 연산에 대해 다음과 같이 변합니다. 두 행을 맞바꾸면 부호가 바뀌고, 한 행에 c를 곱하면 행렬식도 c배가 되며, 한 행에 다른 행의 배수를 더하면 값이 그대로입니다. 그래서 같은 행이 둘 있는 행렬은 그 두 행을 맞바꾸어도 행렬이 그대로인데 부호는 바뀌어야 하므로 행렬식이 0입니다. 이 성질들의 일반적인 증명은 이 교재의 범위를 넘으므로 여기서는 결과만 쓰겠습니다.

정리

• m × n 행렬의 덧셈은 같은 크기끼리 같은 자리를 더하고, 전치는 행과 열을 맞바꿉니다.
• 곱 AB는 A의 열 수와 B의 행 수가 같을 때 정의되며, i행 j열은 $\sum_k a_{ik}b_{kj}$입니다. AB와 BA는 일반적으로 다릅니다.
• 행들의 선형결합이 0이 되는 계수가 모두 0뿐이면 선형 독립, 그렇지 않으면 선형 종속입니다.
• 행렬식은 정사각행렬에 대응하는 수이고, 2 × 2에서는 $ad-bc$, 그 이상에서는 소행렬식에 부호를 곱한 여인수로 전개합니다.
• 실수 정사각행렬은 행렬식이 0일 때 행들이 종속이고 역행렬이 없으며, 여인수 전개는 재귀로 정의되지만 큰 행렬에는 느립니다.

연습 문제

1. 곱할 수 있는 크기

A가 2 × 3 행렬, B가 3 × 4 행렬일 때 AB와 BA를 계산할 수 있는지, 있다면 크기가 무엇인지 쓰세요.

2. 행렬식이 0인 행렬

$D=\begin{pmatrix}2&1\\4&2\end{pmatrix}$의 행렬식을 구하고, 두 행의 관계를 선형 종속의 정의로 설명하세요.

3. 다른 행으로 전개하기

본문의 C를 첫 행 대신 셋째 행으로 전개해 행렬식을 구하고, 첫 행으로 구한 13과 같은지 확인하세요.

곱셈이 헷갈리면 결과의 한 칸만 골라 행과 열을 짝지어 계산해 보세요. 다음 글 역행렬과 연립일차방정식에서는 행렬식이 0이 아닌 행렬의 역행렬을 두 가지 방법으로 구합니다.