Learn Again! 러너게인

이번 포스팅에서는 지난 Lecture 18에 이어 determinant에 대한 포스팅을 하려고한다. 지난 시간에는 determinant에 대한 10가지 특성을 배웠다면, 이번 시간에는 determinant의 실제 계산 방법에 대해 다룰 것이다. 이번 강의의 목적은 determinant의 계산 공식을 이해하는 것이다. 설명하는 과정에서 Lecture 18에서 배웠던 특성들을 많이 언급하므로 이번 강의를 보기 전에 지난 강의를 먼저 보고 오기를 추천한다. 

1. 행렬식의 계산 방법과 공식(Determinant Formulas)

- Determinant split

지난 시간에 우리는 determinant의 세 가지 주요 특성들에 대해 배웠다. 이를 기반으로 나머지 7개의 특성을 정의할 수 있었고, 총 10개의 determinant의 특성들에 대해 정리하였다. 이 중 가장 중요한 처음 세 가지 특성들을 2x2 행렬을 통해 다시금 정리해보자. determinant의 계산 공식을 유도하기 위해서 말이다. 

prop. (1)은 단위 행렬의 determinant가 1임을 나타내었다. 또한 prop. (2)는 행 교환(row exchange)을 했을 때, 부호가 바뀌는 것을 의미한다. 이때 row exchange의 횟수가 홀수번(odd)이면 -1, 짝수번(even)이면 부호는 그대로이다. 

prop. (3)는 (3)-1과 (3)-2로 나누어져 있는데, (3)-1은 하나의 row에 곱해진 scale상수를 밖으로 뺄 수 있다는 것이었고, (3)-2는 하나의 row에 대해서 나머지 row는 그대로 유지한 채 분리해서 정리할 수 있다는 것이었다. 여기서는 (3)-2에 대해서 다시 정리해보자. 

지난 강의에서는 row 1에 [a' b']이 더해진 것을 가정하고 [a b]와 [a' b']에 대한 determinant로 각각 나누어서 정리하였다. 그러나 이번엔 row2는 그대로 유지한 채, 기존의 [a b]를 [a 0]와 [b 0]에 대해서 나누어 정리하였다. 이렇게 나누어 정리해도 determinant는 같음을 알 수 있다. 식 (2)의 우변은 row1을 분리하여 정리한 것인데, 여기서 row2를 기준으로 한 번 더 분리하여 정리해보자. 우선 첫 번째 determinant식의 row1=[a 0]를 그대로 유지한 채 row2=[c d]를 분리하여 정리하고, 마찬가지로 최 우측의 row1=[0 b]을 유지한 채 row2를 분리하여 정리하면 아래 식과 같다. 

이렇게 하여 prop. (3)을 이용하여 행렬식을 분리하여 정리하였다. 이렇게 분리하니 식이 많아지긴 했지만 각각의 계산은 굉장히 간단하다. 아래쪽의 첫 번째와 네 번째 식은 모든 원소가 0인 column vector가 존재하므로 prop. (6)에 의해 determinant가 0이 된다. 즉 pivot이 0인 특이 행렬(singular matrix)이기 때문이다. 

두 번째는 대각 행렬(diagonal matrix)이므로 대각 원소들을 그냥 곱하면 된다. 따라서 determinant는 ad가 된다. 세 번째 determinant는 대각 행렬이 뒤집힌 상태이다. 따라서 prop. (2)를 이용하여 row exchange를 하면 일반적인 대각 행렬이 되고, 부호는 -1을 곱해준다. 이 상태에서 prop. (3)-1을 이용하여 각 row에 곱해진 c와 d를 차례로 밖으로 빼내면 결과적으로 ad-bc가 된다. 아래 식은 식 (3)의 아래 에서 두 번째와 세 번째 determinant를 풀어서 계산한 식을 나타낸다. 

우리는 최초의 2x2 determinant를 지난 시간에 배운 determinant의 특성들을 이용하여 분리하여 계산하였다. 분리하는 과정은 약간 번거로울 수 있지만, 분리한 뒤의 determinant를 계산하는 것은 매우 쉬운일이다. 그런데 왜 우리가 고작 2x2행렬의 determinant를 구하는데 이렇게 애를 쓸까? 그냥 ad-bc를 하면 될텐데. 

우리의 목적은 단순이 2x2행렬의 determinant를 구하는 것이 아니다. 3x3, 4x4, 나아가 n x n행렬의 determinant를 구하는 방법을 알아내는 것이 목적이다. 

우리는 2x2행렬을 분리한 결과, 처음에 row1을 각 원소에 대해 쪼개어 두 개의 행렬식을 만들었다. 식 (2)와 같이 말이다. 그 다음은 식 (3)과 같이 row2에 대해서 쪼개어 식을 네 개로 만들었다. 그렇다면 위의 방법을 3x3행렬에 적용하면 어떻게 될까? 3x3의 행렬을 쪼갠다면 다음과 같은 시나리오가 될 것이다. 

먼저 row2, row3는 그대로 유지한 채 row1=[a b c]에 대해서 쪼개면 식 (5.1)과 같이 3개의 행렬식이 나온다. 이 쪼갠 행렬의 각각에 대해서 이번엔 row2를 기준으로 쪼갤 수 있다. 식(5.1)의 첫 번째 행렬식을 row2에 대해 쪼갠 것이 식 (5.2)에 나타난 3개의 행렬식이다. 이렇게 하면 식 (5.2) 단계에서는 총 9개의 행렬식이 나온다. 이제 마지막으로 식 (5.2)단계에 있는 행렬식들을 나머지 row는 유지한 채 row3=[g h i]를 기준으로 쪼개면 역시 각 행렬식 당 세 개의 행렬식이 식 (5.3)과 같이 나오게 된다. 결국 3x3행렬식을 각 row에 따라 쪼개면 총 27개의 행렬식이 나오게된다. 행렬식 분리가 완료되면 대부분의 행렬식(determinant)들은 column의 원소가 모두 0이기 때문에 0이 되고 남은 행렬식들을 이용하여 간단히 행렬식을 계산할 수 있다. 

4x4를 쪼개면 총 몇 개의 행렬식으로 분리할 수 있을까? 바로 n의 n승, 즉 

이다. 3x3의 경우엔 3^3=27, 4x4의 경우엔 4^4=256개의 행렬식으로 쪼갤 수 있다. 물론 실제 determinant를 계산할 때 이렇게 일일이 쪼개서 하라는 것이 아니다. determinant의 계산 과정의 개념적 설명을 하기 위한 과정이다. 

식 (5)에서 3x3행렬의 determinant를 분리할 때, 마지막 세 번째 단계에서 총 27개의 determinant를 구하였고, 대부분의 determinant는 0이었다. 그런데 0이 되는 것들은 중요하지 않고, 0이 아닌 것들이 중요하다. 그렇다면 언제 determinant가 0이 아니게 될까? 

식 (3)의 마지막 줄을 보면 첫 번째와 네 번째 determinant는 0이 되고 두 번째와 세 번째 determinant만 살아남았다. 이 둘은 공통점이 있는데 무엇일까? 바로 살아남은 각 원소들이 row와 column에 오직 자기 자신만이 존재하는 것이다. 식 (5)에서도 지면의 한계 상 27개의 determinant를 다 적지는 못했지만, 역시 0이 아닌 determinant들은 같은 특성을 보인다. 그렇다면 3x3 determinant를 기준으로 식을 분리했을 때 살아남는 것들을 적어보도록 하겠다. 

일단 식 (6)의 첫 번째 determinant를 보면 a11을 기준으로 해당 row와 column에 오직 a11밖에 없다. a22와 a33로 마찬가지로 원소 자신을 기준으로 row와 column에 오직 자기 자신밖에 없다. 27개의 determinant중에 이와 같이 원소를 중심으로 row와 column에 오직 자신만 존재하는 determinant만 0이 아니게되고 살아남게 된다. 

첫 번째 determinant는 대각 행렬(diagonal matrix)이므로 대각 원소를 그냥 곱해주면 된다. 두 번째를 보자. a11은 그대로이고 아래에 a23과 a32가 존재한다. 이는 마치 치환 행렬(permutation matrix)과 같은 형태인데, 대각 행렬의 형태로 만들어주기 위해선 row exchange를 해야 한다. 즉 row2와 row3을 교환해주면 대각행렬이 만들어진다. determinant위에 R.E 2,3이 Row Exchange 2, 3을 의미하는 것이며, 지난 시간에 배운 prop. (2)를 통해 부호가 바뀌게 된다. 행 교환을 한 다음 prop. (3)-1을 통해 원소들을 밖으로 빼주면 -a11*a23*a32가 된다. 

이번엔 네 번째 determinant를 보자. 네 번째도 대각 행렬 형태가 아니므로 행 교환을 해야하는데, 이번엔 두 번의 행 교환이 필요하다. 먼저 row1과 row3을, 그 다음엔 row2와 row3을 교환해주면 대각행렬이 만들어지는데, 이때 행 교환을 두 번 했기 때문에 부호는 그대로 +가 된다. 나머지도 같은 방법으로 행 교환을 통해 정리해주면 최종적으로 식 (6)과 같이 6개의 행렬식에 대한 식이 만들어진다. 

이렇게 하여 3x3크기의 행렬에 대한 determinant식을 완성하였다. 그런데 이 식을 유도하는 방식을 과연 nxn크기의 determinant를 구하는 일반적인 공식(General formula)처럼 사용할 수 있을까? 정답은 No다. 식 (6)의 첫 번째와 여섯 번째 행렬식(determinant)을 보면 첫 번째 행렬식의 부호는 대각 원소들을 그대로 곱해주면 된다. 그러나 여섯 번째 행렬식은 행 교환(row exchange)을 해야 하고 한 번의 행 교환을 통해 부호가 -로 바뀌게 된다. 즉 대각 행렬의 행렬식의 부호는 +, 여섯 번째와 같이 반대 방향의 대각 행렬식(counter diagonal determinant)의 부호는 -가 된다. 그러나 이는 nxn크기의 행렬식에 대해서 일관성이 없다. 아래의 4x4크기의 행렬식을 보자. 

식 (7)의 counter diagonal형식의 determinant를 diagonal형태로 만들기 위해선 row1과 row4, row2와 row3의 두 번의 행 교환이 필요하다. 따라서 식 (6)의 경우와는 다르게 부호가 +가 된다. 결과적으로 식 (6)의 공식 유도 방식은 일관성이 없으며 오직 3x3크기의 determinant에만 적용될 수 있다. 만약 4x4에다 위의 방식을 적용하여 식을 만들면 각 크기의 determinant마다 서로 다른 형태의 식이 나오게 되고 식이 무한정 길어진다는 단점도 있다. 

우리가 원하는 것은 어떤 nxn 크기의 determinant에도 적용할 수 있는 일반적인 공식이다. 지금부터 임의의 크기의 determinant를 구할 수 있는 일반적인 공식에 대해 알아보도록 하자. 

- Big Formula

지금부터 배울 공식은 Big formula로 불리는 공식이며, 2x2, 3x3, 4x4, ... nxn에 모두 적용할 수 있는 determinant를 계산할 수 있는 일반적인 공식(General formula)이다. 즉 nxn크기의 행렬에 대해서 식 (6)과 같이 0이 아닌 텀들의 합으로 determinant를 계산하는 공식이다. 식 (3)에서는 2x2 determinant에 대해서 분리된 행렬식중에 0이 아닌 텀이 두 개이고, 식 (6)의 3x3에서는 총 27개 중 6개이다. 그렇다면 4x4에서는 0이 아닌 행렬식이 몇 개일까? 바로 24개이다. 이를 계산하는 법은 n!(factorial)이다. 3x3은 3!=3x2x1=6, 4x4는 4!=4x3x2x1=24가 된다. 이렇게 0이 아닌 텀을 factorial로 계산하는 이유는 다음과 같다. 

Fig. 1 3x3 determinant를 분해하는 과정

일단 앞서 언급했듯이 행렬식을 쪼갠 식 중에서 0이 아닌 살아 남는 식들은 바로 치환 행렬(permutation matrix)형태의 식이다. 즉 쪼갠 식의 각각의 원소가 자기 자신의 위치를 중심으로 row와 column에 오직 자기 자신만 존재하는 형태이다. 이와 같이 행렬식을 쪼갤 때 Fig. 1과 같이 먼저 row1의 3개의 각 원소 a11, a12, a13을 기준으로 식을 분리한다. n=3이기 때문에 a11을 기준으로 쪼갠 행렬식에서 나올 수 있는 조합은 이제 n-1=2개 이다.  Fig. 1의 두 번째 줄에서 녹색 영역을 제외한 2x2부분 행렬식에 대해서 이 2개의 경우의 수가 나온다. 이 두 가지의 조합이 바로 마지막 세 번째 줄이다. 이 세 번째 단계에서 나올 수 있는 조합은 이제 n-2=1이므로 a33과 a32를 그대로 쓰면 된다. 나머지 a12, a13도 똑같이 조합에 대한 경우의 수가 row1의 원소들을 시작으로 n-1, n-2과 같이 줄어들기 때문에 결과적으로 n!(factorial)만큼의 살아남는 행렬식들을 계산하고 더해준다. 이때 중요한 것은 절반은 부호가 +, 나머지 절반은 -의 부호를 가진다. 아래식을 보자. 

행렬 A의 determinant를 구하는데 있어서 n factorial의 수 만큼 마지막 단계까지 쪼갠 각 행렬식 계산 결과를 더해준다. 다시 한 번 말하지만 n factorial의 수는 행렬을 분해했을 때 0이 아닌 살아 남는 행렬의 수를 의미하고, 형태는 치환 행렬(permutation matrix)을 의미한다. 이 과정을 수식으로 나타낸 것이 식 (8)이다. 

여기서 alpha부터 omega는 1부터 n까지의 치환 행렬의 column index를 의미한다. 이때 alpha부터 omega의 column index들은 단 한번씩만 사용된다. 즉 식 (8)의 alpha, bete, ... omega등은 a11a22a33 - a11a23a32 - a12a21a33 + a12a23a31 + a13a21a32 - a13a22a31에서 볼드체 숫자(column index)에 해당한다. 

우리는 식 (8)을 이용하여 이전 시간에 배웠던 행렬식의 특성(Determinant properties)들을 전부 확인할 수 있다. 가령 단위 행렬의 determinant가 1인 것은 식 (8)을 이용하여 Fig. 1과 같이 전개해보면 결과값이 1인 것은 오직 첫 번째 텀이다. 따라서 단위 행렬이 1인 것을 식 (8)을 통해 확인할 수 있다. 이와 같이 prop. (1) ~ (10)까지의 모든 특성들도 식 (8)을 통해 확인할 수 있다. 

- Example of Big Formula

이제 실제 행렬의 determinant를 Big formula인 식 (8)을 이용하여 풀어보도록 하자. 아래의 4x4의 determinant를 어떻게 푸는지 그 과정을 잘 살펴보도록 하자. 

식 (10)은 4x4크기의 행렬의 determinant이다. n=4이기 때문에 행렬식(determinant)을 쪼갤 수 있는 총 가짓수는 4의 4승(4^4)이므로 4x4x4x4=256가지의 행렬식으로 분해할 수 있다. 그러나 이 중 0이 아닌 살아남는 행렬식(Permutation matrix type)은 4!=4x3x2x1=24개이다. 그러나 식 (10)의 많은 원소들이 0을 포함하고 있기 때문에 이 24개 중에서도 대부분의 행렬식이 0이 된다. 따라서 계산을 효율적으로 하기 위해 0이 아닌 원소들을 치환 행렬의 조건에 맞게 순차적으로 선택하여 행렬식을 계산해 보도록 하자. 아래 그림을 보자. 

Fig. 2 Big Formula를 이용한 4x4 determinant의 계산

Fig. 2는 식 (8)에 나타난 Big Formula를 이용하여 4x4 행렬의 determinant를 구하는 모습이다. step1-1을 보면 먼저 원소 중에 0이 아닌 원소를 하나 고른다. 맨 처음 고른 원소는 a14의 위치에 있는 원소를 골랐으며, 이 원소를 중심으로 row와 column의 원소들은 다음 step에서 고를 수 없다. 즉 step1-2에서 원소를 고를 때는 step1-1의 흰색 영역에 있는 원소들 중에 0이 아닌 원소들을 골라야 한다. step1-2에서는 a23의 위치에 있는 원소를 골랐다. 역시 step1-3에서는 step1-2의 흰색 영역의 원소들 중에 골라야 하며 a32를 골랐다. 마지막 step1-4에서는 딱 하나 남은 원소인 a41의 위치의 원소를 고른 모습이다. 

