Lecture 34. 전체 정리 — 다섯 개의 분해

서른세 편이 지났다.

우리는 연립방정식 하나에서 출발했다. 그것을 푸는 법을 배웠고, 해가 사는 공간의 모양을 배웠고, 해가 없을 때 가장 가까운 답을 찾는 법을 배웠다. 그다음에는 방향을 돌려 행렬 자체를 들여다보았다. 변하지 않는 방향을 찾았고, 시간의 흐름을 예측했고, 마침내 어떤 행렬이든 조건 없이 쪼갤 수 있는 도구에 닿았다.

그런데 이 많은 것이 결국 무엇이었는가. 한 장에 담을 수 있는가.

담을 수 있다. 다섯 개의 분해다. 이번 강의에서는 새로 배우는 것이 하나도 없다. 지금까지 만든 연장을 전부 꺼내 늘어놓고, 각각이 무엇을 요구하고 무엇을 돌려주는지 마지막으로 확인한다. 그리고 L10에서 뼈대만 그렸던 그림 한 장을 끝까지 채운다.

1. 다섯 개의 분해¶

후반부에서 만든 것을 한 표에 넣는다. 각 줄은 무엇을 요구하고 무엇을 돌려주는가로 읽으면 된다.

$A = LU$ — 소거를 받아 적은 것¶

첫 줄은 L4의 것이다. 소거를 하며 쓴 곱수를 아래삼각행렬에 모으고, 소거가 끝난 모습을 위삼각행렬에 두면 그대로 분해가 된다.

(1)의 오른쪽 등식이 이 분해의 부산물이다. $L$ 의 대각선이 전부 1이므로 $\det L = 1$ 이고, 삼각행렬의 행렬식은 대각선의 곱이므로(L18) 피벗을 곱하면 행렬식이 나온다. 한 번의 소거로 해와 행렬식을 동시에 얻는 셈이다. 그리고 $L$ 과 $U$ 를 쥐고 있으면 우변이 바뀔 때마다 $n^3/3$ 을 다시 치를 필요 없이 $n^2$ 으로 풀 수 있다.

$A = QR$ — 열을 직각으로 세운 것¶

둘째 줄은 L17의 것이다. 그람-슈미트로 열을 하나씩 직교화하면 $Q$ 가 나오고, 그 과정에서 쓴 계수가 $R$ 에 남는다.

(2)의 세 조건이 함께 있으면 최소제곱이 쉬워진다. 정규방정식에 $A = QR$ 을 그대로 넣어 보자.

(3)의 화살표를 건너려면 양변 앞의 $R^{\mathsf T}$ 를 지워야 하는데, 열이 독립이면 $R$ 이 가역이라 지울 수 있다. 남는 것은 후진 대입 한 번이다. $A^{\mathsf T}A$ 를 아예 만들지 않는다는 점이 L33에서 본 그 차이를 만든다.

$S = Q\Lambda Q^{\mathsf T}$ — 대칭이 받는 상¶

셋째 줄은 L25의 스펙트럼 정리다. 대칭이기만 하면 고윳값이 전부 실수이고 고유벡터를 직교로 고를 수 있다. 그래서 $S^{-1}$ 이 $S^{\mathsf T}$ 가 된다.

(4)의 오른쪽은 이 분해를 다르게 읽은 것이다. $\vv{q}_i\vv{q}_i^{\mathsf T}$ 는 $\vv{q}_i$ 방향으로의 투영행렬이므로(L15), 대칭행렬은 서로 직교하는 투영들을 $\lambda_i$ 로 가중해 더한 것이 된다. 여기에 고윳값의 부호만 얹으면 L27의 양정치 판정이 그대로 나온다. 전부 양수면 그릇이고 섞이면 안장이다.

$A = S\Lambda S^{-1}$ — 좋은 좌표계로 갈아타는 것¶

넷째 줄은 L22의 대각화다. 고유벡터를 열에 세워 $S$ 를 만들면, 그 좌표계에서는 행렬이 대각행렬이 된다. 거듭제곱이 곧바로 따라온다.

