Lecture 3. (행렬) 곱셈과 역행렬 (Multiplication and inverse matrices)

다음은 Gilbert Strang의 선형대수학 MIT 강의를 듣고 정리한 글이다. 강의 링크

행렬 곱셈 (Matrix Multiplication)

이번 과정에서는 행렬을 곱셈하는 방법 5가지를 배워볼 것이다.
아래의 모든 예시는 다음 행렬 곱셈을 기반으로 설명된다.
$$
AB = C\rightarrow
\begin{bmatrix}
a_{00} & \cdots & a_{0n} \\
\vdots & \ddots & \vdots \\
a_{m0} & \cdots & a_{mn}
\end{bmatrix}
\begin{bmatrix}
b_{00} & \cdots & b_{0p} \\
\vdots & \ddots & \vdots \\
b_{n0} & \cdots & b_{np}
\end{bmatrix} =
\begin{bmatrix}
c_{00} & \cdots & c_{0p} \\
\vdots & \ddots & \vdots \\
c_{m0} & \cdots & c_{mp}
\end{bmatrix} \\
A\text{ is m by n matrix, }B\text{ is n by p matrix}
$$

1st Way. 일반적인 행렬 곱셈 The standard rule

가장 일반적인 행렬 곱셈은 A의 행과 B의 열을 곱해 C의 값을 구하는 것이다.
$$
c_{ij} = a_{i0}*b_{0j} + a_{i1}*b_{1j} + ... + a_{in}*b_{nj} = \sum_{k=0}^n a_{ik}*b_{kj}
$$

2nd Way. 행을 사용하는 방법 the row way

행렬의 곱셈을 행 또는 열 단위로 넓게 바라볼 수도 있다. 앞 장에서 설명했듯이, 모든 행렬의 곱은 행 벡터의 조합(Combination) 또는 열 벡터의 조합으로 나타낼 수 있다. 따라서 행 벡터를 사용하여 계산한다면 다음과 같을 것이다.

$$
\begin{align}
C_{j} = &\text{the j th of rows of C} \\
C_{j} = &A_j * B = \begin{bmatrix} a_{j0} &a_{j1} & \cdots & a_{jn}\end{bmatrix}
\begin{bmatrix}
b_{00} & \cdots & b_{0p} \\
\vdots & \ddots & \vdots \\
b_{n0} & \cdots & b_{np}
\end{bmatrix}\\
&=a_{j0} * \begin{bmatrix} b_{00} & b_{01} & \cdots & b_{0p}\end{bmatrix}
\\ &+ a_{j1} * \begin{bmatrix} b_{10} & b_{11} & \cdots & b_{1p}\end{bmatrix}
\\ &+ ...
\\ &+ a_{jn} * \begin{bmatrix} b_{n0} & b_{n1} & \cdots & b_{np}\end{bmatrix}
\end{align}
$$

3rd Way. 열을 사용하는 방법 the column way

$$
C_{j} = \text{the j th of columns of C} \\
C_{j} = A * B_j =
\begin{bmatrix}
a_{00} & \cdots & a_{0n} \\
\vdots & \ddots & \vdots \\
a_{m0} & \cdots & a_{mn}
\end{bmatrix}
\begin{bmatrix} b_{0j} \\ b_{1j} \\ \vdots \\ b_{nj}\end{bmatrix}
=b_{0j} * \begin{bmatrix} a_{00} \\ a_{10}\\ \vdots \\ a_{m0}\end{bmatrix} +
b_{1j} * \begin{bmatrix} a_{01} \\ a_{11}\\ \vdots \\ a_{m1}\end{bmatrix} + ... +
b_{nj} * \begin{bmatrix} a_{0n} \\ a_{1n}\\ \vdots \\ a_{mn}\end{bmatrix}
$$

요약
A 첫번째 행 * B = C의 첫번째 행
A * B의 첫번째 열 = C의 첫번째 열

4th Way. column times row