이렇게 하여 step1-4에서 반대방향 대각선의 원소들을 골랐으며, perm(4,3,2,1)로 표기를 하였다. 여기서 괄호 안의 숫자들은 column의 index를 의미한다. 즉 (4,3,2,1)은 순서대로 row1의 column index가 4, row2의 column index가 3, row3의 column index가 2, row4의 column index가 1임을 각각 의미한다. 결과적으로 치환 행렬(permutation matrix)형태의 행렬이 만들어진 것이다. perm(4,3,2,1)의 치환 행렬을 대각 행렬(diagonal matrix)의 형태로 만들기 위해선 두 번의 행 교환(row exchange)이 필요하다. 4와 1, 그리고 2와 3을 교환 하면 대각 행렬이 만들어진다. 따라서 prop. (2)에 따라 부호는 원래대로 +이며, prop. (7)에 따라 대각 원소들끼리 곱해주면 결과적으로 1이 나온다. 

두 번째로 step2-1 ~ step2-4의 단계도 역시 같은 방법으로 이전 단계의 흰 영역중 0이 아닌 원소들을 선택하는 방법으로 Big Formula를 적용하면 perm(3,2,1,4)가 나온다. 여기 까지 하고 나면 행렬식의 모든 원소에 대해서 처리를 했기 때문에 그 이상의 과정은 필요없다. 원래는 4x4의 경우 24개의 텀에 대하여 모두 계산해야 하지만, 이 예제에선 나머지 원소들이 0이기 때문에 하나의 원소라도 0이면 determinant가 0이 되기 때문에 더 이상 진행할 필요가 없는 것이다. 결국 step2-4를 통해 구한 perm(3,2,1,4)의 경우, 3과 1의 한 번의 row exchange만 하면 대각 행렬이 되기 때문에 부호는 -가 되고 결과는 -1이 된다. step1과 step2에서 구한 행렬식의 값들을 더하면 결과적으로 det A는 0이 된다. 결국 Fig. 2의 행렬식은 determinant가 0이기 때문에 특이 행렬(singular matrix)이다. 특이 행렬이기 때문에 row의 선형 결합(Linear combination)이 0이 된다. (row1+row3) - (row2+row4) = 0. column의 경우도 마찬가지이며, 특이 행렬이기 때문에 column의 선형 조합을 통해 영벡터(zero vector)를 만들 수 있는 null space가 존재한다. 

이번 섹션에서 다루었던 Big Formula의 내용을 잘 이해하고, 이를 기반으로 다음 섹션에서 여인수(Cofactor)에 대해 공부해보도록 하자.  

2. 여인수(Cofactor)

여인수(cofactor)는 이전 섹션에서 배웠던 식 (8)의 Big formula를 분할하는 방법이다. 즉 nxn의 determinant를 이보다 한 단계 작은 크기인 (n-1)x(n-1)의 determinant와 연결시키는 방법이다. 이를 여인수 전개(cofactor expansion)라 한다. 식 (8)의 Big Formula는 식 (6)과 같이 determinant의 모든 식을 나열하는 방식이다. Big Formula를 이용하여 구했던 식 (6)의 3x3 determinant를 cofactor를 이용하여 계산해보자. 아래 그림을 보자. 

Fig. 3 cofactor를 이용한 determinant의 계산

Fig. 3은 기존의 Big Formula를 이용하여 계산한 determinant를 cofactor를 이용하여 계산한 것이다. row1의 첫 번째 원소 a11을 선택하고 나머지 2x2공간(흰 부분)에 대한 모든 경우를 계산하여 a11에 곱해준다. 이때 최초에 선택한 a11을 factor, 나머지 2x2의 모든 경우에 대한 계산이 괄호안에 있는 (a22a33 - a23a32)이며 이를 여인수(cofactor)라고 한다. cofactor라는 말은 factor에 "공동", "협동"이라는 뜻을 지닌 접두사 co가 붙어서 factor와 공존하는 cofactor라는 뜻이 된다. 두 번째 파란 줄로 표시된 cofactor는 a12앞의 부호를 +로 만들기 위해 순서를 바꾸어 더해준 것이다. 

그렇다면 cofactor를 단순히 factor를 중심으로 식을 묶어준 것이 지나지 않는 것일까? 단순히 그렇지는 않다. 아래 그림을 보자. 

Fig. 4 nxn과 (n-1)x(n-1)의 determinant 사이의 연결고리 역할을 하는 여인수(cofactor)

cofactor는 앞서 언급했듯이 nxn의 determinant와 (n-1)x(n-1)의 determinant의 연결고리다. 3x3의 determinant의 한 factor인 a11은 이보다 한 단계 작은 2x2의 determinant와 곱해지는데, 여기서 2x2 determinant가 바로 여인수(cofactor)이다. 이는 처음에 factor를 선택하고나면 factor가 있는 row와 column은 다른 원소를 사용할 수 없기 때문에 치환 행렬(permutation matrix)의 형태를 만들기 위해서는 이보다 한 단계 작은 (n-1)크기의 determinant를 고려해야 한다. 결국 (n-1)x(n-1)의 determinant인 cofactor는 nxn의 determinant를 계산하기 위한 각 factor와 관련된 모든 가능한 치환 행렬의 부분 조합이라고 할 수 있다. 

지금까지 우리가 예를 들 때 factor를 항상 row1에서 선택했는데, 사실 반드시 row1에서 선택할 필요는 없다. factor는 어떤 row에서 선택해도 무방하지만 계산하기가 편리하기 때문에 row1에서 선택한 것이다. 

아무튼 이러한 cofactor를 일반적인 식으로 정의해보면 다음과 같다. 

factor aij의 cofactor Cij는 factor aij의 i번째 row와 j번째 column을 제외한 나머지 n-1크기의 행렬에 대한 determinant를 의미한다. 여기서 한 가지 법칙이 존재하는데, cofactor는 i와 j인덱스에 따라 부호가 결정되는데, 바로 i+j가 짝수(even number)이면 부호는 +를, 홀수(odd number)이면 -부호를 가진다. 이 cofactor에 대한 공식은 아래와 같이 쓸 수 있다. 

식 (12.1)은 row1에 대한 cofactor공식이며, row의 index는 어떤 것이라도 가능하다. 식 (12.2)는 cofactor의 부호를 나타낸다. cofactor의 i와 j의 index의 합이 짝수냐, 홀수냐에 따라 부호가 마치 체스보드처럼 교차하여 나타나는 것을 볼 수 있다. 

아래의 식 (13)은 cofactor 공식을 이용하여 2x2행렬의 determinant를 구한것이다. 아래와 같이 ad+b(-c)가 나올 것이다. 

a11의 cofactor C11은 +d가 되고, C12는 i+j=1+2=3(odd)이기 때문에 -c가 된다. 이와 같이 3x3, 4x4, nxn의 determinant에 대해서도 cofactor를 이용하여 계산할 수 있다. cofactor를 이용한 4x4행렬의 determinant계산을 끝으로 이번 챕터를 마무리 하도록 하자. 

위의 식 (14)는 식(10)에서 Big Formula를 이용해 풀었던 행렬이다. 이를 cofactor를 이용하여 풀어보도록 하자. 이번 예제를 통해 보이고자 하는 것은 cofactor를 이용하여 nxn과 (n-1)x(n-1)의 determinant를 어떻게 연결지어 풀 수 있는지를 보이고자 하는 것이다. 아래 그림은 식 (14)의 determinant를 행렬식을 이용하여 풀이한 과정을 나타낸다. 

Fig. 5 여인수(cofactor)를 이용한 4x4행렬의 determinant 계산

맨 처음 4x4행렬에 대한 여인수(cofactor) 식을 세우면 det A = a11C11+a12C12+a13C13+a14C14 와 같이 된다. 이 중 a11과 a12의 값이 0이기 때문에 캔슬 되고 나머지 텀인 a13C13+a14C14만 남게 된다. 이때의 cofactor C13과 C14는 맨 처음 행렬 그림에서 각각 흰색 부분의 3x3행렬에 대한 determinant를 나타내고, 이것을 행렬식으로 표현한 것이 바로 그 아래에 있는 식이다. 이때 두 번째 행렬식의 부호가 -인 이유는 C14의 인덱스의 합이 1+4=5와 같이 홀수가 되므로 부호는 음수가 된다. 그 다음 3x3행렬식을 cofactor 공식을 이용하여 2x2행렬로 나타내고, 마지막에 cofactor의 index에 따른 부호를 고려하여 determinant를 계산해주면 결과적으로 0이 나오는 것을 볼 수 있다. 맨 아래 왼쪽의 2x2행렬식은 원래 1(ad-bc) = 1(1-0) = 1이지만, 이때의 cofactor의 index C12가 1+2=3으로 홀수이기 때문에 부호가 -가 된다. 이와 관련해서는 식 (11)을 참조하자. 결과값은 -1 - (0-1)=0이 된다. 

결과적으로 cofactor를 이용하여 최초의 4x4의 행렬식(determinant)으로부터 3x3, 2x2와 같이 작은 크기의 행렬식으로 정리하여 행렬식을 풀 수 있었다. Fig. 5를 잘 이해하도록 하자. 

3. 마치며

이번 포스팅에선 행렬식(determinant)의 실제 계산법에 대하여 공부해봤다. 지난 강의(Lecture 18)에서 배웠던 행렬식의 특성들을 이용하여 Big Formula를 유도하였고, 이를 통해 여인수(cofactor)를 소개하였다. cofactor는 궁극적으로는 nxn의 행렬식을 계산함에 있어 최초의 nxn의 행렬식으로부터 단계적으로 (n-1)x(n-1)의 행렬식과의 관계를 cofactor로 정의하고 이를 통해 행렬식을 계산하는 것에 그 목적이 있다. 사실 일반적으로는 3x3의 행렬식의 계산법 정도는 손으로 풀 줄 알면 좋지만, 그 이상의 크기는 컴퓨터를 이용하여 계산하기 때문에 반드시 알고 있어야 할 필요는 없을 것 같다. 이렇게 계산할 수 있구나 정도면 알아두면 무리가 없을 것이다. 물론 시험을 봐야 하는 학생들은 예외^^

지금까지 우리는 임의의 직사각행렬(Rectangular Matrix)에 집중해 왔다. 이번 챕터부터는 주로 정방행렬(Square Matrix)에 관련된 내용들을 다룰 것이다. 이번 시간과 다음에 이어질 강의에서는 정방행렬의 행렬식(Determinant)에 관해 공부를 할 것이다. 사실 이 행렬식(Determinant)이 필요한 이유는 여러 가지가 있지만, 가장 큰 이유중 한 가지는 바로 고유값(Eigen Value)때문이다. 행렬식과 고유값에 대한 자세한 내용은 이후의 강의에서 공부하도록 하고 이번 강의에서는 행렬식의 속성과 특징들에 대해서 알아보도록 하자. 

1. 행렬식(Determinant)

행렬식(determinant)은 정방행렬(square matrix)에서만 정의되는 숫자이다. 모든 정방행렬은 이 수치를 가지며, 아래와 같이 표현한다. 

det A, 혹은 양쪽에 bar를 붙여서 |A|로 표현한다. 벡터의 크기를 표현할 때 bar를 양쪽에 두 개씩 붙이는 것( ||a|| )과 혼동하지 말자. 행렬식은 행렬의 행렬식(determinant of the matrix)이다. 

행렬식은 magic number와 같다. 이 하나의 숫자로 행렬의 모든 특성이나 속성을 표현할 순 없지만, 어떤 행렬의 가능한 많은 정보들을 압축하여 하나의 숫자에 담고 있다. 가령 수업시간에 많이 배웠던 내용이고 앞으로도 다시 배우겠지만, determinant(행렬이라는 단어와 혼동이 있을까 싶어 앞으로 행렬식이라는 표현보다 영문 표기를 쓰도록 하겠다)가 0이 아닌 경우 그 행렬이 역행렬이 존재함을 의미한다. 혹은 determinant가 0인 경우 행렬이 특이 행렬(singular matrix)임을 의미한다. 따라서 determinant는 어떤 행렬의 invertibility(역행렬의 존재 가능성)를 테스트하는데 사용된다. 수업시간에 determinant에 대해서 주로 이러한 내용에 관해 배웠을 것이다. 하지만 determinant는 이보다 많은 정보들을 담고 있다. 이제부터 하나씩 배워보도록 하자. 

사실 많은 학생들이 determinant를 배울 때 invertibility의 체크에 대한 내용과 계산 과정에 대해서만 배웠을 거라고 생각한다. 계산 과정이야 그대로 따라하면 초등학생들도 할 수 있는 것이고 중요한 것은 determinant가 의미하는 것이 무엇이고 어떤 정보들을 나타내고 있는지를 아는 것이다. 그래서 이번 포스팅에서는 계산 식에 대한 내용은 거의 다루지 않고 다음 포스팅에서 계산 식에 대한 내용들을 다룰 예정이다. 이번 포스팅에서는 우선 determinant의 3개의 주요 특성에 대해 먼저 다루고, 이 3개의 특성을 기반으로 7개의 특성에 대해서 설명을 하도록 하겠다. 

- prop. (1) 

첫 번째 특성은 단위 행렬(Identity matrix)의 determinant는 1이라는 것이다. 이때 행렬은 n x n크기의 행렬에 대해서 동일하게 적용된다. 계산 과정은 이후에 설명하더라도 첫 번째 특성은 매우 간단하기 때문에 더 이상 설명할 것이 별로 없다. 식 (2)의 예로 2 x 2 단위 행렬의 determinant를 계산해보자. determinant의 실제 계산 수식에 대해선 다음 포스팅에서 자세히 다룰 예정이니 일단 수업 시간에 배웠던 2x2 determinant 계산공식을 활용하여 답을 구해보자. 식 (3.1)은 2x2 행렬의 determinant를 구하는 공식이다. 

단위 행렬의 determinant를 계산한 결과, 식 (2)의 특성 처럼 1이 나오는 것을 볼 수 있다. 

- prop. (2) 

두 번째 특성은 행렬의 어떤 row를 다른 row와 바꾸면 determinant의 부호(sign)가 바뀐다는 것이다. 여기 까지의 특성만 봤을 때 혹시 어떤 행렬에 대한 determinant인지 눈치 채셨는가? 

일단 첫 번째 특성은 단위 행렬로부터 시작하였다. n x n에서 n이 얼마이던 간에 단위 행렬이라면 determinant는 1이다. 두 번째 속성은 어떤 정방행렬 이던간에 임의의 row를 교환하면 determinant의 부호가 바뀐다는 것이다. 그런데 특성 1로부터 출발하면 어떤 행렬이 될까? 즉 단위 행렬에서 임의의 row를 교환할 경우 이전에 배웠던 치환 행렬(permutation matrix)이 되는 것을 알 수 있다. 여기서 우리가 알 수 있는 것은 모든 치환 행렬의 determinant는 1 혹은 -1이 된다는 것이다. 이때 1 혹은 -1이 되는 기준은 행 교환(row exchange)을 짝수번(even) 했는지, 아니면 홀수번(odd) 했는지에 따라 정해진다. 즉 맨 처음 단위행렬에서 임의의 행 교환을 1번 했으면 이때의 determinant는 -1이 된다. 여기에서 임의의 행 교환을 한 번 더 하여 총 행 교환을 두 번 하게 되면 determinant는 1이 된다. 

식 (5)는 치환 행렬에 대한 규칙임을 기억하자. 특성 2는 다른 어떤 정방행렬에도 동일하게 적용되며, 단지 행 교환 이전의 determinant에서 부호가 바뀐다는 것을 명심하자. 마찬가지로 2x2 단위 행렬에 대해 특성 2를 적용하여 실제 계산을 수행해보자. 

최초의 단위 행렬에서 row exchange를 했을 경우 determinant의 부호가 바뀌는 것을 볼 수 있다. 여기서 한 번 더 하면 부호는 다시 +부호가 된다. 결국 단위 행렬의 row exchange를 짝수번 하면 1, 홀수번 하면 -1이 되는 것을 확인하였다. 이것은 임의의 n x n 치환행렬에 대해서도 동일하게 작용한다. 지금은 2x2크기의 정방 행렬의 determinant 공식만 다루고 있지만 사실 우리가 원하는 것은 n x n의 행렬에도 적용되는 일반적인 방법이다. 계산 방법은 바로 다음 포스팅에서 다루도록 하고 세 번째 특성으로 넘어가자. 

- prop. (3)-1

세 번째 특성은 사실 핵심이 되는 determinant의 특성이니 잘 이해하도록 하자. (3)-1과 (3)-2로 나누어서 정리하도록 하겠다. (3)-1의 특성을 우선 식으로 써보면 아래와 같다. 