(5)의 가운데에서 $S^{-1}S$ 가 $k-1$ 번 사라진 것이 계산의 전부다. 그런데 이 식의 값어치는 속도가 아니다. $k$ 가 커질 때 무슨 일이 벌어지는지를 $\lambda_i$ 만 보고 알 수 있다는 것이 값어치다. $\lvert\lambda\rvert < 1$ 이면 0으로 가라앉고 $\lvert\lambda\rvert > 1$ 이면 터진다. L23의 미분방정식과 L24의 마코브 행렬이 전부 이 한 줄에서 나왔다.

$A = U\Sigma V^{\mathsf T}$ — 조건이 하나도 없는 것¶

다섯째 줄이 L29다. 정사각이 아니어도 되고, 대칭이 아니어도 되고, 랭크가 모자라도 된다.

(6)의 오른쪽 합은 (4)의 합과 모양이 닮았지만 결정적으로 다른 데가 있다. 대칭행렬은 $\vv{q}_i$ 한 벌로 자기 자신을 적었고, 여기서는 $\vv{u}_i$ 와 $\vv{v}_i$ 두 벌을 쓴다. 들어가는 공간과 나오는 공간이 다르니 기저도 두 벌이어야 하는 것이다. 그 대가로 조건이 사라졌다.

2. 조건은 사슬이 아니다¶

다섯 줄을 늘어놓으면 자연스럽게 이런 문장을 쓰고 싶어진다.

(7)의 포함 사슬은 틀렸다. 맨 오른쪽 고리는 무엇이든 모든 행렬 안에 들어가니 따질 것이 없고, 맨 왼쪽 고리는 참이다. 그런데 가운데 두 고리가 거짓이다. L32에서도 같은 경고를 했으니, 이미 배운 행렬로 반례를 직접 세워 보자.

대칭인데 $LU$ 가 없다¶

L2에서 피벗이 0이 되는 경우를 보았다. 가장 작은 예가 이것이다.

(8)의 행렬은 대칭이므로 스펙트럼 정리가 무조건 적용된다. 고윳값은 1 과 -1 이고 고유벡터는 $(1,1)$ 과 $(1,-1)$ 로 직교한다. 그런데 왼쪽 위 성분이 0이라 첫 피벗이 잡히지 않는다. 행을 바꾸지 않고는 소거를 시작조차 할 수 없다. 대칭이 $LU$ 를 보장하지 않는다.

$LU$ 는 있는데 대각화가 안 된다¶

L28의 결함 행렬을 가져오면 반대 방향의 반례가 된다.

(9)의 $J$ 는 이미 위삼각이므로 $L = I$ 로 두면 소거가 끝나 있다. $LU$ 가 있고 열도 독립이다. 그런데 고윳값 3의 대수적 중복도가 2인데 $\rank(J - 3I) = 1$ 이라 기하적 중복도가 $2 - 1 = 1$ 이다. 고유벡터가 하나뿐이니 대각화는 불가능하다.

대각화는 되는데 $QR$ 이 없다¶

세 번째 반례는 이 강의에서 계속 쓸 행렬이다.

(10)의 셋째 열이 앞의 두 열의 합이므로 열이 종속이고, 따라서 $QR$ 에서 $R$ 의 마지막 대각 성분이 0이 된다. 그런데 고윳값을 구해 보면 이야기가 달라진다. 대각합이 2, 행렬식이 0, 2차 주소행렬식의 합이 -1 이므로 특성다항식이

이 된다. (11)의 세 근이 서로 다르므로 고유벡터가 세 개 나오고 대각화가 된다. 랭크가 모자란 것과 결함인 것은 전혀 다른 이야기라는 뜻이다.

참인 포함은 양 끝뿐이다¶

반례 셋이 사슬의 가운데를 끊었다. 그러면 남는 것은 무엇인가.

(12)의 왼쪽 포함은 스펙트럼 정리 그 자체다. 대칭이면 고유벡터를 정규직교로 고를 수 있으니 $n$ 개가 반드시 나온다. 반대 방향은 거짓이다. $\begin{pmatrix}2&1\\0&3\end{pmatrix}$ 는 고윳값이 2와 3으로 달라 대각화되지만 대칭이 아니다. 오른쪽 포함은 사정이 다르다. 어떤 행렬이든 SVD를 가지므로 마지막 칸에는 조건이랄 것이 없고, 그래서 이 고리는 참일 수밖에 없다.