지금까지 해왔던 방법과 다르게 진행해보자. A의 열과 B의 행을 곱한다면 어떻게 될까?
$$
\text{the column of A }*\text{ the row of B } = \text{m by p matrix}
$$
Full size matrix를 갖게 된다! 이 행렬의 특이한 점은 열 벡터들이 한 직선상에 존재하고, 행 벡터도 서로 한 직선상에 존재하게 된다는 것이다. 예시는 다음과 같다.
$$
\begin{bmatrix} 2 \\ 3 \\ 4\end{bmatrix} * \begin{bmatrix} 1 & 6\end{bmatrix} = \begin{bmatrix} 2 & 12\\ 3 & 18\\ 4 & 24\end{bmatrix}
$$

그리고 AB(=C)는 다음과 같이 표현할 수 있다.
$$
C = \sum_{j=0}^n \text{ (the } j\text{th column of A)} * \text{(the } j\text{th row of B)}
$$

5th Way. Block Multiplication

어떤 행렬 A, B의 곱을 계산할 때, A와 B를 블록 단위로 나눠서 계산할 수 있다. 예를 들어 행렬을 다음과 같이 나눌 수 있다. 나눌 때 서로 행렬의 크기가 같을 필요는 없으며, 계산 시에 서로 계산이 가능한 관계기만 하면 된다.

 

이 경우에 A*B에 대한 계산은 다음과 같다. (일반적인 행렬 곱셈과 같음)

$$
AB = C \rightarrow
\begin{bmatrix}
A_1 & A_2 \\ A_3 & A_4
\end{bmatrix}
\begin{bmatrix}
B_1 & B_2 \\ B_3 & B_4
\end{bmatrix} =
\begin{bmatrix}
A_1*B_1 + A_2*B_3 & A_1*B_2 + A_2*B_4 \\ A_3*B_1 + A_4*B_3 & A_3*B_2 + A_4*B_4
\end{bmatrix}
$$

모든 방법이 서로 다르게 느껴질 수 있으나, 세밀히 들어가면 동일한 방식으로 작동한다.

역행렬

어떤 정방행렬 A가 주어졌을 때, A는 역행렬을 가지고 있을 수도, 그렇지 않을 수도 있다. (정방행렬이 아니면, 역행렬도 없다.) 만약 A가 역행렬을 가진다면 A를 A is invertible 또는 A is non-singular라고 표현한다. 역행렬은 해당 행렬에 역행렬을 곱하면 단위 행렬(Identity Matrix)가 된다는 중요한 성질을 가지고 있다.

역행렬을 구하는 방법을 알기 전에, 행렬 A가 주어졌을 때 A가 역행렬을 가지고 있는가? 를 먼저 알 수 있는 방법이 있을까?
방법은 다양하게 존재한다.
(방법 1) 행렬식(Determinant)의 개념을 안다면 행렬식을 계산하여 값이 0일 때 역행렬이 존재하지 않음을 알 수 있다.

(방법 2) 다른 접근은 우리가 지금까지 유용하게 사용해왔던 column의 관점으로 확인하는 것이다. (row도 역시 가능하다.) 만약 A가 singular matrix일 때(즉, A가 역행렬을 가지지 않을 때), A의 역행렬이 존재한다고 가정하자.
$$
A=\begin{bmatrix}
1 & 3 \\ 2 & 6
\end{bmatrix} \text{, } \exists \text{ a matrix }A^{-1} \text{ such that }AA^{-1} = I \\
\rightarrow \exists \text{ a real number }a,b \text{ such that }a *\begin{bmatrix}1 \\ 2\end{bmatrix} + b *\begin{bmatrix}3 \\ 6\end{bmatrix} = \begin{bmatrix}1 \\ 0\end{bmatrix}
$$
그러나 위 조건은 충족될 수 없다. 왜냐하면 열 벡터 [1, 2]와 [3, 6]은 벡터공간 상 동일한 직선위에 놓여있기 때문이다. 따라서 모순이 생기므로 행렬 A는 역행렬이 존재하지 않는다.