식 (7)이 의미하는 것은 임의의 정방행렬 A에서 임의의 하나의 row에 t라는 scale 상수를 곱한 다음 determinant를 계산하면, A의 determinant에 t라는 상수를 곱한 것과 값이 같다는 것이다. 이때 t는 임의의 하나의 row에만 곱해지는 상수이고 나머지 n-1의 row는 그대로 두는 것이다. t를 2번째 row, 혹은 n번째 row에 곱하고 나머지는 그대로 둔 상태에서 계산해도 식 (7)의 법칙이 적용이 된다. 이것이 특성 (3)-1이다. 실제로 계산해보면 아래와 같다. 

- prop. (3)-2

역시 특성 (3)-2를 먼저 아래와 같이 식으로 정리해보자. 

식 (9)가 의미하는 것은 행렬 A에서 임의의 row에 어떤 벡터를 더했을 때의 determinant는 더한 row를 따로 분리하여 determinant 계산할 수 있다는 것이다.  즉 row1에 v=[a' b']을 더했다면, 원래 행렬의 determinant와 v와 나머지 row들로 만든 행렬의 determinant를 따로 계산하여 더한 값과 같다는 것이다. 이때 주의할 것은 더한 row를 제외한 나머지 n-1의 row들은 그대로 두어야 한다는 것이다. 실제 계산을 해보면 아래와 같다. 

정리해보면 특성 (3)-1과 (3)-2는 임의의 n x n크기의 정방행렬에 동일하게 적용되며, 어느 하나의 row에 scale상수를 곱하거나 임의의 row벡터를 더했을 경우, 나머지 n-1의 row들은 그대로 둬야 한다는 것이다. 결국 이들 특성 (3)-1과 (3)-2로 하여금 determinant를 구하는데 있어 선형 결합(Linear combination)의 규칙이 작용하는 것이다. determinant는 선형 함수(Linear Function)이다. 특성 (3)-1과 (3)-2를 같이 쓰면 아래와 같다. 

식 (11.1)은 determinant의 선형결합에 관한 식을, (11.2)는 그에 대한 예를 나타낸다. 

여기서 어떤 사람들은 오해를 할 수 있다. 즉 determinant가 선형 함수라고 해서 모든 row에 대해서 이러한 선형성이 동시에 적용되는 것이 아니다. 아래 식은 틀린 식이다. 

식 (12)는 determinant의 선형성이 모든 row에 대해서 동시에 적용되지 않음을 나타내는 것이다. 중요한것은 우리가 지금까지 determinant의 특성들에 대해서 언급하고 예를 들었을 때 단 하나의 row에 대해서만 적용을 하고 나머지 row들은 그대로 뒀다는 것이다. 결국 어떤 정방행렬의 determinant는 각각의 row에 대해서만 독립적으로 선형성(Linearity)을 나타낸다. 

이렇게 하여 determinant의 주요 특성 세 가지를 정리하였다. 우리는 이 세 가지 주요 특성들을 통해 어떠한 행렬의 determinant라도 정의할 수 있다. 그러나 이 세 가지 말고도 determinant는 다양한 특성들을 가지고 있다. 이제 이 세 가지 기본적인 특성들을 기반으로 determinant에 대한 나머지 특성들에 대해서도 알아보자. 

- prop. (4)

네 번째 특성은 행렬 A에 똑같은 row가 2개 존재한다면 그 행렬의 determinant는 0이 된다는 것이다. 사실 2 x 2의 경우엔 이해가 간다. 2 x 2에서 두 개의 row가 같아지면 det A=ab-ab=0 이 되기 때문에 당연히 0이 될 것이다. 하지만 왜 n x n의 행렬의 경우에도 같은 row가 두 개 존재하면 determinant가 0이 될까? 예를 들면 10 x 10의 정방행렬에서 row 2와 row 7이 같다고 해보자. 이렇게 큰 행렬에서 단지 두 개의 row가 같다고 해서 왜 determinant가 0이 될까? 

우리는 지금까지 determinant의 주요한 3개의 특성을 공부했다. 단위 행렬의 determinant가 1이 되는 특성, 행을 교환하면 determinant의 부호가 바뀌는 특성, 그리고 각각의 row에 독립적으로 적용되는 선형성(linearity)등이다. 어찌 되었든 우리는 앞서 배운 세 개의 특성을 가지고 바로 이 네 번째 특성을 정의해야 한다. 어떻게 할 수 있을까? 바로 prop. (2)로 부터 정의할 수 있다. 

prop. (2)는 row exchange가 발생했을 때 원래의 행렬과 다른 행렬이 만들어지게 되고, 결국 determinant의 부호가 바뀐다는 특성이다. 그러나 두 row가 같아져 버리면 row exchange를 해도 원래 행렬과 같아진다. 그러나 prop. (2) 특성은 반드시 만족해야 하기 때문에 부호를 반드시 바꿔야 하는데, 원래 행렬과 같기 때문에 부호를 바꾸어도 똑같아야만 한다. 수 많은 숫자들 중에 부호를 바꿔도 똑같은 숫자가 딱 한가지 있다. 바로 0(zero)이다. 따라서 어떤 행렬 A가 두 개의 같은 row를 가지고 있을 경우, A의 determinant가 0이 되어야만 같은 row를 교환하여 부호가 바뀌어도 prop. (2)가 성립하게 된다. 

또한 이렇게 생각해 볼수도 있다. 정방행렬에서 두 개의 같은 row가 있다면 rank는 n보다 작다. 따라서 이 행렬은 역행렬이 존재하지 않게 되므로 처음에 언급했듯이 determinant가 0이 되어야 한다. 

- prop. (5)

다섯 번째 특성은 소거(elimination)와 관련이 있다. Lecture 2에서 배웠듯이 소거 과정에서 우리는 pivot 변수를 지정하고 그 아래에 있는 원소들을 0으로 만들기 위해 pivot row에 특정 상수를 곱한 다음, 제거 할 row에서 이를 빼준다. 따라서 제거 할 k번째 row로 부터 상수값 $l$을 찾아서 pivot row와 곱해준다음 이를 k 번째 row에서 빼준다. 여기서의 특징은 이러한 소거 과정에서 중간에 나타나는 행렬의 determinant는 처음과 같다는 것이다.  즉 아래의 식과 같다. 

다시 말하자면 원래의 행렬 A를 소거하여 상삼각행렬(Upper triangular matrix) U를 만들었을 때, U의 determinant는 A의 determinant와 동일하다는 것이다. 결국 행렬 A를 소거를 해도, 소거 과정에서 나오는 어떠한 행렬도 determinant는 변하지 않는다. 이것이 다섯 번째 특성이다. 

그렇다면 이 특성은 어디서부터 오는가? 설명을 위해 식 (14)를 2x2행렬에 표현해 보자. 

식 (15)는 2x2행렬에서 소거를 위해 row1에 $l$을 곱하여 row2에서 빼주는 식에 대한 determinant를 나타낸 것이다. 그런데 이 식은 우측과 같이 분리가 가능하다. 바로 특성 prop. (3)-2로 부터 파생되는 것이다. 결과적으로 식 (15)의 최 우측의 determinant는 0이 되어 원래 행렬의 determinant와 같아지는 것을 볼 수 있다. prop. (3)-2를 통해 소거된 행렬과 원래 행렬의 determinant는 같음을 보였다. 

여기서 최 우측의 determinant에 prop. (3)-1을 적용할 수 있다. row2에 곱해져 있는 $l$을 밖으로 빼내면 아래와 같이 쓸 수 있다. 

이렇게 되면 최 우측 행렬의 determinant는 row1과 row2가 같다. 따라서 prop. (4)에 의해 0이 된다. 

prop. (5)를 정리하자면 임의의 행렬 A를 소거하는 과정에서 만들어지는 모든 행렬은 원래의 행렬 A와 같은 determinant값을 가진다. 이를 이전에 정리했던 특성들 prop. (3)-1, prop. (3)-2, prop. (4) 를 통해 정리하였다. 

- prop. (6)

Determinant의 여섯 번째 특성은 간단하다. 바로 원소들이 모두 0인 row가 하나 라도 존재한다면 determinant가 0이 된다는 것이다. 

모든 원소가 0인 row가 하나 라도 존재한다면, 해당 행렬은 특이 행렬(singular matrix)이 되고, rank는 n보다 작아지며, 역행렬은 존재하지 않는다. 그렇다면 이전의 특성들로부터 어떻게 특성 (6)을 유도할 수 있을까? 바로 prop. (3)-1으로부터 유도할 수 있다. 

예를 들어 t=0이고, t가 어떤 특정 row에 곱해졌다고 생각해보자. t는 prop. (3)-1에 의해 밖으로 뺄 수 있는데, t가 0이기 때문에 결국 determinant는 0이 된다. 

- prop. (7)

일곱 번째 특성은 매우 중요하면서 유용하므로 집중해서 잘 알아두도록 하자. 이는 상삼각행렬(Upper triangular matrix)과 관련되어있다. 2x2크기의 경우엔 determinant를 구하는 것이 어렵지 않지만, 100x100과 같이 큰 행렬일 경우엔 계산 과정이 굉장히 오래 걸린다. 이번 특성은 이러한 determinant의 계산을 손쉽게 해주는 방법이고 굉장히 유용하게 사용될 수 있다. 일단 아래의 상삼각행렬을 보자. 

4x4처럼 표현 되긴 했지만, 식 (19)를 n x n크기의 정방행렬이라고 생각해보자. 상삼각행렬이기 때문에 대각선 원소들을 중심으로 아래쪽 원소들은 모두 0이다. 대각선 원소들을 d1, d2, ... dn이라고 표현하고, 위쪽에 있는 원소들은 중요하지 않기 때문에 별표로 표시하였다. 

상삼각행렬(Upper triangular matrix)은 원래의 행렬 A를 소거(elimination)하여 만들 수 있는 행렬이다. 따라서 prop. (5)에서 확인했듯이 원래 행렬의 determinant와 같다. 그러나 이 상태에서 determinant를 구할 수 있는 더 쉬운 방법이 있다. 바로 상삼각행렬의 determinant는 대각 원소 d1, d2, ... dn들의 곱으로 구할 수 있다. 즉

따라서 상삼각행렬을 얻었을 때 determinant를 구하려면 대각 원소들을 곱해주기만 하면 된다. MATLAB과 같이 행렬 연산을 하는 software의 경우, 실제 어떤 행렬의 determinant를 계산할 때 먼저 소거(elimination)를 통해 상삼각행렬을 만들어준 뒤 pivot원소인 대각 행렬의 곱을 통하여 determinant를 계산한다. 행렬의 크기가 늘어날 수록 계산이 복잡해지는데, 이와 같은 방법으로 계산을 해주면 훨씬 빠르고 효율적으로 계산할 수 있다. 

대각 원소들의 곱으로 determinant를 구하는 건 알았고, 한 가지 더 신경써야 할 부분이 있다. 바로 determinant의 부호이다. 소거를 하는 과정에서 그대로 한 번에 된다면 좋겠지만, 어떠한 경우에는 행 교환(row exchange)을 해야할 때가 생긴다. 소거 과정에서 row exchange가 필요한 경우엔 부호를 살펴야하고 그렇지 않은 경우엔 그대로 대각 원소 d들을 곱해주면 된다. 만약 행 교환이 홀수번 일어나면 대각 원소들의 곱의 결과 값에 -1을 곱해주면 되고, 행 교환이 짝수번 발생하면 그대로 두면 된다. 이는 prop. (2)로 부터 증명할 수 있다. 

여기서 한 가지 의문점이 생긴다. 식 (20)에서 determinant를 구하기 위해선 대각 원소들의 곱을 통해 구할 수 있다고 했는데, 왜 *로 표시된 값들은 determinant에 영향을 미치지 않을까? 이를 어떻게 증명할 수 있을까? 이는 prop. (5)를 통해 증명할 수 있다. 소거를 해도 determinant에는 영향을 미치지 않기 때문에 Lecture 3의 Gauss-Jordan에서 했던 위쪽 방향으로의 소거를 해도 같다. 결국 U행렬은 대각 원소들만 존재하는 대각 행렬(diagonal matrix)이 되며,  determinant는 아래 식과 같이 표현할 수 있다. 

이제 대각 행렬을 제외한 나머지 원소들은 determinant에 영향을 미치지 않는 것으로 증명이 되었다. 그런데 왜 하필 대각 원소들의 곱일까? 이는 prop. (1)와 prop. (3)-1을 통해 증명할 수 있다. 우선 식 (21)을 보면 U의 각 row에 d1, d2, ... dn들이 곱해져 있는 형태이다. prop. (3)-1에 의해 우리는 이 d들을 밖으로 뺄 수 있다. d1을 시작으로 d2, d3, ... dn을 차례로 빼면 아래와 같은 형태가 된다. 

식 (22)에서 d들을 밖으로 빼면 대각 행렬은 단위 행렬(identity matrix)이 되며, prop. (1)에 의해 단위 행렬의 determinant는 1이 된다. 결과적으로 대각 원소들의 곱으로 상삼각행렬 U의 determinant를 구하는 것을 prop. (1), (2), (3)-1, (5)를 통해 증명하였다. 최초의 행렬 A에서 prop. (5)를 통해 소거를 하여 D를 만들고, prop. (3)-1을 통해 d들을 밖으로 빼내었으며, prop. (1)을 통해 d들의 곱만으로 determinant를 계산할 수 있음을 보였다. 또한 행 교환이 필요한 경우 prop. (2)를 통해 부호를 적절히 바꿀 수 있음을 보였다. 

결국 prop. (7)이 말하고자 하는 것은 A가 특이 행렬(singular matrix)이 아닐 때, determinant를 대각 원소들의 곱만으로 계산할 수 있다는 것이다. 매우 중요하니 잘 알아두도록 하자. 

- prop. (8)

prop. (7)에서는 pivot원소, 즉 d1 ~ dn이 0이 아님을 가정하였다. 그런데 만약 식 (20)에서 만약 어느 하나의 pivot 원소 dk가 0인 경우엔 어떻게 될까? 이 경우엔 위쪽 방향으로의 소거를 통해 식 (21)과 같이 대각 행렬(diagonal matrix)을 만들었을 때 dk=0인 row가 zero row가 된다. 이 경우 prop. (6)에 의해 행렬 자체가 특이 행렬임이 판명나고, 결국 determinant는 0이 된다. 따라서 여덟 번째 특성은 행렬 A가 특이 행렬(singular matrix)일 때 determinant가 0이 되고, A가 특이 행렬이 아닐 때, 즉 역행렬을 가질 때(invertible)는 determinant가 0이 아니다. 

어떤 pivot 원소가 0이라는 것은 결과적으로 행렬의 rank가 그 만큼 줄어들게 되고, 하나의 zero row를 갖게 되어 prop. (6)에 따라서 determinant는 0이 된다. 결국 full rank가 아닌 행렬은 특이 행렬이 되어 역행렬이 존재하지 않게 된다. 이것을 우리는 determinant의 계산을 통해 알 수 있다. 따라서 determinant의 계산은 역행렬의 존재 여부를 판단할 수 있는 좋은 방법이다. 

반면 행렬 A가 역행렬을 가질 때, 우리는 소거를 통해 A를 U(upper triangular matrix)로 만들고, 다시 위쪽으로 소거하여 D(diagonal matrix)를 만들고, 대각 원소 d1 ~ dn을 곱하여 determinant를 계산한다. 여기서 중요한 사실 한 가지는 우리는 방금 언급한 이 사실을 통하여 determinant의 공식을 유도할 수 있다는 것이다. 2x2크기의 정방행렬에 대한 determinant의 계산 공식은 다들 알다시피 ad-bc이다. 그러나 이 공식이 어떻게 유도되었는지 아는 사람은 그리 많이 않을 것이다. 아래 식을 보자. 

식 (24)는 행렬 A를 소거하여 상삼각행렬 U를 만든 것이다. (24.1)을 보면 소거할 때 pivot인 a를 소거할 원소인 c와 같게 만들기 위해 c/a를 row1에 곱한 뒤 row2에서 이를 빼준다. 이해가 잘 가지 않는다면 예를 든 (24.2)를 참고하기 바란다. 어쨋든 행렬 A를 소거하여 (24.1)과 같이 상삼각행렬 U를 만들었다. 우리는 prog. (7)을 통해 U의 determinant는 대각 원소들을 곱하면 된다고 이미 배웠다. 0인 pivot이 없으므로 (24.1)의 대각행렬을 곱해보자. 어떤 식이 나오는가? 

