57. Matrices

이번 글에서는 선형대수학(Linear Algebra)에 대한 내용을 다룬다. 선형대수학은 덧셈과 곱셈을 통한 변화에 초점을 두는 수학의 한 분야이며, 적절한 표현을 이용하여 선형방정식의 해를 구하는 것을 핵심으로 하고 있다.

 

선형대수학에서 중요하게 다뤄지는 개념으로 행렬(Matrices)과 벡터(Vectors)가 존재하는데, 벡터에 관한 자세한 내용은 카테고리 G에서 다루고 여기서는 행렬에 관한 내용 위주로 다루기로 한다.

 

행렬은 수나 식을 직사각형 모양으로 배열한 것으로 행(Row, 가로줄)의 수가 $n$, 열(Column, 세로줄)의 수가 $m$인 경우 $n \times m$ 행렬이라고 한다. 또한 각각의 수나 식을 행렬의 성분(Entry)이라고 하고, 각각의 행을 행벡터(Row Vector), 각각의 열을 열벡터(Column Vector)라고도 한다.

 

행렬은 일반적으로 알파벳 대문자와 대괄호를 써서 다음과 같이 표시한다. 드물게 대괄호 대신 소괄호를 사용하는 경우도 있다.

 

$$A = \begin{bmatrix} a_{1,1} & \cdots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,m} \end{bmatrix}$$

 

어떤 행렬이 같은 수의 행과 열을 갖는 경우 그 행렬을 정사각행렬(Square Matrix)이라고 한다. 또한 $i$번째 행의 $i$번째 열을 행렬의 주대각선(Main Diagonal)이라고 하고, 행렬의 주대각선에 위치한 성분은 모두 $1$이고 나머지 성분은 모두 $0$인 정사각행렬을 단위행렬(Unit Matrix)이라고 한다. 단위행렬은 보통 기호 $I$로 나타낸다.

---

행렬의 기본적인 연산에는 덧셈과 곱셈이 있다. (뺄셈은 단순히 덧셈의 반대로 진행하면 되지만 행렬 연산에서는 그렇게 큰 의미를 두지 않으며, 나눗셈은 직접적으로 정의되어 있지 않다.) 두 행렬 $A, B$의 크기가 각각 $n_1 \times m_1, n_2 \times m_2$일 때 행렬의 덧셈, 곱셈이 가능할 조건은 다음과 같다.

• $n_1 = n_2, m_1 = m_2$일 경우 두 행렬을 더할 수 있다.
• $n_2 = m_1$일 경우 두 행렬을 곱할 수 있다. 곱한 행렬의 크기는 $n_1 \times m_2$가 된다.

행렬의 덧셈과 곱셈은 다음과 같이 정의한다.

• 행렬의 덧셈: $C_{i,j} = A_{i,j} + B_{i,j}$
• 행렬의 곱셈: $C_{i,j} = \sum_{k=1}^{n_2} A_{i,k}B_{k,j}$

행렬의 덧셈은 직관적으로 이해할 수 있다. 행렬의 곱셈은 앞 행렬의 행벡터와 뒤 행렬의 열벡터를 곱하는 방식으로 이루어진다. 이러한 이유로 행렬의 곱셈에서는 교환법칙이 성립하지 않는다. (순서를 바꾸면 아예 곱할 수가 없는 경우도 많다.)

 

구현은 다음과 같다. 행렬의 곱셈 코드에서 $c$ 배열은 모두 $0$으로 초기화되어 있다고 가정한다. 그렇지 않다면 초기화를 먼저 해 주어야 한다.

============================================================

# Addition

for(int i = 1; i <= n1; i++)
{
   for(int j = 1; j <= m1; j++)c[i][j] = a[i][j] + b[i][j];
}

============================================================

# Multiplication

for(int i = 1; i <= n1; i++)
{
   for(int j = 1; j <= m2; j++)
   {
      for(int k = 1; k <= n2; k++)c[i][j] += a[i][k] * b[k][j];
   }
}

============================================================

시간복잡도를 확인하면 행렬의 덧셈은 $\Theta(n_1m_1)$, 행렬의 곱셈은 $\Theta(n_1n_2m_2)$이다. 단순화하면 행렬 덧셈의 시간복잡도는 $\Theta(n^2)$, 행렬 곱셈의 시간복잡도는 $\Theta(n^3)$이라고 할 수 있다. 더 빠르게 행렬을 곱할 수 있는 방법도 존재하고, 이후에 한 가지 방법을 소개할 예정이지만 일반적으로 위에 나온 기본적인 곱셈만 알고 있어도 대부분의 문제를 푸는 데에는 지장이 없다.

---

정사각행렬의 경우 행렬의 거듭제곱을 정의할 수 있다. 정의는 일반적인 거듭제곱과 크게 다르지 않다. $A^0 = I, A^k = A \times A^{k-1}$이다. $(k \ge 1)$ 또한 행렬의 거듭제곱을 구할 때는 곱셈의 교환법칙이 성립한다.

 

행렬의 거듭제곱을 빠르게 구하기 위해서는 빠른 거듭제곱을 행렬의 곱셈에 그대로 적용하면 된다.

 

[연습문제]

 

BOJ 10830. 행렬 제곱 (Gold IV)

행렬의 거듭제곱을 빠르게 구하면 된다. 중간 과정에서 계속해서 각각의 원소들을 $1000$으로 나눈 나머지를 구해 주어야 한다.

 

→ solved.ac tag: linear_algebra