(방법 3) 이외에도 아래의 조건으로 증명이 가능하다.
$$
\text{If a matrix has no Inverse, then I can find a vector }x \text{ that } Ax = 0 \text{ (} x \text{ is not zero vector)}
$$
A가 singular matrix인 상황에서 A의 역행렬이 존재한다고 가정하고 예시를 들어보면,
$$
A=\begin{bmatrix}1 & 3 \\ 2 & 6\end{bmatrix}, x=\begin{bmatrix}3 \\ -1\end{bmatrix} \rightarrow Ax=0 \\
Ax=0\rightarrow A^{-1}Ax=0\rightarrow Ix=0\rightarrow x=0
$$
위와 같이 x의 초기 설정값과 모순된다. 따라서, A는 역행렬이 없음을 증명할 수 있다.

Gauss-Jordan 소거법 (Gauss-Jordan Elimination)

이제, A의 역행렬을 구하는 방법을 알아볼 것이다.
예시를 다음과 같이 들어보겠다.
$$
A=\begin{bmatrix}1 & 3 \\ 2 & 7\end{bmatrix}, A^{-1}=\begin{bmatrix}a & b \\ c & d\end{bmatrix} \rightarrow AA^{-1}=I \\
$$
이 때, A의 역행렬을 구하는 것은 두 개의 equation system을 푸는 것과 다름없다.
$$
\begin{cases}
a*\begin{bmatrix}1\\ 2\end{bmatrix} + c*\begin{bmatrix}3 \\ 7\end{bmatrix} = \begin{bmatrix}1 \\ 0 \end{bmatrix} \\
b*\begin{bmatrix}1\\ 2\end{bmatrix} + d*\begin{bmatrix}3 \\ 7\end{bmatrix} = \begin{bmatrix}0 \\ 1 \end{bmatrix}
\end{cases}
$$
이 두 개의 equation system을 이전에 배웠던 Gauss Elimination과 유사하게 풀 수 있다. 그리고 여기에 Jordan의 아이디어가 추가된다. Jordan의 아이디어란 바로, 이 두개 (또는 그 이상)의 system을 한번에 풀 수 있게 하는 것이다!
Gauss-Jordan 소거법의 순서는 다음과 같다.

1. 주어진 수식을 확장행렬로 표현한다.
   $$
   \left[
   \begin{array}{c|c}
   A & I
   \end{array}
   \right] =
   \left[
   \begin{array}{cc|cc}
   1 & 3 & 1 & 0\\
   2 & 7 & 0 & 1\\
   \end{array}
   \right]
   $$
2. Gauss 소거법과 같이 전진 소거법(straightforward elimination)을 진행한다. (= 상삼각행렬(Upper Triangular Matrix)를 만든다.)
   $$
   \left[
   \begin{array}{cc|cc}
   1 & 3 & 1 & 0\\
   2 & 7 & 0 & 1\\
   \end{array}
   \right] =
   \left[
   \begin{array}{cc|cc}
   1 & 3 & 1 & 0\\
   0 & 1 & -2 & 1\\
   \end{array}
   \right]
   $$
3. 반대 방향(위 방향)으로도 소거법을 진행한다.
   $$
   \left[
   \begin{array}{cc|cc}
   1 & 3 & 1 & 0\\
   0 & 1 & -2 & 1\\
   \end{array}
   \right] = \left[
   \begin{array}{cc|cc}
   1 & 0 & 7 & -3\\
   0 & 1 & -2 & 1\\
   \end{array}
   \right] = \left[
   \begin{array}{c|c}
   I & A^{-1}
   \end{array}
   \right]
   $$

그럼 여기서 의문이 드는 점은, 왜 해당 단계들을 따라가면 역행렬이 나오는가?

우리는 소거 행렬(Elimination Matrix) 을 상기시킬 필요가 있다. 이전 시간에서 전진 소거법을 진행하는 각각의 단계들을 행렬의 곱셈으로 표현할 수 있었고, 원 행렬에 곱해지는 행렬을 소거 행렬이라고 불렀다. 그렇다면 위 단계들(2번, 3번) 에서 진행하는 소거법 역시 A에 소거행렬을 곱하는 표현으로 나타낼 수 있다.
$$
E_{21}(E_{12}A) = I
$$
이를 일반적으로 표현하면
$$
EA = I
$$
이고, 우리는 A에 행렬을 곱함으로써 단위 행렬이 만들어지면 그 곱한 행렬을 역행렬이라 부른다.