우리가 수업시간에 determinant를 구할 때 늘 써먹던 그 식은 바로 이와 같이 determinant의 prop. (1) ~ prop. (7)로 부터 유도된 것이다. 만약 식 (24)에서 a가 0이면 row exchange를 하고 determinant의 부호를 바꾸면 되고, 그래도 계산할 수 없다면 A가 특이 행렬이다. 

정리하자면 어떤 임의의 크기의 정방행렬 A의 determinant는 소거를 통해 만들어진 U의 대각 성분들의 곱으로 간단히 구할 수 있으며, (25)는 이런 절차에 따라 유도된 식이다. 

- prop. (9)

아홉번 째 특성은 간단하면서도 굉장히 유용하다. 일단 먼저 써보도록 하겠다. 

행렬 A와 B의 곱의 determinant는 determinant A와 determinant B의 각각의 곱과 같다는 것이 아홉번째 특성이다. 언뜻 보면 별것 아닌 것처럼 보이겠지만, 이 특성은 굉장히 값지고 유용한 특성이다. 이전의 prop. (3)-2의 식 (12)에서 행렬의 덧셈에 대한 determinant는 성립하지 않음을 알았다. 즉 모든 row에 대한 선형성(linearity)이 동시에 적용되지는 않는다는 것이다. 그러나 재밌게도 행렬의 곱셈에 대한 determinant는 분리하여 정의할 수 있다. 

예를 한 번 들어보자. A의 역행렬(inverse matrix)에 대한 determinant는 어떻게 정의할 수 있을까? 

식 (27.1)은 A의 역행렬과 A를 곱하면 단위행렬이 된다는 우리가 잘 아는 관계식이다. 식 (27.1)을 식 (26)을 이용하여 determinant를 구하면 (27.2)와 같이 되는데, 우변의 단위 행렬의 determinant는 prop. (1)에 의해 1이 된다. 여기서 식 (27.2)의 양변을 det A로 나눠주면 아래와 같이 det A(inverse)를 정의할 수 있다. 

A의 역행렬의 determinant는 1/(det A)로 정의할 수 있다. 사례를 한 번 들어보자. A를 소거를 통하여 대각 행렬(diagonal matrix) D로 만들었다고 했을 때, 식 (28)의 내용을 아래와 같이 쓸 수 있다. 

결과적으로 식 (26)이 의미하는 것은 어떤 두 개의 대각 행렬(diagonal matrix)의 관계를 정의할 때 유용하게 사용될 수 있으며, 이때 만약 행렬들이 대각행렬이 아니라면 소거 과정을 통해 대각 행렬을 만들어 이들을 적용할 수 있다. 

앞서 언급했지만 determinant는 행렬 A의 역행렬의 존재 여부(invertibility)를 체크하는데 사용된다. 즉 A가 역행렬을 가지면 determinant는 0이 아니고, 역행렬을 가질 수 없으면(singular matrix이면) determinant는 0이 된다. 이를 식 (28)을 통해 설명할 수 있다. A determinant가 0이 되면 A의 역행렬의 determinant가 1/0이 되어 식이 이상하게 되어버린다. 따라서 determinant는 역행렬의 존재 여부를 판별할 때 좋은 기준이 된다. 

약간 다른 경우도 한 번 살펴보자. A의 제곱인 경우엔 어떨까? 즉 A*A말이다. 이 역시 (det A)(det A)가 된다. 그렇다면 2*A의 determinant는 어떻게 될까? 2*A는 A+A이다. 이 경우엔 어떻게 정의할 수 있을까? 이때는 단순히 2*(det A)는 틀린 답이다. 2*A라는 것은 A의 모든 row에 각각 2씩을 곱해준 것이다. 따라서 prop. (3)-1과 식(22)와 같이 2를 앞쪽으로 빼줄 수 있다. row1에 곱해진 2를 먼저 앞으로 빼고, row2, ... row n에 곱해진 2를 차례로 앞으로 빼면 결과적으로 2를 n번 만큼 앞으로 빼서 곱해준 셈이 되기 때문에 2의 n승이 된다. 이들을 정리하면 다음과 같다. 

식 (30.1)은 식 (26)에 의해 정의된 것이다. 또한 나중에 자세히 다룰 기회가 있겠지만 식 (30.2)의 determinant는 어떤 volume을 정의하는데 있어 유용하게 사용된다. 

- prop. (10)

마지막 열 번째 특성도 그리 어렵진 않다. 바로 적어보겠다. 

열 번째 특성은 A의 transpose의 determinant는 원래 A의 determinant와 같다는 것이다. 일단 여기서 다루고 있는 행렬은 정방행렬이므로 전치(transpose)를 해도 A의 가로, 세로의 크기는 변하지 않는다. 눈여겨 봐야할 것은 row와 column이 바뀐다는 것이다. 

지금까지 우리는 determinant와 관련된 모든 작업을 row 기준으로 해왔다. 모든 원소가 0인 row가 하나라도 있을 경우 determinant는 0이 되는 등 row기준으로 모든 작업을 진행해왔다. 그렇다면 모든 원소가 0인 column이 존재한다면 determinant는 어떻게 될까? 정답은 똑같이 0이다. 마찬가지로 행 교환(row exchange)을 했을 때 부호가 바뀌었다면, 열 교환(column exchange)을 했을 때에도 부호가 바뀐다. 그리고 일단 식 (31)의 determinant를 구했을 때, 양쪽 모두 ad-bc로 식은 같다.

 뭔가 같은 것 같긴 하지만 그래도 이전의 특성들을 활용해 식 (31)을 증명해보자. 아래 식을 보자. 

최초의 식 (33.1)에서 Lecture 4에서 배웠던 LU 분해(LU decomposition)를 통해 식 (33.2)와 같이 만들 수 있다(두 행렬의 곱에 transpose를 취하면 순서가 바뀜에 유의). 식 (33.2)는 하삼각행렬(Lower triangular matrix) L과 상삼각행렬(Upper triangular matrix) U의 곱으로 이루어져 있다. 이를 바로 전에 배웠던 prop. (9)의 특성을 이용하여 정리하면 식 (33.3)과 같이 된다. 여기서 L의 경우 대각 원소들은 1로 이루어져있다. 이 L행렬들의 대각 원소들을 제외한 나머지 원소들은 소거(elimination)를 통하여 없앨 수 있고, 결국 L의 determinant는 1이 된다. 

이제 남은 것은 식 (33.4)의 U이다. 알다시피 U도 transpose이던 아니던 삼각행렬(triangular matrix)의 형태를 띈다. 어떤 삼각 행렬이던간에 대각 원소들을 제외한 나머지 원소들은 소거를 통하여 없앨 수 있으며 determinant의 계산에 영향을 미치는 것은 결국 대각 원소(diagonal elements)들이다. 따라서 U를 transpose해도 대각 원소들은 바뀌지 않기 때문에 결과적으로 determinant는 같다. 이렇게 하여 determinant의 열 번째 특성도 증명을 하였다.  

2. 마치며

이번 강의에선 행렬식(determinant)의 특성들에 대해서 알아보았다. 아직 2x2크기의 행렬 이외의 determinant를 구하는 계산식은 배우지 않았는데 이들은 다음 포스팅에서 다룰 예정이다. 사실 계산식을 배우는 것 보다는 determinant가 가지고 있는 특성들을 먼저 이해하는 것이 나중에 응용될 여러 가지 수식들에 대해서도 훨씬 유용하다. 우리는 먼저 determinant의 중요한 3가지 특성들을 정리하고, 이를 기반으로 나머지 7개의 특성들에 대해서 정리하였다. 마지막으로 중요한 말 한 가지만 하자면, determinant는 pivot들의 곱으로 이루어지는 수치이다 !.

각 특성들은 determinant를 이해하는 데에 중요하기 때문에 반드시 이해하고 넘어가시기 바랍니다. 

특성들이 총 10가지나 되기 때문에 이를 한 눈에 알아보기 쉽게 아래에 표로 정리하였으니 참고하기 바랍니다. 꼭 표만 보지 마시고 반드시 본문의 내용을 숙지하신 뒤 참고용으로만 보시는 것을 추천드립니다. 

• Determinant의 특성들

특성	수식	설명
prop. (1)		단위행렬의 determinant는 1이다.
prop. (2)		행을 바꾸면 determinant의 부호가 바뀐다.  홀수번 바꾸면 -1, 짝수번 바꾸면 원래 부호 그대로.
prop. (3)-1		행렬의 하나의 row에 곱해진 상수는 밖으로 뺄 수 있다.
prop. (3)-2		행렬의 하나의 row에 더해진 row벡터는 분리하여 정리할 수 있다.
prop. (4)		행렬에 두 개의 똑같은 row가 존재하면 determinant는 0이 된다.
prop. (5)		행렬을 Gauss소거법으로 소거하여도 determinant의 값은 변하지 않는다.
prop. (6)		모든 원소가 0인 row가 하나 라도 존재한다면, determinant는 0이다.
prop. (7)		삼각행렬(triangular matrix)의 determinant는 대각 원소들의 곱으로 간단히 구할 수 있다. 이때 d들은 0이 아니어야 한다.  일반 행렬들도 소거를 통해 삼각행렬을 만들고 대각 원소들의 곱으로 간단히 determinant를 구할 수 있다.
prop. (8)		행렬 A가 특이 행렬(singular matrix)이면 determinant는 0이다.   역행렬이 존재하면 determinant는 0이 아니다.  반대로 determinant를 통해 행렬의 역행렬 존재 여부를 판별할 수 있다.
prop. (9)		두 행렬의 곱 AB의 determinant는 각 행렬의 determinant의 곱과 같다.  A의 역행렬의 determinant는 A의 determinant의 역수이다.  A의 제곱의 determinant는 A의 determinant의 제곱과 같다.  A에 상수를 곱한 determinant는 상수의 n승을 A의 determinant에 곱한 것과 같다.
prop. (10)		행렬 A의 transpose의 determinant는 원래 행렬의 determinant와 같다.  즉 transpose를 해도 determinant는 변하지 않는다.

지난 강의 Lecture 17-(1)에 이어 직교행렬과 그람-슈미트 과정 두 번째 강의다. 반드시 이전 강의에서 직교행렬(orthogonal matrix)을 공부하고 오기를 추천한다. 이제 그람-슈미트 과정(Gram-Schmidt Process)에 대해 공부해보도록 하자. 

4. 그람-슈미트 과정(Gram-Schmidt Process)

지난 강의의 마지막 부분에서 잠깐 언급했듯이, 그람-슈미트 과정(Gram-Schmidt Process)은 어떤 임의의 행렬 A의 column vector를 orthonormal column들로 바꾸는 것이다. 즉 행렬 A를 정규직교벡터(orthonormal vector)들로 이루어진 직교 행렬(orthogonal matrix) Q로 만드는 것이다. 이때 중요한 조건은 A의 column vector들이 독립(independent)이어야 한다. 아래 그림을 보자. 

Fig. 1 두 개의 독립(independent)인 벡터

Fig. 1은 두 개의 독립(independent)인 벡터를 나타낸다. 두 벡터 a와 b를 임의의 차원의 공간에서 2차원을 정의하는 기저벡터라고 하자. a와 b는 독립이기 때문에 분명 선형조합(Linear combination)을 통해 2차원 공간의 모든 벡터를 나타낼 수는 있다. 그러나 보다 효과적인 연산, 간단한 연산을 위해 이들을 똑같은 공간을 정의하는 정규직교벡터(orthonormal vector)로 만들고 싶은 것이다. 그람-슈미트 과정은 이렇게 독립인 벡터들을 정규직교벡터로 만들어준다. 

그람-슈미트 과정의 아이디어는 다음과 같다. 먼저 맨 처음 벡터인 a는 그대로 두고 시작한다. 이 a를 기준으로 a에 직교(orthogonal)한 벡터를 만들어낸다. 이를 각각 q1, q2라고 하자. 즉 a->q1, b->q2로 만드는 것이다. 여기까지 그람(Gram)의 아이디어다. 다음으로 할 일은 직교 벡터인 q1, q2를 정규직교벡터(orthonormal vector)로 만드는 것이다. 이는 q1과 q2를 각각 자신의 크기로 나누어주면 된다. 이것이 슈미트(schmidt)의 아이디어다. 지금까지의 과정을 정리하면 아래와 같다. 

Fig. 2 그람-슈미트(Gram-Schmidt)의 과정

- (1) Making Orthogonal Vectors (by Gram)

이제 Fig. 1의 두 벡터 a와 b를 가지고 그람-슈미트 과정을 수행해보자. 먼저 벡터 a는 그대로 q1이 된다. 마치 초기값과 같은 것이다. a->q1으로 변하는 과정은 전혀 문제가 없다. 문제는 b->q2의 과정이다. 왜냐하면 b는 a에 직교하지 않기 때문이다. 우리가 하고자 하는 것은 a와 독립이지만 직교는 아닌 벡터 b에서 출발하여 a와 직교인 벡터 q2를 찾는 것이다. q2를 어떻게 만들 수 있을까? 바로 Lecture 15에서 배웠던 투영(Projection)을 이용하는 것이다. 아래 그림을 보자. 

Fig. 3 투영을 이용한 직교 벡터 계산 방법

첫 번째 벡터인 빨간색 a는 그대로 q1이 된다. 그다음 두 번째 벡터 b를 a에 투영시켜서 p를 만드는데, 이때 error벡터인 e를 만들어낼 수 있다. 즉 b를 a에 투영시킬때, a에서 b에 가장 가까운 지점은 b와 연결되면서 a에 수직한 지점이다. 투영의 정의에 의해서 b와 연결되는 a에 수직한 지점으로 투영이 되어 벡터 p가 생성되고, 결과적으로 b에서 p를 빼면 e=b-p 를 계산할 수 있다. 이때의 e는 a와 수직(perpendicular)한 벡터가 되고 e가 곧 q2가 된다. 결국 투영(projection)을 이용하여 a=q1에 수직한 벡터 e=q2를 만들어낼 수 있다. 

투영 파트에서는 구하고자 하는 벡터가 p였고 e는 그저 버려지는 벡터였는데, 이번엔 반대로 p가 버려지고 e를 취하게 되었다. 투영에 관한 자세한 사항은 위에 링크를 걸어놓은 Lecture 15를 참고바란다. 

그렇다면 q2에 대한 실제 식은 어떻게 될까? 아직 투영 행렬 P를 모르는 상태이고, 주어진 것은 벡터 b와 벡터 a=q1이다. e=b-p에서 p에 대한 식만 정리하면 된다. 식은 아래와 같다. 

뭔가 익숙한 식일 것이다. Lecture 15(이해가 안가면 꼭 먼저 공부하고 오자)에서 벡터를 이용하여 투영 벡터를 구할 때 보던 식이다. p=xa에서 분수 부분이 바로 x에 해당한다. 현재 q1은 원래의 a와 같다. 이렇게 하여 q2를 구하였다. 결과적으로 q1과 q2는 수직(perpendicular)이다. 즉 내적(dot product)을 했을 때 결과가 0이어야 한다. 식이 맞는지 확인해보도록 하자. 

식을 곱해서 전개하면 분수의 분모가 캔슬되고 분자만 남게되고(분수의 계산 결과는 상수임을 기억하자), 결과는 0이 된다. q1과 q2가 직교(orthogonal)임을 식의 전개를 통해 확인하였다. 

우리는 지금까지 두 개의 독립인 벡터 a와 b를 가지고 a를 기준으로 서로 직교(orthogonal)인 벡터 q1과 q2를 만들었다. 이제 세 번째 벡터 q3를 만들어보자. q3를 만들기 위해선 a와 b와 독립인 벡터 c가 필요하다. Fig. 1의 a와 b에서 화면으로 나오는 방향, 혹은 들어가는 쪽으로 비스듬하게 독립인 벡터 c가 있었다고 가정해보자(이때의 행렬은 3x3크기의 full rank=3인 행렬). Fig. 3은 a와 b로부터 q1과 q2를 만든 모습이다. 아래의 Fig. 4는 이 시점에서부터 시작한다. 

Fig. 4 독립 벡터 c의 그람-슈미트 과정 첫 번째 단계. 왼쪽 그림은 옆에서 바라본 장면이다. 

(2D로 표현하기에는 한계가 있어서 3D-CAD툴을 이용하여 표현하였다)