3. 같은 행렬 하나에 다섯을 다 걸어 본다¶

그러면 다섯을 전부 통과하는 행렬은 어떤 것인가. 대칭이면서 소거가 되고 랭크가 꽉 차야 한다. L27의 삼중대각행렬이 바로 그것이다.

(13)의 $T$ 는 대칭이고, 선행 주소행렬식이 $2, 3, 4$ 로 전부 0이 아니며, 가역이다. 다섯 줄이 전부 걸린다. 하나씩 걸어 보자.

소거하면 피벗이 규칙적으로 나온다.

(14)의 곱이 (1)의 등식을 그대로 확인해 준다. 행 교환이 한 번도 필요하지 않으므로 순열행렬 없이 $T = LU$ 가 된다. $QR$ 로 가면 $Q$ 의 열이 $T$ 의 열을 직교화한 것이 되고, $R$ 의 대각 성분 절댓값의 곱이 다시 4가 된다. 직교행렬은 부피를 바꾸지 않기 때문이다(L20).

고윳값을 구하면 이렇게 나온다.

(15)의 셋이 전부 실수이고 전부 양수다. 실수인 것은 대칭이기 때문이고(L25), 양수인 것은 피벗이 전부 양수이기 때문이다(L27). 곱하면 $(2+\sqrt2)\cdot 2\cdot(2-\sqrt2) = 2(4-2) = 4$ 로 역시 행렬식이다.

이제 마지막 세 줄을 나란히 세워 보자. 여기서 재미있는 일이 벌어진다.

(16)의 등식들이 뜻하는 바는 세 분해가 같은 것으로 무너졌다는 것이다. 대칭이라 고유벡터가 직교하니 $S$ 를 굳이 비직교로 고를 이유가 없고, 고윳값이 전부 양수라 $\sigma_i = \lvert\lambda_i\rvert = \lambda_i$ 이며, $A^{\mathsf T}A = T^2$ 의 고유벡터가 $T$ 의 고유벡터와 같기 때문이다.

(17)의 왼쪽은 L29에서 확인한 등식이고 오른쪽은 L32의 조건수다. 분모와 분자에 $2+\sqrt2$ 를 곱하면 $\frac{(2+\sqrt2)^2}{4-2} = \frac{6+4\sqrt2}{2}$ 이 되어 $3 + 2\sqrt2$ 가 나온다. 5.83이면 아주 얌전한 행렬이다.

4. 네 부분공간 최종본¶

이제 이 강의의 결론이다. L10에서 네 개의 기본 부분공간을 그렸고, 그때는 상자 네 개와 차원만 있었다. L29에서 그 상자에 정규직교기저를 채웠다. L33에서 되돌아오는 화살표를 그렸다. 셋을 합치면 이런 정리가 된다.

Theorem 1의 정리를 (10)의 행렬로 끝까지 확인해 보자. 랭크가 2이고 $3 \times 3$ 이므로 네 칸이 전부 비어 있지 않다.

$\vv{v}$ 를 구한다¶

L29의 절차대로 $A^{\mathsf T}A$ 부터 만든다.

(19)의 행렬은 대칭이고 셋째 열이 앞 두 열의 합이라 랭크가 2다. 고유벡터를 눈으로 찾을 수 있다. $(1,1,2)$ 를 곱하면 $(2+1+6,\ 1+2+6,\ 3+3+12) = (9,9,18)$ 이라 정확히 9배이고, $(1,-1,0)$ 을 곱하면 $(2-1,\ 1-2,\ 3-3) = (1,-1,0)$ 이라 1배다. 그리고 $(1,1,-1)$ 을 곱하면 $(2+1-3,\ 1+2-3,\ 3+3-6) = (0,0,0)$ 이다.

(20)의 세 값이 $A^{\mathsf T}A$ 의 고윳값에 제곱근을 씌운 것이다. 0이 아닌 것이 둘이므로 랭크가 2라는 사실이 여기서도 확인된다. 대응하는 고유벡터를 길이 1로 맞추면 다음과 같다.