Fig. 4는 독립인 벡터 c를 q1과 q2에 동시에 직교(orthogonal)한 벡터로 만드는 그람-슈미트 과정의 첫 번째 단계를 나타낸다. 파란색 벡터 c는 독립이긴 하지만 q1과 q2어느 누구와도 직교는 아닌 상태이다(Fig. 4의 왼쪽 side view 참고). 여기서 우리가 해야할 일은 c를 q1과 q2에 동시에 직교하게 만들어야 하는데, 먼저 q1과 직교하게 만들고 그 다음 q2와 직교하게 만들면 된다. Fig. 4는 이 중 q1과 직교하게 만드는 과정을 나타낸다. 

벡터 c를 a에 투영시키면 녹색 벡터 p를 얻을 수 있고, p=xa와 ec1=c-p에 의해 a와 직교한 에러 벡터 ec1을 구할 수 있다. 이 과정은 식 (1)과 같은 과정이며, e->ec1, b->c, 와 같이 c에 맞게 바뀐 것이다. 이것을 식으로 나타내면 아래와 같다. 

벡터 c로부터 이렇게 q1과 직교인 에러 벡터 ec1을 만들어냈다. q1과 직교인 벡터를 만들어 냈으니 다음은 q2와 직교한 벡터를 만들 차례다. 아래 그림은 Fig. 4에 이어 q2와 직교한 벡터를 만드는 과정을 나타낸다. 

Fig. 5 q2와 직교한 벡터 ec2를 만드는 과정. 결과적으로 에러 벡터 ec2는 q1과 q2에 동시에 직교하므로 ec2=q3이다. 

q1과 직교한 벡터 ec1을 q2에 투영시키면 벡터 p를 얻고, 이 둘 사이의 에러 벡터인 ec2=ec1-p를 계산해주면 최종적으로 ec2를 구할 수 있다. Fig. 5에서 보는 것과 같이 ec2는 q1과 q2모두에 직교한 벡터이기 때문에 결과적으로 ec2=q3가 된다. 이를 식으로 나타내면 아래와 같다. 

약간 복잡해 보이지만 그리 어렵지 않으니 차근차근 확인해보자. 먼저 ec2는 앞서 구한 ec1에서 투영 벡터 p를 빼주면 구할 수 있는데, 이때 투영 벡터 p는 q2에 어떤 스칼라(scalar)상수를 곱한 것과 같다. 이 예에선 음수 값이 될 것이다. 그리고 ec2는 q2와 직교 하기 때문에 내적(dot product)을 해주면 그 결과가 0이 된다. 이러한 정의들을 가지고 식을 치환하고 전개해서 풀어주면 x에 관한 식을 (4.1)과 같이 구할 수 있다. 

그 다음 ec2=ec1-p에서 p를 x q2로 치환한 후 (4.1)의 x를 대입해주면 (4.2)와 같은 식을 구할 수 있다. 그런데 식에 ec1이 있어서 약간 혼란스러울지도 모르겠다. ec1을 식 (3)에서 정의한 내용으로 치환하여 다시 정리하면 아래와 같다. 

식이 많이 길지만 겁먹을 건 없다. 그저 치환해서 정리한 것 뿐이다. 먼저 (5.1)은 (4.2)의 분수의 분자에 있는 ec1을 (3)으로 대체하여 정리한 것이고 (5.2)와 같이 전개된다. 이때 분자에 q2 transpose와 q1을 내적하는 부분이 있는데, q1과 q2는 직교(orthogonal)이기 때문에 0이 되어 사라지고 (5.3)과 같이 된다. 이제 (5.3)의 ec1을 (3)으로 대체하여 정리해주고 ec2를 q3로 바꿔주면 최종적으로 식 (5.5)와 같이 정리된다. 

이렇게 하여 임의의 독립(independent)인 column 벡터 a, b, c로부터 같은 column space를 공유하면서 직교(orthogonal)하는 직교 벡터(orthogonal vector) q1, q2, q3를 구하였다. 다시 한 번 식을 한 번에 정리해보자. 

q1은 굉장히 쉽게 구했다. 그냥 첫 번째 벡터인 a를 대입하면 된다. q2는 b의 투영을 통해 a와 직교한 에러 벡터(error vector) e를 구하는 식이다. 마지막 q3는 c를 q1과 q2에 순차적으로 투영시켜 에러 벡터를 구하게 된다. q3의 패턴을 살펴보면 원래의 벡터 c에서 q1으로 투영시킨 벡터, q2로 투영시킨 벡터를 각각 빼준다. 여기서 한 가지 중요한 사실은 만약 4차원, 5차원, n차원 column vector가 더 있다면 q4, q5, qn을 위와 같은 패턴으로 구할 수 있다는 것이다. 물론 조건은 독립(independent)이어야 한다. 만약 q4를 구해야 한다면 원래 벡터인 d에서 q1, q2, q3로 각각 투영시킨 벡터들을 빼주면 된다. 이것이 Gram이 제안한 직교벡터를 만드는 아이디어이다. 

마지막으로 q3를 구하는 과정을 하나의 그림으로 살펴보고 다음으로 schmidt가 제안한 아이디어를 알아보도록 하자. 아래 그림은 q3를 구하는 과정을 하나의 그림으로 표현한 것이다. Fig. 4와 Fig. 5를 하나로 합친 것으로 생각하면 된다. 벡터 c부터 시작한다. 

Fig. 6  q3를 구하는 과정. 벡터 c부터 시작

- (2) Making Orthonormal Vectors (by Schmidt)

그 다음 과정은 상대적으로 간단하다. 지금 까지 구한 직교 벡터(orthogonal vector)는 정규화(normalized)가 되어 있지 않다. 즉, 각 벡터의 크기가 제각각이다. 이들을 방향 성분만을 나타내는 벡터로 만들기 위해선 정규화를 통해 정규직교벡터(orthonormal vector)로 만들어 줘야한다. 정규직교벡터를 만드는 방법은 각 벡터를 자신의 크기로 나누어 주면 된다. 

기존의 직교 벡터(orthogonal vector)와 구분해주기 위해 q hat으로 표현을 했다. 이렇게 직교 벡터로부터 정규직교벡터를 만드는 것은 schmidt의 아이디어이다. 

이렇게 해서 기존의 독립(independent)인 column vector a, b, c로부터 정규직교벡터(orthonormal vector) q1, q2, q3를 만들어냈다. 이 실제 벡터를 이용해서 계산해 보도록 하자. 

5. 예제와 MATLAB 구현

- 2D subspace in R3

아래의 두개의 독립인 3차원 벡터를 그람-슈미트 방법(Gram-Schmidt Process)을 이용하여 정규직교벡터(orthonormal vector)로 만들어보자. 벡터 a와 b는 3차원 공간에 존재하는 벡터들이며, 이 두 벡터가 이루는 column space는 2차원 평면 임을 알아두자. 

먼저 식 (6.1)과 (6.2)를 이용하여 직교 벡터(orthogonal vector)로 만들면 아래와 같다. 

직교 벡터 q1과 q2는 구했고, 이제 정규화를 해보자. q1과 q2를 각각의 크기로 나누어주면 아래와 같이 단위 벡터가 만들어진다. 

이렇게 하여 a와 b로부터 정규직교벡터(orthonormal vector) q1과 q2를 구하였다. 이렇게 계산한 q1(hat)과 q2(hat)로 직교 행렬(orthogonal matrix)을 만들 수 있는데, 간단히 q1(hat), q2(hat), ... qn(hat)을 순서대로 column vector로 삽입하면 된다. 

우리는 기존의 행렬 A로부터 직교행렬 Q를 만들었다. 이미 언급했지만 여기서 column space에 관한 얘기를 한 번 더 해보자. column space라는 것은 column vector들의 가능한 모든 선형 조합(Linear Combination)을 통해 형성하는 공간을 의미한다. 그렇다면 원래의 행렬 A와, A로부터 만든 직교행렬 Q와는 무슨 관계가 있을까? A와 Q의 column space는 똑같은 공간을 공유한다. 즉 원래의 행렬 A의 column vector들은 column space의 기저(basis)이며, 선형 조합을 통해 column space를 형성한다. 마찬가지로 Q의 column vector들도 기저(basis)로써 A와 같은 공간을 형성하는데, 기저가 정규직교벡터(orthonormal vector)이기 때문에 A보다는 계산 등에 훨씬 유리하다. 정리하자면 A의 column space의 기저(basis)를 보다 효율적이고 최적화된 기저로 만드는 방법이 그람-슈미트 방법(Gram-Schmidt Process)이라고 생각하면 된다. 

MATLAB구현을 보기 전에 q1(hat)과 q2(hat)가 직교인지 확인해보자. 내적(dot product)을 하여 결과 값이 0이 나오는지 확인하면 된다. 

내적 결과 값이 0이므로 q1과 q2가 직교한다는 사실을 확인했다. 

아래 그림은 위의 q1과 q2를 MATLAB을 이용하여 구현한 것이다. 

Fig. 7 Gram-Schmidt Process를 이용한 정규직교벡터의 그래프

Fig. 7은 식 (8)의 벡터 a, b와 이를 그람-슈미트를 이용하여 정규직교벡터로 만든 q1(hat), q2(hat)를 그래프로 나타낸 것이다. 보다시피 원래의 벡터 a와 b는 독립이며 노란색으로 표현된 column space를 "span"할 수 있다. 그러나 a와 b의 선형 조합(Linear combination)을 이용하여 column space를 표현할 경우 계산상에 많은 불리함이 있다. 

보라색과 하늘색 벡터는 a와 b를 정규직교벡터로 만든 q1(hat)과 q2(hat)이다. 앞서 말했듯이 q1(hat)은 a를 그대로 대입하고 정규화 했기 때문에 a와 같은 선상에 위치한 것을 볼 수 있다. q1(hat), q2(hat)는 a와 b로 형성했던 column space와 같은 공간에 위치한 것을 볼 수 있으며, 같은 column space를 "span"하더라도 계산상에 있어 훨씬 유리한 점이 많다. 이 점에 대해서는 지난 강의 Lecture 17-(1)에 언급해 놓았으니 참고하기 바란다. q1(hat)과 q2(hat)는 90도 각도를 이루고 있음을 볼 수 있다. Fig. 7에 보이는 그래프에서는 완벽한 90도가 아닌 것 처럼 보일 수는 있으나 이것은 MATLAB그래프의 가로 세로의 비율(aspect ratio)과 바라보는 각도때문에 왜곡이 생겨서 그렇다. 실제로는 90도를 이루고 있다. 

직교성을 확인하기 위해 MATLAB에서 계산한 q1(hat)과 q2(hat)를 실제로 내적하면 정확하게 0이 안나오는 경우가 생긴다. 이는 컴퓨터로 계산할 때 발생하는 round off 에러 때문인데, 컴퓨터의 수치 정밀도 때문에 발생하는 것이다(자세한 것은 구글 참조). 실제로 Fig. 7의 q1(hat)과 q2(hat)의 내적을 계산하면 1.6653e-16 이라는 수치가 나오는데, 엄청나게 작은 수 이므로 0으로 간주하는 것이다. 아래의 첨부된 MATLAB 코드를 참조하여 실제로 구현해서 확인해보는 것을 추천한다. 

- 3D space

이번에는 a, b에 이어 c가 추가된 3차원 column space에 대한 그람-슈미트 과정(Gram-Schmidt Process)을 수행해보도록 하자. 벡터 c는 아래와 같다. A는 c가 추가된 행렬을 나타낸다. 

q1과 q2는 이미 구했으니 c와 관련된 q3만 구하면 된다. 식 (6.3)을 이용하여 계산해보자. 

계산하다보니 숫자가 좀 커졌지만, 어쨋든 q3를 구하였다. 이제 정규화(normalization)를 통해 q3를 정규직교벡터로 만들어보자. 

이렇게하여 a, b, c로부터 정규직교벡터 q1(hat), q2(hat), q3(hat)를 만들었다. 직교행렬(orthogonal matrix)을 만드는 것은 식 (11)과 같기 때문에 넘어가도록 하겠다. 직교성을 확인하기 위해 q1(hat), q2(hat)와 내적하는 것은 MATLAB을 이용하거나 직접 해보길 바란다. 아래 그래프는 식 (13)의 벡터와 이에 대한 그람-슈미트 과정을 통해 얻은 정규직교벡터를 나타낸다. 

Fig. 8 식 (13)의 벡터와 그들의 정규직교벡터 그래프

Fig. 8을 보면 기존의 독립 벡터 a, b, c는 3차원 공간을 "span"하기는 하지만 크기도 제각각이고 column space인 3차원 공간의 기저(basis)가 되기엔 뭔가 최적화 되어 있지 않아 보인다. 반면 그람-슈미트 과정을 통해 만든 정규직교벡터 q1(hat), q2(hat), q3(hat)는 정규화된 동일한 크기의 벡터이고 서로 완벽하게 직교(orthogonal)를 이루는 모습을 볼 수 있다. 아래는 이를 구현한 MATLAB 코드이다. 

이번 포스팅에서는 3차원 정규직교벡터인 q3까지 구하였다. 하지만 이전에도 언급했듯이 4차원, 5차원, n차원의 벡터에 대해서도 계산은 가능하다. q1->q2->q3로 가면서 계산하는 패턴은 동일하기 때문에 n차원 그람-슈미트 방법에 대한 구현도 어렵지않게 할 수 있을 것이다. 

6. QR분해(QR decomposition)

- QR decomposition basic

마지막으로 살펴볼 내용능 지금까지 계산했던 그람-슈미트 방법(Gram-Schmidt Process)을 행렬로 정리하는 것이다. 이를 QR 분해(QR decomposition, QR factorization)라고 한다. 그러나 여기에선 그리 많은 양을 다루진 않고 간략히 살펴보고 넘어가도록 하겠다. 나중에 기회가 되면 따로 정리하도록 하고 일단 이런게 있구나 정도만 보고 넘어가면 될 것 같다. 

우리는 지난 Lecture 4에서 A=LU 분해(A=LU decomposition)를 배웠다. A라는 행렬을 소거 행렬(elimination matrix)을 통해 삼각행렬(triangular matrices)들의 곱으로 분해해서 표현하는 방법인데, QR 분해 역시 마찬가지로 원래의 A행렬을 Q행렬과 R행렬의 곱으로 분해하여 표현하는 방법이다. 여기서 Q행렬은 우리가 지금까지 그람-슈미트 방법을 통해 구했던 직교 행렬(orthogonal matrix)을 의미하며, R행렬은 A와 Q를 연결시켜주는 행렬이라고 생각하면 된다. 특히 R행렬은 상삼각행렬(Upper triangular matrix)의 형태를 띄고 있는데, 지금부터 이 R행렬이 무엇이고 왜 상삼각행렬의 모양으로 하고 있는지 알아보자. 

행렬 A와 Q, R은 아래와 같이 나타낼 수 있다. 

위의 식 (16)을 보고 어떤 사람들은 이렇게 생각할지도 모르겠다. 아까 분명히 Q행렬을 만들 때 q1, q2, ... 들을 순서대로 Q의 column vector에 삽입하면 된다고 했는데, 왜 갑자기 Q가 m x m이 되는 거지? 사실 식 (16)은 QR 분해를 할 때 A가 정방행렬(square matrix)의 형태 뿐만 아니라 직사각행렬(rectangular matrix)의 형태까지 고려한 일반적인 형태이다. 직사각행렬인 경우 계산 과정이 약간 더 복잡해진다. 이에 대한 자세한 내용은 QR분해 위키를 참조하도록 하고 일단 정방행렬인 경우만 고려하여 생각하도록 하자. 

우선 A행렬의 column vector들을 a1, a2, ...로 표현했는데, 위에서 설명한 a, b, c, 등의 벡터를 나타낸다. Q행렬은 A와 똑같은 column space를 형성하는 기저(basis)들로 구성되어 있으며 정규직교벡터들로 구성되어 있다. 중요한건 R행렬인데, 각 원소들은 a1, a2 등의 벡터들과 Q행렬의 column vector인 q1, q2 벡터들과의 내적으로 구성되어 있다. 그런데 대각선을 기준으로 아래쪽 원소들은 전부다 0이 된다. 왜 그럴까? 

아래쪽 원소의 식을 보면 a1과 q2, 그리고 a2와 q3와 같이 q벡터와 이전 index의 벡터들과 내적을 한다. 어째서 어떤 q벡터와 이전 index의 a벡터와 내적을 하면 0이 될까? 그것은 그람-슈미트의 계산 과정과 관련이 있다. 식 (6.3)이나 Fig. 6을 보면 우리가 벡터 c로부터 q3를 만들 때 먼저 q1과 직교하게 만들고, 그 다음 q2와 직교하게 만들어서 q3를 생성하게 된다. 이 말은 qn을 만들 때 qn-1과는 반드시 직교(orthogonal)해야하고 따라서 q1, q2등과 대응 되는 a, b, c, ... 등의 이전의 모든 벡터와는 직교해야함을 의미한다. 따라서 아래쪽 삼각형 원소들은 모두 0이 되고 R은 상삼각행렬(upper triangular matrix)의 형태가 된다. 

- QR matrices and MATLAB function

Q행렬은 그람-슈미트 과정을 통해 얻은 q벡터들을 Q의 column vector들로 삽입하여 간단히 얻을 수 있다고 하였다. 그렇다면 R행렬은 어떻게 구할 까? A행렬이 정방행렬(square matrix)이라고 가정할 때, 아래의 식을 통해 간단히 얻을 수 있다. 

결국 원래 행렬 A에 Q transpose행렬을 곱해주면 R을 얻을 수 있다. 아래 그림은 식 (13)을 MATLAB을 이용하여 계산한 결과다. 

Fig. 9 식(13)의 QR decomposition

기존에 구했던 q1, q2, q3를 이용하여 직교행렬 Q를 만든 다음, 식 (17)과 같이 R을 계산하고 Q와 R을 곱하여 식이 맞는지 확인하였다. 결과적으로 A와 같음을 볼 수 있다. 

그런데 MATLAB에는 행렬 A만 있으면 기본적으로 QR decomposition을 해주는 함수가 있다. 명령어는 " [Q R]=qr(A) " 와 같이 치면 되고 자동으로 Q와 R행렬을 계산해준다. 그러나 Fig. 9에서 계산한것과 부호 등이 다른 경우가 있는데, 이는 구현 알고리즘이 달라서 발생하는 현상이며 결국은 같은 기능을 하는 것이다. 실제 구현에서는 Householder reflection방법을 많이 사용하는데, 수치계산에 있어서 그람-슈미트보다 훨씬 안정적이라고 한다. 자세한 사항은 QR분해 위키를 참조하자. 아래는 MATLAB내장함수인 qr()을 이용하여 계산한 결과다. Fig. 9의 결과와 비교해보자. 

Fig. 10 MATLAB내장 함수를 이용하여 수행한 QR decomposition

7. 마치며

이번 포스팅에선 그람-슈미트 방법(Gram-schmidt Process)에 대해서 공부하였다. 그람-슈미트는 기존 행렬의 column space를 이루는 기저(basis)를 계산에 있어서 보다 효율적이고 최적화된 기저로 바꾸는 방법이며, 바뀐 기저는 정규직교벡터(orthonormal vector)의 형태를 띈다. 이는 계산 상에 있어 여러 모로 효율적이다. 정규화된 단위 벡터이기 때문에 크기는 1이며, 방향 성분만을 나타내는 벡터이다. 따라서 overflow, underflow등과 같은 문제에 있어 자유롭고, 계산을 간단하게 해주는 특징을 보인다. 

그람-슈미트 방법은 기본적으로 투영(projection)의 개념을 이용하여 계산되며, 이 그람-슈미트 방법은 이후 SVD(singular value decomposition)에 응용 되기도 하니 잘 알아두도록 하자. 

이번 강의에서 배울 내용은 직교행렬(Orthogonal Matrix)과 그람 슈미트 과정(Gram-Schmidt Process)이다. 먼저 이들을 간략히 설명하면 다음과 같다. 직교 행렬은 모든 column vector가 자기 자신을 제외한 나머지 모든 column vector들과 직교이면서 크기가 1인 단위 벡터들로 구성된 행렬을 의미한다. 그리고 그람 슈미트 과정은 임의의 독립 행렬(independent matrix)로부터 각 column vector가 정규직교(Orthonormal)한 벡터들로 구성된 직교 행렬을 만드는 과정 혹은 방법을 의미한다. 이 설명만 가지고는 이해하기가 어려울 수 있으니 차근차근 공부해 보도록 하자. 먼저 정규직교벡터(Orthonormal vector)에 대해 공부해보자. 

1. 정규직교벡터(Orthonormal Vector)

- 단위 벡터(Unit Vector)

정규직교벡터(Orthonormal Vector)를 알아보기 전에 먼저 단위 벡터에 대해 먼저 알아보도록 하자. 

일반적으로 어떤 벡터는 크기와 방향 성분을 가진다. 예를 들어 벡터 v가 v=[2 1]T라고 했을 때, v는 바닥에서 약 26.5도 회전한 쪽으로의 방향을 가리키고 있고, √5의 크기를 갖는다. 여기서 어떤 scale상수를 곱해서 벡터의 길이를 늘린다고 가정해보자. scale상수가 3이면 3 x v = [6 3]T = √45 = 3√5의 크기가 된다. 즉 원래 벡터의 길이에 곱해진 scale만큼 길이가 더 늘어나게 된다. 

그렇다면 단위 벡터(Unit Vector)란 무엇인가? 정의하자면 길이가 1인 벡터를 의미한다. 즉 길이가 1이라는 것은 단위 길이(Unit length)를 의미하며 오직 방향성분만을 나타내는 벡터이다. 우리가 길이를 나타낼 때 표준 단위계(SI)에선 m(meter)을 이용하여 길이를 표현한다. 가령 2미터를 나타낼 때 "2m"과 같이 숫자 뒤에 m을 붙여주는데, 이때 m은 길이의 단위를 나타낼 뿐 실제 길이에 어떠한 영향도 끼치지는 않는다. 

단위 벡터는 바로 "m"과 같은 역할을 하는 것이다. 힘의 크기와 방향 등을 벡터로 나타낼 때 단위 벡터(Unit vector)는 크기 성분에는 전혀 영향을 끼치지 않는다. 방향 성분만을 나타내기 때문에 어떤 scale상수를 곱하여 길이를 늘린다고 했을 때 그 늘린 길이가 scale상수 그 자체이다. scale이 3, 벡터 v가 단위 벡터라고 했을 때 3 x v의 길이(크기)는 3이다. 

일반 벡터를 단위벡터로 만들기 위해선 아래 식과 같이 기존의 벡터를 벡터의 크기로 나누어주면 된다. 

식 (1)을 참고하여 벡터 v=[2 1 3]T를 단위벡터(Unit vector)로 만들어보자. 

우리는 이러한 단위 벡터를 정규화 벡터(normalized vector)라고도 한다. 즉 서로 다른 스케일을 가지고있는 벡터들을 동일한 스케일에서 바라보기위해 벡터의 크기로 나누어 정규화(normalization)한 벡터를 의미한다. 

- 정규직교벡터(Orthonormal vector)

직교 벡터(orthogonal vector)는 알다시피 벡터 사이의 각도가 90도, 즉 직각(perpendicular)을 이루는 벡터를 말한다. 즉 어떤 a라는 벡터가 있고, a와 직각인 벡터 b가 있을 때 a와 b벡터를 우리는 직교벡터라고 하며 이때 a와 b의 내적(dot product)은 0이 된다. 따라서 직교 벡터는 어떤 하나의 벡터로는 정의할 수 없고 반드시 한 쌍 이상의 벡터로부터 정의되어야 한다. 

그렇다면 정규직교벡터(orthonormal vector)란 무엇일까? 이는 바로 직교 벡터(orthogonal vector)이면서 단위 벡터(unit vector)인 벡터를 말한다. 즉 두 벡터가 90도의 각도를 이루고, 각 벡터의 길이(크기)는 1인 방향성분만을 나타내는 벡터를 우리는 정규직교벡터(orthonormal vector)라 한다. 이를 수식으로 나타내면 아래와 같다. 

Orthonormal vector를 각각 qi, qj라고 했을 때, qi는 자기 자신에게는 직교(orthogonal)하지 않는다. qi를 자기 자신과 곱하면, 즉 자기 자신과 내적(dot product)하면 그 결과값은 1이 된다. 이것이 의미하는 것은 q는 벡터의 크기가 1인 단위 벡터(unit vector)라는 의미다. 단위 벡터인 식 (2)의 v hat을 제곱해보자. 결과는 4/14 + 1/14 + 9/14 = 1이 될 것이다. 이처럼 벡터들이 서로 직교(orthogonal)하면서 동시에 정규화된 벡터이기 때문에 ortho-normal이라는 이름을 사용하는 것이다. 

자기 자신을 제외한 나머지 모든 벡터들과는 직교(orthogonal)한다. 즉 자기 자신을 제외한 나머지 벡터들과의 내적(dot product)결과가 0이 되는 것이다. 아래 그림은 이러한 정규직교벡터(orthonormal vector)의 한 예를 나타낸다. 

Fig. 1 정규직교벡터(orthonormal vector)의 예

Fig. 1은 sin과 cos으로 이루어진 벡터를 나타낸다. 이들 벡터 a, b의 길이는 각각 1이며 둘 사이의 각도는 90도이다. 두 벡터가 직교(perpendicular)하며 각 벡터의 길이는 1로써 방향성분만을 나타내므로 이들은 정규직교벡터이다. 

이러한 정규직교벡터들을 행렬의 column vector에 삽입하면 직교행렬(orthogonal matrix)이 된다. 즉 Q를 직교행렬이라고 했을 때 orthonormal vector들이 Q의 정규직교기저(orthonormal basis)가 되는 것이다. 이러한 정규직교기저는 선형대수의 행렬 계산에 있어 좋은 결과를 보여준다. 특히 선형대수계산을 연구하는 분야인 Numerical Linear Algebra의 대부분의 연산은 이러한 orthonormal vector를 기반으로 이루어진다. 이들은 수치 연산을 하는 과정에서 값이 무한정 커지거나 작아져서 발생하는 overflow나 underflow문제에 있어서 자유롭다. 왜냐하면 크기에 영향을 미치지않는 단위 행렬(unit vector)성분을 가지고 있기 때문이다. 이것이 정규화(normalization)의 힘이다.

2. 직교행렬(Orthogonal Matrices)

- Basic of Orthogonal Matrix

직교행렬(orthogonal matrix)은 행렬의 row와 column vector들이 자기 자신을 제외한 나머지 모든 row, column vector들과 직교(perpendicular)이면서 동시에 단위 벡터(unit vector)인 행렬을 의미한다. 즉 orthonormal vector들을 행렬 Q에 집어넣은 것과 같다. 아래 식과 같이 말이다.  

식 (4)는 orthonormal vector를 행렬 Q에 column vector로써 삽입한 형태이다. 이때 임의의 벡터 qi는 자기 자신을 제외한 나머지 벡터들과 직교(perpendicular)하다. 즉 식 (3)의 규칙을 따르는 것이다. 식 (3)의 규칙을 확인하기 위해서는 Q transpose와 Q를 곱한 값을 보면 알 수 있다. 

식 (5)는 Q transpose와 Q의 곱셈 결과를 나타낸다. Q transpose는 q transpose를 Q의 row vector로 삽입한것과 같다. 이를 Q와 곱하면 어떤 결과가 나오는가? 바로 단위 행렬(Identity matrix)이다. Q transpose의 row1과 Q의 col1의 곱은 자기 자신과의 곱셈이다. 따라서 모든 row(i)와 col(j), (i=j)의 곱셈은 자기 자신과의 곱셈이기 때문에 결과 행렬의 대각 성분은 1이 된다. 반면 나머지 벡터끼리의 곱셈은 직교(orthogonal)하기 때문에 0이 되어 결과적으로 단위 행렬이 나오는 것이다. 결국 

는 

와 마찬가지로 모든 row와 column 벡터들 끼리의 내적(dot product)을 확인하는 것이다. 식 (3)의 정의와 맞는 것을 볼 수 있다. 

이렇게 하여 우리는 orthonormal column을 가진 orthogonal matrix를 배웠다. 사실 Q에 대한 더 정확한 표현은 orthonormal matrix이다. 각 벡터들이 orthogonal이 아닌 orthonormal한 벡터를 가지고 있기 때문이다. 그러나 무슨 이유에서인지 표현은 항상 orthogonal matrix로 한다. 

- Square Orthogonal Matrix

직교 행렬(orthogonal matrix)이면서 정방행렬(square)인 경우의 가장 대표적인 예는 단위행렬(identity matrix)이다. 단위행렬의 각 column vector는 자기 자신을 제외한 나머지 벡터들과 90도의 각도를 이루면서 각각의 크기는 1이다. 이를 시각화하면 아래 그림과 같다. 

Fig. 2 직교행렬(orthogonal matrix)이면서 정방행렬(square matrix)인 단위행렬(identity matrix)의 시각화

Fig. 2는 어디서 많이 본 그림일 것이다. 바로 표준 기저(standard basis)이다. x축은 y축과 z축에 각각 수직(perpendicular)이며, y는 x와, z축에, z는 x와 y에 각각 수직이다. 각 벡터끼리 내적(dot product)을 하면 0이 되는 것을 볼 수 있다. 또한 각 축의 기저는 정규화(normalized)된 크기인 1이다. 이러한 표준 기저의 선형 조합(Linear combination)을 통해 우리는 3차원 공간의 모든 벡터, 점 등을 정의할 수 있다. 

이와 같이 직교 행렬이 정방행렬일 경우 한 가지 흥미로운 특성을 갖는다. 그것은 바로 transpose가 역행렬(inverse matrix)과 같다는 것이다. 다시 정리해보자면

정규직교벡터(orthonormal vector)로 구성된 직교 행렬(orthogonal matrix) Q가 row의 수와 column의 수가 같은(m=n) 정방행렬(square)인 경우,  의 관계에 의해서 Q의 transpose는 Q의 역행렬(inverse matrix)이 된다. 즉

사실 식 (5)를 잘 살펴보면 당연하다. Q transpose와 Q를 곱했을 때 단위행렬이 된다는 것은 Q가 정방행렬인 상황에서 Q transpose가 당연히 역행렬이어야 한다. 예를 한 번 들어보자. 우리는 지난 Lecture 5에서 행 교환(row exchange)연산을 해주는 치환행렬(permutation matrix)에 대해 공부했었다. 치환행렬은 정규직교벡터로 구성된 직교 행렬(orthogonal matrix)이다. 아래 식을 보자. 

식 (6)의 치환행렬(permQ)의 column vector나 row vector들은 각자의 크기는 1이면서 자기 자신을 제외한 나머지 벡터들과는 수직(perpendicular)이다. 이제 여기에 Q의 transpose를 곱해보자. 결과는 아래와 같다. 

직교 행렬 Q에 Q transpose를 곱했더니 단위행렬이 나오는 것을 볼 수 있다. 따라서 Q transpose는 Q의 역행렬과 같다. 

한 가지 예를 더 들어보자. Fig. 1과 관련이 있는 예다. 

식 (8)은 cos과 sin으로 이루어진 직교 행렬(orthogonal matrix)이다. column 벡터들을 보면 각각 col1=[cos sin]T, col2=[-sin cos]T인데, 둘은 Fig. 1에 보이는 것과 같이 직교하며 내적(dot product)을 하면 0이 된다. 각 column vector의 크기는 1이며, 크기 구하는 식에 대입해보면 바로 알 수 있다. 

한 가지 예를 더 들어보자. 아래의 행렬은 직교 행렬인가? 

분명 column 혹은 row vector를 비교해보면 직교 벡터를 가지고 있다. 그러나 각 벡터의 길이가 1이 아니다. 어떻게 이들의 길이를 1로 만들어줄 수 있을까? 위의 단위 벡터 편에서 단위 벡터를 만들기 위해선 벡터의 크기로 나눠주면 된다는 것을 배웠다. 마찬가지로 벡터의 크기로 행렬 원소 전체를 나눠주면 된다. 다음 식과 같이 말이다. 

식 (11)의 임의의 qi의 길이(크기)를 계산해보면 √(1/2+1/2)=√(1)=1이 되는 것을 알 수 있다. 사실은 column 1과 column 2가 직교(orthogonal)하지만, 크기가 다를 경우가 있다. 따라서 보다 정확하게 말하자면 column 1은 column 1의 크기로, column 2는 column 2의 크기로 각각 나누어줘야 한다. 

이제 마지막 예를 들어보도록 하겠다. 다음 행렬을 살펴보자. 식 (10)의 행렬을 반복하여 만든 행렬이다. 

식 (12)는 식 (10)의 행렬 Q의 각 원소들에 Q를 대입한 것과 같은 형태이다. 먼저 직교성(orthogonality)을 계산해보면 Q의 임의의 column qi와 나머지 column vector와 내적을 하면 결과는 0이 된다. 그러나 각 column 혹은 row vector의 길이는 1이 아니다. 즉 직교성은 만족하지만, 단위 행렬(unit vector)속성은 만족하지 않는다. 따라서 직교행렬이 되기 위해선 식 (11)과 같이 단위 행렬로 만들어야 한다. 이를 위해서 해당 column 혹은 row 벡터의 길이(length or magnitude)로 자기 자신을 나누어주면 된다. 