(21)의 앞 둘이 행공간의 정규직교기저이고 셋째가 영공간의 기저다. 서로 직교하는지는 내적을 재 보면 된다. $\vv{v}_1 \cdot \vv{v}_2 = 1 - 1 + 0 = 0$ 이고 $\vv{v}_1 \cdot \vv{v}_3 = 1 + 1 - 2 = 0$ 이며 $\vv{v}_2\cdot\vv{v}_3 = 1 - 1 + 0 = 0$ 이다.

$\vv{u}$ 를 구한다¶

$\vv{u}_i$ 는 따로 구하는 것이 아니라 $A\vv{v}_i$ 를 $\sigma_i$ 로 나눠 얻는다. L29에서 이 순서를 어기면 부호가 어긋난다고 경고했던 그 자리다.

(22)의 가운데 벡터는 $A(1,1,2) = (1+1+4,\ 1+0+2,\ 0+1+2)$ 를 계산한 것이다. 분모의 3이 $(6,3,3)$ 을 $(2,1,1)$ 로 줄여 준다. 둘째도 같은 방식으로 나온다.

(23)의 $\vv{u}_2$ 는 $A(1,-1,0) = (1-1,\ 1-0,\ 0-1)$ 에서 나왔고, $\vv{u}_3$ 은 앞의 둘에 직교하도록 고른 것이다. 이 셋이 L29의 앵커 $C$ 에서 나온 $\vv{u}$ 와 똑같다. $A$ 의 앞 두 열이 바로 그 $C$ 이기 때문이다.

(24)의 두 등식이 아래 두 칸의 정체를 확정한다. $\vv{v}_3$ 이 영공간에 있고 $\vv{u}_3$ 이 좌영공간에 있다. 네 칸의 차원을 세면 이렇게 맞아떨어진다.

(25)의 두 등식이 L10의 차원의 기본정리다. 왼쪽은 정의역 쪽 $\R^3$ 을 두 조각으로 나눈 것이고 오른쪽은 치역 쪽 $\R^3$ 을 나눈 것이며, 두 조각은 직교한다(L14).

화살표를 양쪽으로 그린다¶

Theorem 1의 두 화살표를 이 행렬에서 숫자로 적으면 이렇게 된다.

(26)의 두 쌍이 서로를 되돌린다. $\vv{v}_1$ 은 3배로 늘어나 $\vv{u}_1$ 이 되고, $\vv{u}_1$ 은 3으로 나뉘어 $\vv{v}_1$ 로 돌아온다. $\vv{v}_2$ 는 1배이므로 길이가 그대로다. 행공간과 열공간 사이는 왕복이 된다.

아래 두 칸은 사정이 다르다.

(27)의 마지막 조각이 편도인 이유다. $1/\sigma_3$ 을 쓸 수 없으니 $\Sigma^{+}$ 의 그 자리에 0을 넣을 수밖에 없었다(L33). 그래서 $\vv{v}_3$ 방향으로 들어 있던 정보는 0으로 눌린 뒤 어떤 행렬로도 되찾을 수 없다.

실제로 만들어 보면 이렇게 생겼다.

(28)의 행렬에 $A$ 를 곱해 보면 단위행렬이 나오지 않는다. 나올 수가 없다. $A$ 가 3차원을 2차원으로 눌렀으니 그 손실을 메울 방법이 없기 때문이다. 대신 이런 것이 나온다.

(29)의 두 행렬은 각각 행공간으로의 투영과 열공간으로의 투영이다. $I$ 에서 한 방향의 투영을 뺐으니 남는 것은 그 방향의 직교여공간으로의 투영이다(L15). 숫자로 적으면 둘 다 대각선이 $\tfrac23$ 인 행렬이고, 고윳값은 $1, 1, 0$ 이다. 살렸다, 살렸다, 죽였다.

5. 세 개의 태도¶

공식은 잊어도 좋다. 그러나 다음 셋은 이 교재가 남기고 싶은 것이다.

옳은 공식과 쓰는 공식은 다르다¶

첫째 태도다. 후반부에서 이 교훈을 네 번 만났다.

(30)의 두 값은 $n = 20$ 에서 각각 약 $5.1\times10^{19}$ 와 $2{,}667$ 이다. 크래머 공식은 해를 행렬식의 비로 아름답게 적어 주지만, 그 아름다움을 계산하려면 우주의 나이가 필요하다. 여인수 전개(L19)도 $n!$ 이라 사정이 같다.