식 (13)의 어떠한 벡터의 크기를 계산해도 1이 된다. 따라서 식 (13)은 직교 행렬(orthogonal matrix)이다. 식 (13)의 행렬을 특히 Adhemar matrix이라고 부른다. 이에 대한 자세한 것은 구글을 참고하자. 여기선 그냥 넘어가도록 하겠다. 

- Rectangular Orthogonal Matrix

지금까지는 직교 행렬(Rectangular Matrix)이 정방행렬인 경우만 살펴보았다. 이번엔 임의의 직사각 형태인 직교 행렬을 살펴보도록 하자. 아래 식은 직사각 형태의 직교 행렬을 나타낸다. 

식 (14.1)일 때는 그저 단순히 하나의 단위 벡터(unit vector)이다. 여기에 col1벡터와 독립인 col2벡터를 추가하여 (14.2)와 같은 직사각형 형태(Rectangular) 식을 만들었다. 이때의 column vector들은 3차원 공간에서 2차원 부분 공간(subspace)의 column space를 이루는 기저(basis)가 된다. 여기에 세 번째 column vector를 더하면 (14.3)과 같이 된다. 

사실 여기서 말하고자 하는 것은 (14.1)에서 (14.2)로 넘어갈 때, 그리고 (14.2)에서 (14.3)으로 넘어갈 때 어떻게 직교벡터(orthogonal vector)를 만드느냐이다. 특별한 알고리즘이나 방법이 없이는 우리의 직관에 의해서 직교 벡터들을 만들어서 기존의 행렬에 더해줘야 한다. 그러나 이는 행렬의 크기가 커질 수록 너무나 어려운 일이다. 이후에 설명할 그람-슈미트 과정(Gram-Schmidt Process)은 이러한 직교 행렬을 만들어주는 특별한 방법이다. 즉 임의의 독립된 column vector들로 구성된 행렬, 즉 독립(independent)인 행렬(matrix)이 있을 때, 이 독립인 행렬을 직교행렬(orthogonal matrix)로 만들어주는 방법이다. 

본격적으로 그람-슈미트 과정을 공부하기 전에 먼저 직교 행렬을 이용하여 연산을 했을 때 어떠한 이점이 있는지 살펴보도록 하자. 

- Advantage of using Orthogonal Matrix

직교 행렬(orthogonal matrix) Q를 활용하여 계산하면 몇 가지 이점이 있다. 먼저 수식이 굉장히 간단해진다. 우리가 어떤 벡터 b를 행렬 A의 column space로 투영(projection)시키고 싶을 때, 투영행렬(projection matrix)을 통해 이를 할 수 있음을 Lecture 15에서 배웠다. 투영 행렬의 식을 다시 상기시켜보자. 

식 (15)의 투영행렬식은 얼핏 보면 약간 복잡해 보이긴 한다. 그렇다면 A대신 Q를 이용하여 투영행렬을 만들게 되면 식이 어떻게 변할까? 

Q는 정규직교(orthonormal) column vector들로 이루어진 직교 행렬(orthogonal matrix)이다. A대신 Q를 이용하여 투영 행렬(projection matrix)를 만들었더니 식 (16)과 같이 식이 굉장히 간단해졌다. 괄호 안의 Q transpose Q가 식 (5)에서 본 것과 같이 단위행렬이 되기 때문이다. 따라서 괄호 안의 식은 없어지는 것과 마찬가지가 되고 결국 양 끝에 Q와 Q transpose만 남게 된다. 이때 Q가 임의의 직사각행렬(rectangular matrix)이라면, (16)의 결과 행렬은 대칭 행렬(symmetric matrix)이 된다. 

만약 Q가 정방행렬(square matrix)이라면 어떨까? 이 경우엔 식이 훨씬 더 단순해진다. 우리는 위의 노란박스에서 Q가 정방행렬일 경우 Q의 전치(transpose)는 Q의 역행렬이라고 배웠다. 식 (16)에서 Q의 투영행렬은 

이 되므로 결과적으로 단위 행렬이 된다. 식은 아래와 같다. 

왜 Q가 정방행렬일 경우 투영행렬이 단위 행렬이 되는지 잘 생각해보자. 투영 행렬은 임의의 벡터 b를 행렬 A 혹은 Q의 column space로 투영(column space의 가장 가까운 벡터로의 매칭)시키는 역할을 한다. 그런데 Q가 정방행렬이 되어버리면 Q의 column space가 전체 공간과 같아져버리게 된다. 따라서 임의의 벡터 b는 전체 공간인 Q의 column space에 이미 존재하기 때문에 투영 자체가 의미가 없어져버린다. 그래서 정방행렬(square matrix)인 직교 행렬(orthogonal matrix)의 투영 행렬(projection matrix)이 단위 행렬이 되는 것이다. 

마지막으로 투영 행렬의 특성중 하나인 

를 확인해보자. 투영시킨 벡터를 다시 투영해도 그 결과는 같다는 것 말이다. 식 (16)을 기준으로 이 특성을 다시 써보면 아래와 같다. 

식 (18)의 밑줄 친 부분이 단위행렬이 되므로 결과는 P와 같다. 

이와 같이 기존의 임의의 행렬 A에 대한 해를 구하는 식은 Q를 이용할 경우 훨씬 간단해진다. Lecture 15-(1)에서 배웠던 overdetermined case의 해를 구하는 식을 Q를 이용하여 정리하면 아래와 같이 간단하게 정리된다. 

앞의 Q transpose Q가 단위 행렬이 되어 사라지고 뒤의 식만 남게된다. 결과적으로 Q를 이용할 경우 해(solution) x hat의 각 원소들은 Q transpose와 b의 내적(dot product)연산에 의해 간단히 정의된다. 

3. 마치며..(continue)

이번 강의에선 그람-슈미트 과정을 배우기에 앞서 필요한 선행 지식인 직교행렬에 관해 공부하였다. 직교행렬(orthogonal matrix)은 정규직교벡터(orthonormal vector)들로 이루어진 행렬이며 계산을 간단하게 해주는 특징이 있다는 것을 공부하였다. 또한 실제 계산에 있어서 정규화(normalized)된 직교(orthogonal) 벡터들을 이용하기 때문에 계산 결과값이나 overflow, underflow와 같은 문제에 있어서 훨씬 좋은 성능을 보인다. 

그러나 여기서 어떤 사람들은 이런 의문이 들수도 있을 것이다. A대신 Q를 이용해서 식을 만들면 좋은건 알겠는데, 대체 A랑 Q랑 무슨 관계지? Q가 좋긴 하지만 A대신 사용하게 되면 원래 식과는 완전히 달라지는거 아냐? 

이후 과정에서 더 자세히 설명하긴 하겠지만, A와 Q는 같은 column space를 공유하는 행렬이다. 즉 A의 column vector들을 기반으로 A와 똑같은 column space, 혹은 부분 공간(subspace)을 이루는 행렬 Q를 만드는 것이다(※이때 A는 반드시 독립이어야 함). 다시 말하면 원래 A가 가지고 있던 column vector들은 column space의 기저(basis)이긴 하지만, 최적의 기저는 아닐 가능성이 크다. 원래의 행렬 A의 column space의 기저(basis)를 보다 최적화된 기저로 만들어준다! 정도로 생각하면 될 것 같다. 

원래 그람-슈미트 과정(Gram-Schmidt Process)까지 이번 포스팅에서 다루려고 했으나, 내용이 너무 길어질 것 같아서 나누어서 하겠습니다. 다음 강의(17-(2))에서는 직교행렬에 이어 그람-슈미트 과정을 다루도록 하겠습니다. 

우리는 지난시간에 투영(Projection)에 대해 공부하였다. 이는 해가 존재하지 않는 Overdetermined case의 선형방정식에 대한 근사해(approximate solution)를 구하는 것이 목적이며 x hat을 근사해로써 구했다. 이제 해야 할 일은 이 투영을 어떻게 응용할 수 있는지를 알아보는 것이다. 우리는 이 투영에 대한 응용으로써 최소자승법(Least square method)을 공부해볼 것이다. 먼저 지난 강의 Lecture 15에서 배운 내용 중 투영행렬(Projection matrix)에 대해 간략히 살펴보도록 하자. 

1. 투영(Projection)

- Two extreme cases

벡터의 투영에 대해 두 가지 극단적인 경우를 살펴보자. 

지난 강의에서 배운 것과 같이 투영 행렬의 식은 다음과 같다. 

투영 행렬(Projection matrix)은 말 그대로 어떤 벡터를 다른 어떤 공간으로 투영시키는 것을 의미한다. 즉 곱해지는 벡터 b를 column space에 존재하는 벡터 중 가장 가까운 점, 가장 가까운 벡터로 바꿔주는 역할을 한다. 그렇다면 이러한 경우엔 어떨까? 벡터 b가 이미 column space에 존재한다면? 혹은 벡터 b가 column space와 수직(perpendicular)이라면? 이러한 두 가지 극단적인 경우의 벡터에 대해 투영 행렬을 곱해주면 어떤 결과가 발생할까? 

먼저 이미 벡터 b가 column space에 존재하는 경우를 살펴보자. 이때는 투영 행렬 P에 b를 곱하면 그대로 b를 얻는다. 즉

b는 column space상에 존재하는 벡터라고 했다. 그렇다면 일반적으로 column space상에 존재하는 벡터는 어떻게 나타내는가? 바로 column vector들의 선형 조합(Linear combination)으로 표현한다. 이것을 표현한 것이 바로 Ax다. x의 각 원소들이 A의 column vector에 계수로 곱해져서 선형 조합이 되는 것이다. 식 (1)에다 b, 즉 Ax를 곱하면 식의 가운데 부분이 캔슬되어 결국 그대로 b만 남는다. 결과적으로 투영행렬이 이미 column space에 존재하는 벡터 b를 그대로 유지시킨 것이다.

다음으로 벡터 b가 column space와 수직(perpendicular)인 경우는 투영 행렬 P에 b를 곱하면 그 결과는 0이 된다. 

식 (3)의 경우엔 왜 이러한 결과가 나올까? 이는 부분 공간(subspace)과 연관이 있다. Pb=0이 된다는 것은 b가 column space가 아닌 다른 공간에 존재한다는 것이다. 그렇다면 그 다른 공간은 어떤 공간인가? 바로 Left null space이다. 우리는 Lecture 14에서 Left null space는 column space와 수직임을 배웠다. 따라서 column space에 수직인 b는 곧 Left null space에 존재하는 것이다. 

또한 투영 행렬 P와 벡터 b를 곱한다는 것은 P의 row vector들과 b의 column vector와의 내적(dot product)을 의미한다. 이때 P는 여러 개의 row vector가 될 것이므로 결국 P의 row space와 직교한 것이고 그 결과는 0이 된다. 직교할 때 column space에서 b와 가장 가까운 벡터는 영벡터(zero vector)뿐이다. 결과적으로 투영 행렬이 벡터 b를 없애버린 셈이다. 

위의 내용을 그림을 이용해 이해해보자. 

Fig. 1 Column space와 Left null space사이에서 벡터 b의 관계

Fig. 1에서 파란색 벡터 b가 바로 column space에 존재 하지 않는 b이다. 이 벡터 b를 column space에 투영한 벡터가 바로 빨간색 벡터 p가 되고, 투영 행렬 P에 벡터 b를 곱하여 p=Pb를 통해 투영시킨다. 

반대로 Left null space에 투영 시킨 벡터가 보라색 벡터인 e가 되며, e는 단위행렬에서 투영행렬을 뺀 (I-P)행렬에 b를 곱하여 투영시킨다. (I-P)는 P행렬로 투영시키는 공간과 직교하는 공간으로 투영시키는 역할을 한다. 이미 배운 것과 같이 P는 대칭(symmetric)이며 $P^2=P$이다. $(I-P)$역시 대칭이며, ${(I-P)}^2=(I-P)$를 만족한다. 

벡터 p와 e를 더하면 b가 된다. 즉 b=p+e이고 각 벡터를 투영 행렬과의 곱으로 표현하면 아래와 같다. 

요약하자면 p는 column space에, e는 column space와 직교(perpendicular)인 Left null space에 각각 존재하며, 벡터 b는 이들 두 공간에 존재하거나 혹은 그 사이에 존재할 수 있다. b는 투영행렬 P와의 곱인 p=Pb를 통해 p가 되고, e=(I-P)b를 통해 e가 된다. 

2. 최소자승법(Least Square Method)

- Basics of Least Square

우리가 배웠던 투영(Projection)은 미지수(unknown)보다 방정식(equation)이 더 많아서 이를 만족시키는 해가 존재하지 않을 때, 주어진 모든 방정식을 최대한 만족시키는 일반화된 해를 찾는 것이 그 목적이다. 그렇다면 어떠한 경우에 우리는 방정식이 미지수보다 많을 수 있을까? 바로 센서 들과 같은 장치로부터 많은 수의 데이터를 수집한 경우이다. 이때 얻은 많은 데이터들은 방정식의 계수로써 표현할 수 있고, 각 데이터들의 차원이 바로 미지수가 된다. 즉 수집한 데이터들을 기반으로 해당 시스템의 일반화된 표현식을 구하는 것이다. 

최소자승법(Least Square Method)은 수집한 데이터를 기반으로 이들 모두를 최대한 만족시키는 하나의 Line에 대한 식을 찾는 방법이다. 이렇게 찾은 Line을 통해 우리는 데이터에 대한 예측 뿐만 아니라 시스템의 특성까지 파악할 수 있다. 최소자승(Least square)이라는 말의 의미를 이해한다면 훨씬 느낌이 와 닿을 것이다. 이에 대해서는 잠시 후에 설명하기로 하고 먼저 아래와 같이 3개의 데이터를 얻었다고 가정해보자. 

Fig. 2 주어진 3개의 데이터 (1,1) (2,2) (3,2)

주어진 3개의 데이터는 (1,1) (2,2) (3,2)이다. 가로 축을 시간 t라고 하고 시간에 따라 얻은 데이터라고 생각해보자. 세로축은 b, 혹은 y이고 해당 시간에 얻은 실제 데이터 값으로 생각하자. (1,1)은 1초에 얻은 데이터의 값이 1이고, (3,2)는 3초때에 얻은 데이터의 값이 2라는 의미다. 여기서 우리가 하고자 하는 것은 저 데이터들을 잘 표현할 수 있는 하나의 직선(Line)을 찾는 것이다. 본격적으로 방법을 알아보기 전에 이 질문에 대해 한 번 생각해보자. 

왜 이러한 직선을 찾으려고 할까? 바로 시스템의 특성에 대한 분석과 미래 예측이 목적이다. 주어진 데이터가 주가의 시간에 따른 변화라고 가정해보자. 이때 최소자승법을 이용하여 데이터 집합을 잘 나타내는 Line을 찾으면 그 Line의 기울기 등을 통해 현재 상태를 파악할 수 있다. 또한 아직 획득하지 못한 미래의 데이터를 예측할 수도 있다. 물론 실제 문제는 이보다 훨씬 복잡하고 Line이 아닌 n차 방정식의 curve fitting을 활용해야 할 것이다. 어쨋든 최소자승법의 기본적인 목적은 분석과 예측이다. 

다시 우리 문제로 돌아와서, 위의 데이터의 경향을 가장 잘 나타내는 Line을 찾으려면 중학교때 배웠던 y=ax+b의 직선의 방정식의 파라미터인 a와 b를 찾으면 된다. 그러나 문자 표기가 좀 헷갈릴 수 있으니 우리 문제와 맞추기 위해 표기를 아래와 같이 조금 바꿔보도록 하자. 

y->b,  a->c,  x->t,  b->d로 각각 바뀌었다. 우리가 현재 알고 있는 값은 변수에 해당하는 t와 b이다. t와 b값들의 집합을 가지고 직선을 표현하는 파라미터인 c와 d를 찾아내야 한다. 이를 위해선 먼저 위 식을 Ax=b의 꼴로 나타내고 투영 행렬의 해를 구했을 때 처럼 x에 대해서 풀어주면 된다. 참고로 Ax=b에서의 x는 x=[c d]T를 나타낸다. 결과적으로 주어진 데이터를 기반으로 Ax=b의 식으로 표현하면 된다. 우리의 최종 목표는 직선을 나타내는 파라미터인 x를 알아내는 것이고, 이를 위해 행렬 A만 알아내면 거의 끝난 것이나 다름 없다. 

주어진 데이터(Fig. 2)와 식 (5)를 통해 우리는 3개의 방정식을 만들어낼 수 있다. 식 (5)의 t와 b에 Fig. 2의 주어진 데이터를 넣으면 다음과 같이 3개의 방정식을 만들 수 있다. 

이제 식 (6)의 3개의 방정식을 Ax=b의 꼴로 만들면 아래와 같다. 

식 (7)의 곱셈을 실제 수행하여 풀어써보면 다시 식 (6)과 같이 되는 것을 볼 수 있다. 

자 이제 행렬 A를 구했으니 거의 다 된 셈이다. 다시 한 번 말하지만 식 (7)은 미지수(unknown)보다 방정식(equation)이 많은 overdetermined case이다. 행렬 A의 column1과 column2는 독립(independent)이며 또한 column space의 기저(basis)이다. 그러나 우변의 벡터 b는 column space에 존재하지 않는다. 따라서 이 식을 완벽하게 만족시키는 해 x=[c d]T는 존재하지 않는다. 다만 가장 근사한 해, best solution을 구할 뿐이다. 실제 해를 구하는 방법은 Ax=b의 양변에 A transpose를 각각 곱해주면 된다. 즉

이 식 (8)을 이용하는 것이다. 지난 강의에서 많이 봤던 식일 것이다. 위의 식이 잘 이해가 가지 않는 사람은 반드시 Lecture 15를 공부하고 오길 바란다. 

어쨋든 완벽한 해가 존재하지 않는 다는 것은 Fig. 2를 기준으로 설명하자면 각 데이터 포인트들을 모두 완벽하게 관통하는 직선은 존재하지 않는 다는 것이다. 다만 각각의 데이터와의 에러를 최소화 하는 직선은 찾을 수 있다. 결국 각 데이터와 직선 사이의 에러의 총합이 최소가 되게끔 하는 선을 찾는 것이 우리가 찾고자 하는 것이다. 이것이 선을 결정 짓는 조건이다. 

그렇다면 구체적으로 여기서 말하는 에러(error)가 무엇일까? 식 (6)을 보면 우리는 주어진 3개의 데이터를 이용하여 3개의 방정식을 만들어냈다. 이때 c와 d에 대한 파라미터 값을 추정했다고 가정했을 때, 각각의 식에 대입하여 계산하면 좌변의 값이 나올 것이다. 이 좌변의 값과 우변의 b값 사이의 차이를 계산한 것이 여기서 말하는 에러(error)이다. 이때 중요한 것은 이 에러 값은 제곱을 해줘야 한다. 왜냐하면 에러 값으로 음수가 나올 경우도 있는데, 이 경우 값이 상쇄되어 에러 값이 0이 나올 경우도 있기 때문이다. 실제로는 에러가 엄청 큰데도 말이다. 따라서 음수 값이 나오지 않도록 항상 에러 값을 제곱해준다. 

이렇게 3개의 모든 방정식의 에러 값을 더했을 때 최종 에러값의 크기를 가장 작게 만드는 c와 d를 찾는 것이다. 이를 식으로 표현하면 아래와 같다. 

식 (9)를 식 (6)의 방정식을 이용해 기술하면 

와 같을 것이다. 이렇게 세운 식을 미적분학(calculus)을 적용하여 해를 구할 수도 있다. 즉 자승(square)은 2차식이고, 이를 두 변수인 c와 d로 각각 편미분(partial derivative)하여 식을 =0의 꼴로 정리하면 c와 d에 대한 식을 구할 수 있다(2차식의 기울기가 0인 부분이 최소값을 갖는 성질을 이용). 이 부분은 인터넷에 자료가 많이 있으며 나중에 기회가 되면 다루도록 하겠다. 

우리는 이미 식(6)을 식 (7)과 같이 Ax=b의 꼴로 만들었다. 에러를 최소화 시키는 (9)를 (7)에 대해서 정리하면 식은 아래와 같이 될 것이다. 식 (7)의 우변의 b를 좌변으로 이항하고, 이에 대한 길이를 구하고(norm-2) 이를 제곱해주면 된다.

Ax-b의 결과는 error 벡터가 나올 것이고, 이 벡터에 대한 길이는 에러의 총 크기를 나타낼 것이다. 이 에러 벡터에 대한 길이는 식 (9)에서  j=1 ~ m 각 방정식의 에러의 값들의 총 합과 같은데, (9)에서는 음수가 나오지 않도록 제곱을 해줬다. (10)에서도 같은 이유로 제곱을 해주는데, 사실 벡터의 길이를 2-norm으로 계산하면 루트(square root)가 씌워져서 나온다. 이 루트를 제거해주기 위한 이유로 제곱을 해주는 것도 있다. 

여기서 우리는 최소자승법(Least square method)의 의미를 파악할 수 있다. 최소(Least)라는 말은 Ax와 b사이의 에러를 최소화 해주기 위함을 의미하고, 자승(square)은 식 (10)에서 제곱함을 의미한다. 정의하자면...

정도로 정의할 수 있겠다. 

그렇다면 이 에러 벡터가 실제 그림에선 어떤 부분을 의미할까? 아래 그림을 살펴보자. 

Fig. 3 최소자승법을 통한 Line fitting

Fig. 3 은 Fig. 2의 데이터를 이용해 Line의 파라미터를 추정하고 이를 통해 Line을 표현한 모습이다. 붉은색 점은 원래 측정된 점들을 의미하고, 파란색 점은 Line fitting을 통해 예측된 점, 즉 측정된 점들과 이 점들이 Line에 수직(vertical)방향으로 대응되는 점들이다. 녹색 선은 측정값 b와 예측값 p사이의 에러(error)를 나타낸다. e=[e1 e2 e3]T에서 e1, e2, e3는 스칼라(scalar)값이며 총 에러는 각 에러의 자승(square)의 합으로 표현할 수 있다. 

식 (11)에 나타난 에러의 총 합이 우리가 최소화 하고자 하는 에러값이다. 

우리는 주어진 데이터를 이용하여 데이터들의 추세를 파악하고 예측한다. 이것은 통계학(statistics)의 한 부분으로도 볼 수 있으며 통계학 용어로는 회귀(regression)라고 부른다. 즉 이미 주어진, 혹은 측정한 데이터를 기반으로 데이터의 경향을 파악하고 미래를 예측하고자 하는 것이며 같은 목적성을 지니고 있다. 최소자승법은 결국 주어진 데이터를 이용해 회귀(regression)를 한 것이다. 여기서는 Line을 이용하여 fitting을 했기 때문에 선형 회귀(Linear regression)를 한 것이다. 

- Outliers in Least square

Fig. 3과 같이 데이터가 분포해 있을 경우엔 최소자승법이 대체적으로 데이터의 추세를 잘 반영하는 듯 보인다. 그러나 어떤 통계학자들은 최소자승법에 우려를 표했는데, 그것은 바로 어떤 한 점이 다른 대부분의 점들과 동떨어져 있을때이다. 이렇게 어떤 데이터가 동떨어져서 측정되는 경우는 그것이 실제 제대로된 측정값일 수도 있으나 대체적으로 쓸모없는 값, 즉 노이즈 데이터일 경우가 많다. 이렇게 다른 대부분의 데이터들의 분포에서 큰 거리를 두고 측정되는 소수의 데이터들을 우리는 아웃라이어(Outlier)라고 한다. 이러한 아웃라이어들은 대부분 잡음(noise)일 경우가 많다. 

Fig. 3의 데이터에 (0, 3)의 아웃라이어가 추가되면 보라색 라인은 어떻게 될까? 최소자승법은 모든 데이터에 대한 에러를 최소화 하는 방향으로 파라미터가 결정된다. 이때 당연히 아웃라이어와의 에러도 최소화 해야 하므로 Fig. 3과는 상당히 다른 양상을 보일 것이다. 아래 그림과 같이 말이다. 

Fig. 4 아웃라이어가 존재할 경우 최소자승법

Fig. 4는 (0, 3)의 아웃라이어가 존재할 경우 최소자승법을 보여주고 있다. 아웃라이어와의 에러까지 고려하다보니 Fig. 3와는 라인의 위치가 상당히 차이가 난다. 아웃라이어때문에 결국 전체적인 데이터의 경향을 잘 반영하지 못하게 되었다. 이를 overcompensate이라 한다. 이러한 아웃라이어에 따른 overcompensate문제를 해결하기 위한 RANSAC(Random Sample Consensus)등의 방법이 존재한다. 그러나 우리는 이러한 아웃라이어가 있다는 것 정도만 알고 이번 포스팅에서는 더 이상 다루지 않겠다. 

- Solution of Least square

Fig. 3은 식 (7)의 해를 구하여 라인을 표시한 것이다. 식 (7)을 다시 꺼내보자. 

행렬 A의 column vector는 독립(independent)이며 column space의 기저(basis)이다. 그러나 b벡터는 이 column space에 존재하지 않기 때문에 Ax=b의 해는 존재하지 않는다. 정확한 해는 존재하지 않지만 해를 구하기 위해선 b를 column space로 투영시키면 된다. b를 column space로 투영시킨 벡터를 p라고 하면 Fig. 3에 존재하는 빨간 점들 p1, p2, p3는 바로 벡터 p=[p1 p2 p3]가 된다. 즉 원래의 측정된 벡터 b=[b1 b2 b3]를 column space로 투영 시킨 벡터가 p=[p1 p2 p3]이다. 이때 p는 Fig. 3에서 직선 위에 존재하는 점들이다. 즉 b와 p를 Fig. 3에서는 점(p1, p2, p3)으로 보고 Fig. 1에서는 벡터 b와 p로 이해하면 된다.  

벡터 p는 A의 column space로 투영시킨 것이기 때문에 해가 존재한다. b를 p로 투영시켰기 때문에 식(7)은 아래와 같이 바뀐다. 

정확한 해가 아니라 최적해(best solution)이기 때문에 x에 hat을 붙여준다. 다시 한 번 말하자면 x hat은 해를 정확하게 만족시키는 직선이 아니다. 원래 다른 공간에 존재하던 b를 column space의 가장 근접한 위치로 끌고온 뒤 구한 해, 즉 추정된 해, 가장 근사한 해(estimated solution)를 의미한다. 

이제 식 (7)에 대한 x hat을 구해보도록 하자. Ax=b의 양변에 A transpose를 곱해주자. 

위의 식을 일반적인 방정식으로 만들면 다음과 같다. 

이제 남은 것은 위의 방정식을 가우스 소거법을 활용하여 실제 해를 구하는 것이다. 계산하기에 식이 약간 귀찮게 되었지만 일단 해보자. pivot은 14이고 pivot아래의 원소를 없애야 하므로 6c를 소거해야한다. 첫 번째 방정식에 6/14를 곱하여 두 번째 방정식에서 빼주면 d=2/3을 얻고, 후방대입법(back substitution)을 통해 c=1/2라는 것을 알아낼 수 있다.

이렇게 하여 $\hat{x}={[\hat{c} \; \hat{d} ]}^T$를 구하였다. 따라서 최적의 라인(Line)에 대한 방정식은 다음과 같다. 

이제 Fig. 3의 p의 실제 값들을 구해보자. t=1, 2, 3을 각각 대입해주면 p1=7/6, p2=5/3, p3=13/6을 얻는다. 

다음으로 에러를 구해보자. 에러는 e=b-p이므로 b=1, 2, 2에서 p1, p2, p3를 각각 빼주면된다. 이를 정리하면 아래와 같다. 

위에서 계산한 p와 e를 Fig. 3에 표현해보자. 

Fig. 4 최소 자승법의 p와 e의 값

이렇게 하여 주어진 데이터들을 이용하여 방정식을 세우고 최소자승법을 이용하여 이 데이터들을 가장 잘 근사하는 라인을 찾아내었다. 

- Error vector

앞서 우리는 최소자승법을 이용하여 데이터의 경향을 최대한 잘 반영하는 직선(Line)을 찾았다. 여기서 좀 더 깊은 이해를 위해 에러(error) 벡터에 대해 알아보자. 

식 (4)와 같이 원래의 데이터 값인 b벡터는 에러 벡터 e와 투영 벡터 p의 합으로 이루어져 있다. 즉 b=e+p이다. Fig. 4를 기준으로 보면 당연하다. 투영된 값인 p에 에러 e를 다시 더하면 원래의 b가 된다. 이것을 개개의 데이터가 아닌 벡터의 기준으로 생각해보자. Fig. 1에서 p와 e는 직교(perpendicular)이다. 그렇다면 실제 값은 어떻게 될까? 식 (17)에서 구한 실제 p와 e의 값을 가지고 검증해보자. 

p2는 계산의 편의를 위해 5/3 -> 10/6 으로 바꿨다. 우선 e+p의 결과가 b가 되는 것은 쉽게 덧셈을 해보면 알 수 있다. 

e와 p가 실제로 직교하는지 알아보려면 어떻게 하면 될까? 바로 내적(dot product)을 통해 알 수 있다. 내적을 해보면...

-7/36 + 20/36 - 13/6 = 0 이 된다. 따라서 e와 p가 직교임을 확인하였다. 

여기서 한 가지 중요한 사실은 e가 직교한 것은 p뿐만이 아니라는 것이다. 바로 p가 존재하는 column space전체와 직교한다. 다른 column 벡터와 내적을 통해 확인해보자. 다른 column vector의 예로는 A의 column space의 기저(basis)인 A의 column vector들과의 연산을 해보면 될 것이다. 실제로 계산을 수행해보면 0이 되어 직교하는 것을 확인할 수 있다. 

에러 벡터 e가 기저 벡터들과 수직이기 때문에 결과적으로 column space와 수직이다. 

3. MATLAB 구현

식 (7)을 최소자승법을 통해 해를 구하는 프로그램을 MATLAB으로 작성하였다. 아래 그림은 plot 결과이다. 

Fig. 5 식 (7)의 최소자승법의 MATLAB 구현 결과

아래는 코드이다. 참고로 추가적인 데이터를 넣어서 돌려보고 싶다면 다음과 같이 하면 된다. 예를 들어 [2, -1]의 데이터를 새로 넣고 싶다면 A의 column 1의 마지막에 2를, column 2의 마지막은 1로, b의 마지막 부분에 -1을 추가해주면 된다. 

4. 마치며

이번 강의에서는 투영(Projection)에 대해 리뷰를 하고 이를 응용한 최소자승법(Least square)에 대해 공부하였다. 최소자승법을 적용하는 데에 있어 이를 두 가지 관점에서 바라볼 수 있다. 

첫 번째는 벡터의 관점, 두 번째는 데이터의 관점이다. 벡터의 관점에서 보자면 이는 투영과 깊은 관련이 있고 Fig. 1에서 원래의 벡터 b가 column space로 투영된 벡터 p가 된다는 것이다. 이것을 이용해서 최소자승법의 해를 구한다. 두 번째는 데이터의 관점이며 Fig. 4에서 처럼 직선의 방정식의 파라미터로써 나타난다. 그러나 실제로 해 자체를 구하는 것은 투영의 관점으로부터 출발하는 것이다. 즉 해가 존재하지 않는 상황에서 최적해(best solution)를 구하기 위해 투영의 개념을 이용하여 b를 column space로 투영시켜 p를 만들고 해를 구한 다음 이 해를 직선의 방정식의 파라미터로 이용하는 것이다. 

Fig. 1과 Fig. 4는 같은 식으로 표현되는 두 가지 다른 형태의 그림이다. Fig. 1에서는 x(hat)=[c d]가 column vector의 선형 조합(Linear combination)으로 p를 표현하였고, Fig. 4에서는 x(hat)=[c d]가 직선을 표현하는 파라미터로써 이용되었다. 이 두 가지 관점을 잘 구분하여 이해하도록 하자. 중요한것은 투영의 개념으로부터 온 것이며, 표현된 방식이 다를 뿐 결국 같은 것을 나타낸다는 것이다. 

결국 최소자승법은 다음의 핵심 방정식을 이해함으로써 해를 구할 수 있다. 

식 (20.1)에서 x hat으로 식을 정리하기 위해선 $A^T A$가 역행렬이 존재(invertible)해야 한다. 역행렬이 존재하려면 아주 중요한 조건이 있는데 바로 A의 column vector들이 독립(independent)해야 한다는 것이다. column vector가 독립이 아니라면 역행렬이 존재하지 않고 결국 해를 구할 수 없다. 

이러한 최소자승법은 통계학의 관점에서는 회귀(regression)의 한 방법으로 볼 수 있으며 선형 회귀(Linear regression)와 같다. 

최소자승법은 해가 존재하지 않을 경우 가장 근접하는 최적해(best solution)를 구하고자 하는 것과,

수많은 데이터가 주어진 상황에서 데이터의 경향을 분석하고 예측하기 위한 도구로써의 목적성을 가진다. 

이것들을 잘 기억하도록 하자.