(31)의 관계가 L28의 결론이었다. $\epsilon$ 을 10^-8 만 흔들어도 고윳값이 $3 \pm 10^{-4}$ 로 갈라지고 고유벡터 행렬의 조건수가 10⁴ 이 된다. 조르당 형은 존재하지만 수치적으로는 존재하지 않는다.

(32)의 등식이 L33의 결론이었다. 정규방정식을 그대로 코드로 옮기면 조건수가 제곱되어 유효자릿수가 절반으로 준다. 네 번 다 이유가 같다. 답이 있다는 것과 그 답을 손에 쥘 수 있다는 것은 다르다.

좋은 기저를 고르면 어려운 문제가 쉬워진다¶

둘째 태도다. 대각화가 그 첫 사례였다.

(33)의 왼쪽은 고유벡터 기저에서 적은 것이다. 표준기저에서는 행렬을 $k$ 번 곱해야 알 수 있는 것이, 좋은 기저에서는 스칼라를 $k$ 제곱하는 것으로 바뀐다. 기저를 바꿨을 뿐인데 문제의 난이도가 달라졌다.

(34)의 두 값은 $N = 2^{20}$ 에서 $52{,}429$ 배 차이가 난다. 푸리에 행렬을 반씩 쪼개는 요령 하나가 신호처리 전체를 실용 가능하게 만들었다. L31의 DCT도, L29의 SVD도 같은 이야기의 다른 판본이다. 어느 좌표계에서 보느냐가 문제의 크기를 정한다.

조건이 없는 도구가 가장 강하다¶

셋째 태도다. 앞의 둘이 요령이라면 이것은 원칙에 가깝다.

(35)의 대비가 SVD의 값어치다. 무작위 $4\times4$ 실행렬 400개를 만들어 보면 그중 88%가 복소 고윳값을 갖는다. $4\times3$ 이면 고윳값이라는 개념 자체가 없다. 그런데 특이값은 어느 쪽에서도 음이 아닌 실수로 존재한다.

6. 전체 역인덱스¶

찾아볼 수 있게 개념과 강의 번호를 붙여 둔다.

전반부 — $A\vv{x} = \vv{b}$ 를 푸는 문제¶

후반부 — 행렬 $A$ 자체를 쪼개는 문제¶

파이썬 색인¶

7. 다음 여정¶

Figure 5의 지도에서 오른쪽 끝의 점선이 여기서부터다. 세 편을 준비해 두었다.

보강 1 — 주성분분석과 SVD. 공분산행렬은 대칭이고 양의 준정부호라 L25와 L27이 그대로 통한다. 그런데 실무 라이브러리는 공분산행렬을 만들지 않고 데이터 행렬에 직접 SVD를 건다. 이유는 (32)의 등식 하나다.

보강 2 — 수치선형대수 입문. 5절 첫째 태도의 네 사례가 조건수라는 하나의 개념으로 설명된다는 것을 보인다. 그리고 고윳값을 실제로 구하는 법을 다룬다. L22에서 벡터에 행렬을 거듭 곱한 것이 곧 거듭제곱법이었다.

보강 3 — 그래프 라플라시안. L12의 결합행렬 $A$ 로부터 만든 라플라시안이다.

(36)의 왼쪽은 대칭이고 양의 준정부호라 지금까지의 도구가 전부 통한다. 오른쪽 등식은 L12에서 이미 본 것이고, 여기에 두 번째로 작은 고윳값을 더하면 그래프를 둘로 자르는 선이 나온다.

그 너머에는 최적화와 함수해석과 양자역학이 있다. 어느 길로 가든 Figure 3의 그림은 계속 따라온다.

8. 자주 하는 오해¶

① 다섯 분해는 조건이 느슨해지는 순서로 늘어선다. 아니다. 2절이 반례 셋을 보였다. 확실한 것은 대칭이 대각화 가능에 포함된다는 것과 맨 아랫줄이 무조건이라는 것뿐이다. 사슬이 아니라 연장통이다.

② SVD 하나만 알면 나머지는 몰라도 된다. 아니다. SVD는 $A^{k}$ 의 극한을 알려주지 않는다. 그것은 고윳값의 몫이다. 방정식을 빠르게 풀어야 할 때 $LU$ 대신 SVD를 쓰면 몇 배가 느리다. 조건이 없다는 것과 가장 많이 알려준다는 것은 다른 말이다.

③ 고윳값과 특이값은 대체로 비슷한 수다. 아니다. $\sigma_i = \lvert\lambda_i\rvert$ 가 되는 것은 정규행렬, 곧 $A^{\mathsf T}A = AA^{\mathsf T}$ 일 때다(L32). 대칭행렬은 그중 한 종류일 뿐이고 직교행렬도 정규행렬이다. Figure 1의 90도 회전이 대칭이 아니면서 $\lvert\lambda\rvert$ 와 $\sigma$ 가 둘 다 1인 예다. 반대로 $\begin{pmatrix}3&0\\4&5\end{pmatrix}$ 는 정규행렬이 아니라서 고윳값이 3과 5인데 특이값은 $3\sqrt5 \approx 6.71$ 과 $\sqrt5 \approx 2.24$ 다. 노름은 5가 아니라 6.71이다.

④ 네 부분공간 그림은 $A$ 가 정사각일 때의 이야기다. 아니다. 오히려 정사각이 아닐 때 더 요긴하다. $m \neq n$ 이면 왼쪽 상자와 오른쪽 상자가 사는 공간의 차원부터 다르고, 그 차이가 곧 해가 없거나 무한히 많은 이유다. 4절에서 $m = n = 3$ 으로 잡은 것은 그림을 그리기 위해서다.

⑤ 랭크가 모자란 행렬은 대각화도 안 된다. 아니다. (11)의 계산이 반례다. 랭크가 모자란 것은 고윳값 0이 있다는 뜻일 뿐이고, 결함인 것은 고유벡터의 개수가 모자란다는 뜻이다. 두 이야기는 관계가 없다.

⑥ 이제 다 배웠다. 아니다. 여기까지가 실수 유한차원의 이야기다. 무한차원으로 가면 스펙트럼 정리가 훨씬 조심스러워지고, 희소행렬로 가면 소거 자체를 포기하고 반복법을 쓴다. 다 배운 것이 아니라 지도를 손에 넣은 것이다.

마치며...¶

서른네 편의 여정이 끝났다. 이번 강의에서 정리한 것은 이렇다.

• 후반부는 다섯 개의 분해로 요약된다. 각 줄은 요구하는 것과 돌려주는 것의 거래다.

• 다섯 조건은 사슬이 아니다. 양 끝의 두 포함만 확실하다.

• 다섯을 전부 통과하려면 대칭이어야 하고, 그때는 아래 세 줄이 하나로 무너진다.

• 네 부분공간에 $\sigma_i$ 배로 오가는 화살표를 채우면 그림이 완성된다. 위쪽은 왕복이고 아래쪽은 편도다.

• 남는 세 문장은 이것이다. 옳은 공식과 쓰는 공식은 다르다. 좋은 기저를 고르면 어려운 문제가 쉬워진다. 조건이 없는 도구가 가장 강하다.

돌아보면 후반부 전체가 하나의 이야기였다. 조건과의 싸움이었다. $LU$ 는 소거가 되어야 했고, $Q\Lambda Q^{\mathsf T}$ 는 대칭이어야 했고, $S\Lambda S^{-1}$ 은 고유벡터가 충분해야 했다. 그 조건들이 하나씩 깨지는 것을 지켜보았고, 마지막에 조건이 하나도 없는 분해에 닿았다. 그 자리에서 네 개의 상자와 그 사이를 오가는 $A$ 와 $A^{+}$ 의 화살표를 얻었다. 선형대수 전체가 그 한 장에 있다.

마지막 실습이 남았다. L34 실습 노트북에서 다섯분해 함수를 만들어 같은 행렬에 다섯을 전부 걸어 보고, 네 부분공간 최종본을 돌려 가며 보고, 이 책에 나온 행렬을 전부 모아 마지막으로 한 번씩 통과시킨다.

긴 여정을 함께해 주어 고맙다.