Lecture 27. 양의 정부호 행렬과 최소값

L25에서 대칭행렬의 고윳값이 전부 실수임을 배웠다. 그렇다면 이런 질문을 던질 수 있다. 그 실수들이 전부 양수라면 어떻게 되는가.

별것 아닌 조건 같지만 이 하나에서 다음이 전부 따라 나온다. $\vv{x}^{\mathsf T}S\vv{x}$ 가 늘 양수가 되고, 그 함수의 그래프가 그릇 모양이 되어 원점이 유일한 최소가 되고, 등고선이 타원이 되고, 소거했을 때 피벗이 전부 양수가 되고, 최소제곱의 해가 유일해진다.

하나의 조건이 이렇게 많은 결과를 낳는 경우는 흔치 않다. 그리고 그 모든 결과의 기하학적 정체는 단 하나의 그림, 타원이다.

1. 다섯 개의 동치 조건¶

정의는 고윳값으로 했지만, 고윳값을 구하는 것은 비싼 일이다. 다행히 같은 것을 말하는 방법이 넷 더 있다.

다섯 개가 전부 동치라는 것 자체가 놀라운 사실이다. 고윳값과 행렬식과 소거와 함수의 부호와 인수분해가 하나로 묶인다. 서로 다른 강의에서 따로 배운 것들이다.

쓰임도 각각 다르다.

조건	언제 쓰는가
① 고윳값	뜻을 이해할 때. 계산은 비싸다
② 선행 주소행렬식	$2 \times 2$ , $3 \times 3$ 을 손으로 판정할 때
③ 피벗	소거를 이미 했을 때. $n^3$ 이면 끝난다
④ 에너지	이론을 전개할 때. 증명에서 가장 자주 쓴다
⑤ $A^{\mathsf T}A$	어디서 양정치 행렬이 나타나는지 설명할 때

앵커로 다섯 개를 다 확인하자¶

이번 강의 내내 쓸 행렬이다.

S = \begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix}

(1)

① 고윳값. $\operatorname{tr}(S) = 10$ , $\det S = 25 - 16 = 9$ 이므로

\lambda^2 - 10\lambda + 9 = (\lambda - 1)(\lambda - 9) = 0 \qquad\Longrightarrow\qquad \lambda = 1, \; 9

(2)

둘 다 양수이다. 고유벡터는 L25의 방식대로 $(1,-1)$ 과 $(1,1)$ 이다.

② 선행 주소행렬식. 왼쪽 위부터 잘라 낸다.

\det\begin{bmatrix} 5 \end{bmatrix} = 5 > 0, \qquad \det\begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix} = 9 > 0

(3)

③ 피벗. 2행에서 1행의 $\tfrac45 = 0.8$ 배를 뺀다.

\begin{bmatrix} 5 & 4 \\ 4 & 5 \end{bmatrix} \;\longrightarrow\; \begin{bmatrix} 5 & 4 \\ 0 & 5 - 0.8 \times 4 \end{bmatrix} = \begin{bmatrix} 5 & 4 \\ 0 & 1.8 \end{bmatrix}

(4)

피벗이 5 와 1.8 로 둘 다 양수이다. 곱이 9 로 행렬식과 같다(L18).

④ 에너지. 2절에서 다룬다.

⑤ $A^{\mathsf T}A$ . 6절에서 다룬다.

$3 \times 3$ 도 하나 보자. 다음 행렬은 뒤에서 계속 나온다.

T = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}

(5)

선행 주소행렬식이 $2, 3, 4$ 이고 피벗이 $2, \tfrac32, \tfrac43$ 이다. 둘 다 규칙이 예쁘고 전부 양수이다. 고윳값은 $2 - \sqrt2 \approx 0.586$ , 2, $2 + \sqrt2 \approx 3.414$ 로 역시 전부 양수이다. 피벗의 곱 $2 \times \tfrac32 \times \tfrac43 = 4$ 가 행렬식이다.

2. 에너지 — 행렬이 아니라 함수를 본다¶

조건 ④는 나머지 넷과 성격이 다르다. 행렬의 성분을 보는 것이 아니라 함수를 보는 조건이다.

f(\vv{x}) = \vv{x}^{\mathsf T}S\vv{x}

(6)

성분으로 풀어 쓰면 무엇인가. $2 \times 2$ 로 계산해 보자.

\begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} s_{11} & s_{12} \\ s_{12} & s_{22} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = s_{11}x_1^2 + 2s_{12}x_1x_2 + s_{22}x_2^2

(7)

2차 항만 있는 다항식이다. 이것을 2차 형식이라 한다. 앵커에 넣으면 이렇다.

f(\vv{x}) = 5x_1^2 + 8x_1x_2 + 5x_2^2

(8)

물리에서 퍼텐셜 에너지가 이 모양이라 에너지라고도 부른다. 용수철을 잡아당기면 에너지가 늘어난 길이의 제곱에 비례하고, 여러 개가 얽혀 있으면 정확히 이 꼴이 된다.

왜 대칭이 전제인가¶

$S$ 가 대칭이 아니어도 $\vv{x}^{\mathsf T}A\vv{x}$ 를 계산할 수는 있다. 그런데 해 보면 대칭 부분만 남는다. $\vv{x}^{\mathsf T}A\vv{x}$ 는 수이므로 전치해도 그대로이다.

\vv{x}^{\mathsf T}A\vv{x} = \left(\vv{x}^{\mathsf T}A\vv{x}\right)^{\mathsf T} = \vv{x}^{\mathsf T}A^{\mathsf T}\vv{x}

(9)

두 식을 더하고 2로 나누면 다음이 된다.

\vv{x}^{\mathsf T}A\vv{x} = \vv{x}^{\mathsf T}\left(\frac{A + A^{\mathsf T}}{2}\right)\vv{x}

(10)

비대칭 부분은 에너지에 아무 기여도 하지 못한다. 그러니 양정치를 논할 때 대칭을 전제하는 것은 제약이 아니라 정리이다. 어차피 대칭 부분만 보이기 때문이다.

3. 그릇인가 안장인가¶

1변수 미적분에서 $f'(0) = 0$ 이고 $f''(0) > 0$ 이면 원점이 극소였다. 다변수에서 그 자리를 무엇이 대신하는가.

$f(\vv{x}) = \vv{x}^{\mathsf T}S\vv{x}$ 의 원점에서의 2계 도함수들을 모아 놓은 행렬을 헤시안이라 하는데, 계산해 보면 $2S$ 이다. 그러므로 조건은 이렇게 옮겨진다.

f'' > 0 \qquad\longrightarrow\qquad \text{헤시안이 양의 정부호}

(11)

그림으로 보면 세 가지 경우가 있다.

같은 \vv{x}^{\mathsf T}S\vv{x} 인데 고윳값의 부호만 다르다. — Figure 1:같은 $\vv{x}^{\mathsf T}S\vv{x}$ 인데 고윳값의 부호만 다르다.

양의 정부호 — 고윳값이 전부 양수이면 어느 방향으로 가도 올라간다. 그릇이고 원점이 유일한 최소이다.
부정부호 — 부호가 섞여 있으면 어떤 방향으로는 올라가고 어떤 방향으로는 내려간다. 안장이고 최소도 최대도 아니다. 올라가고 내려가는 방향이 정확히 고유벡터 방향이다.
준정부호 — 고윳값에 0이 있으면 그 방향으로는 평평하다. 골짜기이고 최소가 한 점이 아니라 직선(또는 부분공간)을 이룬다.

왜 그런지는 L25의 랭크 1 분해로 한 줄에 보인다. $S = \sum_i\lambda_i\vv{q}_i\vv{q}_i^{\mathsf T}$ 이므로

\vv{x}^{\mathsf T}S\vv{x} = \sum_i \lambda_i\left(\vv{q}_i^{\mathsf T}\vv{x}\right)^2

(12)

이다. 괄호 안은 제곱이라 늘 음이 아니다. 부호는 오직 $\lambda_i$ 가 정한다. 전부 양수이면 합도 양수이고, 하나라도 음수이면 그 방향으로 $\vv{x}$ 를 잡아 음수를 만들 수 있다.

4. 소거법은 사실 제곱완성이었다¶

(8)의 식을 제곱완성해 보자. 고등학교에서 하던 그대로이다.

$x_1$ 이 들어간 항을 모으고 $x_1^2$ 의 계수 5로 묶는다.

5x_1^2 + 8x_1x_2 + 5x_2^2 = 5\left(x_1^2 + \frac{8}{5}x_1x_2\right) + 5x_2^2

(13)

괄호 안을 제곱꼴로 만든다. $\tfrac85$ 의 절반은 $\tfrac45 = 0.8$ 이다.

x_1^2 + \frac{8}{5}x_1x_2 = \left(x_1 + 0.8\,x_2\right)^2 - 0.64\,x_2^2

(14)

되돌려 넣고 $x_2^2$ 항을 정리한다.

5\left(x_1 + 0.8x_2\right)^2 - 5 \times 0.64\,x_2^2 + 5x_2^2 = 5\left(x_1 + 0.8x_2\right)^2 + (5 - 3.2)\,x_2^2

(15)

\vv{x}^{\mathsf T}S\vv{x} = \mathbf{5}\left(x_1 + \mathbf{0.8}\,x_2\right)^2 + \mathbf{1.8}\,x_2^2

(16)

굵게 쓴 세 수를 (4)의 소거와 비교해 보자.

$S = LDL^{\mathsf T}$ ¶

우연이 아니다. 소거를 행렬로 쓰면 $S = LU$ 인데(L4), $U$ 의 각 행에서 피벗을 빼내면 $U = DL^{\mathsf T}$ 가 된다. $S$ 가 대칭이라 나머지가 정확히 $L^{\mathsf T}$ 이다.

S = LDL^{\mathsf T}, \qquad L = \begin{bmatrix} 1 & 0 \\ 0.8 & 1 \end{bmatrix}, \qquad D = \begin{bmatrix} 5 & 0 \\ 0 & 1.8 \end{bmatrix}

(17)

이제 에너지에 넣어 보자. $\vv{y} = L^{\mathsf T}\vv{x}$ 로 두면

\vv{x}^{\mathsf T}S\vv{x} = \vv{x}^{\mathsf T}LDL^{\mathsf T}\vv{x} = \left(L^{\mathsf T}\vv{x}\right)^{\mathsf T}D\left(L^{\mathsf T}\vv{x}\right) = \vv{y}^{\mathsf T}D\vv{y} = \sum_i d_i\,y_i^2

(18)

제곱들의 가중합이고, 가중치가 피벗이다. 앵커에서 $y_1 = x_1 + 0.8x_2$ 이고 $y_2 = x_2$ 인데, 이것이 (16)의 괄호 안과 정확히 같다.

$L^{\mathsf T}$ 는 대각이 1인 삼각행렬이라 늘 가역이다. 그러므로 $\vv{x} \neq \vv{0}$ 이면 $\vv{y} \neq \vv{0}$ 이고, 거꾸로도 그렇다. 결론이 곧바로 나온다.

\text{모든 피벗} > 0 \quad\Longleftrightarrow\quad \vv{x} \neq \vv{0} \text{ 이면 } \sum d_iy_i^2 > 0 \quad\Longleftrightarrow\quad \text{양의 정부호}

(19)

조건 ③과 조건 ④가 같다는 것이 이렇게 증명된다.

5. 등고선은 타원이다¶

$\vv{x}^{\mathsf T}S\vv{x} = 1$ 이 그리는 도형은 무엇인가.

L25의 $S = Q\Lambda Q^{\mathsf T}$ 를 넣고 $\vv{y} = Q^{\mathsf T}\vv{x}$ 로 두자. $Q$ 가 직교행렬이라 이 갈아끼우기는 회전일 뿐 길이를 바꾸지 않는다.

\vv{x}^{\mathsf T}S\vv{x} = \vv{x}^{\mathsf T}Q\Lambda Q^{\mathsf T}\vv{x} = \vv{y}^{\mathsf T}\Lambda\vv{y} = \lambda_1y_1^2 + \lambda_2y_2^2 + \cdots + \lambda_ny_n^2

(20)

그러므로 방정식이 이렇게 된다.

\lambda_1y_1^2 + \lambda_2y_2^2 + \cdots + \lambda_ny_n^2 = 1

(21)

고등학교에서 본 타원의 표준형이다. $\lambda_iy_i^2 = 1$ 인 자리, 곧 $y_i = 1/\sqrt{\lambda_i}$ 가 축의 끝이다.

앵커로 확인하자. $\lambda = 1$ 과 9 이므로 반지름이 1 과 $\tfrac13$ 이다. 긴 축은 $\lambda = 1$ 의 고유벡터 $(1,-1)$ 방향이고, 짧은 축은 $\lambda = 9$ 의 고유벡터 $(1,1)$ 방향이다.

왼쪽이 \vv{x}^{\mathsf T}S\vv{x} = 1 이고 오른쪽이 여러 값의 등고선이다.
축의 방향은 값이 달라져도 움직이지 않는다. 크기만 변한다. — Figure 3:왼쪽이 $\vv{x}^{\mathsf T}S\vv{x} = 1$ 이고 오른쪽이 여러 값의 등고선이다. **축의 방향은 값이 달라져도 움직이지 않는다.** 크기만 변한다.

고윳값이 음수이면 (21)의 부호가 섞여 타원이 아니라 쌍곡선이 되고, 0이면 그 방향으로 축이 무한히 길어져 도형이 열린다. 3절의 안장과 골짜기가 등고선으로는 그렇게 보인다.

축의 비가 크면 헤맨다¶

가장 큰 고윳값과 가장 작은 고윳값의 비를 조건수라 한다.

\kappa = \frac{\lambda_{\max}}{\lambda_{\min}}

(22)

조건수가 1이면 등고선이 원이고, 크면 길쭉한 타원이다. 이것이 왜 중요한가. 최소를 찾아 내려갈 때 길쭉하면 헤매기 때문이다.

기울기의 반대 방향으로 내려가는 것을 경사하강이라 한다. 등고선이 원이면 기울기가 곧장 중심을 가리키지만, 길쭉하면 기울기가 골짜기 벽을 향해 비스듬히 서기 때문에 좌우로 튕기며 조금씩만 전진한다.

같은 자리에서 출발해 같은 방식으로 내려갔다. 조건수가 1.2, 9, 30으로 커질수록
걸음 수가 6, 63, 210으로 늘어난다. — Figure 4:같은 자리에서 출발해 같은 방식으로 내려갔다. 조건수가 1.2, 9, 30으로 커질수록 걸음 수가 6, 63, 210으로 늘어난다.

수렴 속도를 정하는 것은 다음 값이다.

\frac{\kappa - 1}{\kappa + 1}

(23)

$\kappa = 1$ 이면 0이라 한 걸음에 끝나고, $\kappa$ 가 커지면 1에 가까워져 한없이 느려진다. 가장 뻣뻣한 방향과 가장 물렁한 방향의 비율이 최적화의 속도를 정한다. 조건수는 L33에서 다시, 이번에는 수치 안정성의 척도로 만난다.

6. $A^{\mathsf T}A$ — L16의 빚을 갚는다¶

조건 ⑤를 다룰 차례이다. 그리고 이것이 양정치 행렬이 실제로 나타나는 자리이다.

아무 $m \times n$ 행렬 $A$ 에 대해 $S = A^{\mathsf T}A$ 를 만들어 보자. 먼저 대칭이다. 전치해 보면 된다.

\left(A^{\mathsf T}A\right)^{\mathsf T} = A^{\mathsf T}\left(A^{\mathsf T}\right)^{\mathsf T} = A^{\mathsf T}A

(24)

이제 에너지를 계산한다. 여기가 핵심이다.

\vv{x}^{\mathsf T}\left(A^{\mathsf T}A\right)\vv{x} = \left(A\vv{x}\right)^{\mathsf T}\left(A\vv{x}\right) = \lVert A\vv{x}\rVert^2

(25)

괄호를 옮겼더니 길이의 제곱이 되었다. 길이의 제곱은 음이 될 수 없으므로 $A^{\mathsf T}A$ 는 언제나 준정부호 이상이다.

언제 양정치인가. 0이 되려면 $\lVert A\vv{x}\rVert = 0$ , 곧 $A\vv{x} = \vv{0}$ 이어야 한다. 그런 $\vv{x}$ 가 영벡터뿐이라는 것은 $A$ 의 영공간이 원점뿐이라는 뜻이고, 그것은 $A$ 의 열이 독립이라는 뜻이다(L9).

A \text{ 의 열이 독립} \quad\Longleftrightarrow\quad A^{\mathsf T}A \text{ 가 양의 정부호} \quad\Longrightarrow\quad A^{\mathsf T}A \text{ 가 가역}

(26)

마지막 화살표는 고윳값이 전부 양수라 0이 없기 때문이다.

7. 준정부호 — 골짜기의 바닥¶

고윳값에 0이 섞이면 양의 준정부호라 한다. 조건들이 전부 “ $>$ ” 에서 “ $\ge$ ” 로 바뀐다.

\vv{x}^{\mathsf T}S\vv{x} \ge 0 \qquad (\text{모든 } \vv{x} \text{ 에 대해})

(27)

$\lambda = 0$ 인 고유벡터 방향으로는 에너지가 정확히 0이다. (12)에서 그 항이 통째로 사라지기 때문이다. 그래서 최소가 한 점이 아니라 직선이 된다. Figure 1의 세 번째 그림이 그것이다.

$\lambda = 0$ 인 방향은 곧 영공간이므로, 0인 고윳값의 개수가 $n - \rank(S)$ 이다. 골짜기 바닥의 차원이 랭크 부족분이다.

$A^{\mathsf T}A$ 는 $A$ 의 열이 종속이면 정확히 이 경우가 된다. 종속인 만큼 골짜기가 넓어진다. 이 사실이 두 강의 뒤 특이값 분해를 유도할 때 그대로 재료가 된다.

8. 촐레스키 — 가장 빠른 판정¶

컴퓨터로 양정치를 판정하는 실용적인 방법이 하나 더 있다. (17)의 $S = LDL^{\mathsf T}$ 에서 피벗이 전부 양수이면 $\sqrt{d_i}$ 가 실수이므로 $D = \sqrt{D}\sqrt{D}$ 로 쪼개 양쪽에 나눠 줄 수 있다.

S = LDL^{\mathsf T} = \left(L\sqrt{D}\right)\left(L\sqrt{D}\right)^{\mathsf T} = R\,R^{\mathsf T}

(28)

$R = L\sqrt{D}$ 는 대각이 양수인 하삼각행렬이다. 이것을 촐레스키 분해라 한다.

이것이 조건 ⑤의 구체적인 모습이기도 하다. $S = R R^{\mathsf T} = \left(R^{\mathsf T}\right)^{\mathsf T}R^{\mathsf T}$ 이므로 $A = R^{\mathsf T}$ 로 두면 $S = A^{\mathsf T}A$ 이다.

$T$ 로 해 보면 다음이 나온다.

R = \begin{bmatrix} \sqrt2 & 0 & 0 \\ -1/\sqrt2 & \sqrt{3/2} & 0 \\ 0 & -\sqrt{2/3} & 2/\sqrt3 \end{bmatrix}

(29)

대각이 $1.414, 1.225, 1.155$ 로 전부 양수이고, 제곱하면 피벗 $2, 1.5, 1.333$ 이 나온다.

9. 자주 하는 오해¶

대각 성분이 전부 양수면 양정치라는 오해¶

가장 흔한 오해이다. 반례가 간단하다.

B = \begin{bmatrix} 1 & 10 \\ 10 & 1 \end{bmatrix}

(30)

대각이 $1, 1$ 로 양수이다. 그런데 고윳값이 11 과 -9 이다. 에너지로 확인하면 더 분명하다. $\vv{x} = (1, -1)$ 을 넣어 보자.

\vv{x}^{\mathsf T}B\vv{x} = 1 - 20 + 1 = -18 < 0

(31)

선행 주소행렬식도 1 과 $1 - 100 = -99$ 라 두 번째에서 걸린다. 대각만 보아서는 알 수 없다. 대각 밖의 성분이 크면 언제든 무너진다.

“선행” 주소행렬식임을 놓치는 것¶

조건 ②는 왼쪽 위 모서리부터 순서대로 잘라 낸 것들이다. 아무 행과 열을 골라 만든 부분행렬이 아니다. 양의 준정부호를 판정할 때는 모든 주소행렬식을 봐야 하지만, 양의 정부호는 선행만 보면 된다.

양정치와 가역을 같은 것으로 보는 오해¶

양정치이면 가역이지만 거꾸로는 아니다. 음의 정부호도 가역이다. $-I$ 는 고윳값이 전부 -1 이라 완벽하게 가역인데 양정치가 아니다. (30)의 $B$ 도 $\det B = -99 \neq 0$ 이라 가역이다.

비대칭 행렬에 양정치를 논하는 것¶

2절에서 본 대로 에너지는 대칭 부분만 본다. 그래서 비대칭 행렬에 대해서는 "양정치"라는 말을 쓰지 않는 것이 관례이다. 굳이 판정하려면 $\tfrac12(A + A^{\mathsf T})$ 를 보면 된다.

마치며...¶

이번 강의에서 다룬 것을 정리하면 다음과 같다.

대상	내용
다섯 조건	고윳값 / 선행 주소행렬식 / 피벗 / 에너지 / $A^{\mathsf T}A$
에너지	$\vv{x}^{\mathsf T}S\vv{x}$ 는 2차 형식. 비대칭 부분은 보이지 않는다
스펙트럼으로	$\sum\lambda_i(\vv{q}_i^{\mathsf T}\vv{x})^2$ — 부호는 $\lambda$ 가 정한다
세 모양	그릇 / 안장 / 골짜기
제곱완성	계수가 곧 피벗, 배수가 곧 소거의 배수
$LDL^{\mathsf T}$	$\vv{y} = L^{\mathsf T}\vv{x}$ 로 두면 $\sum d_iy_i^2$
타원	축은 고유벡터, 반지름은 $1/\sqrt{\lambda}$
조건수	$\lambda_{\max}/\lambda_{\min}$ . 크면 경사하강이 지그재그
$A^{\mathsf T}A$	$\lVert A\vv{x}\rVert^2$ 이라 늘 준정부호. 열이 독립이면 양정치
준정부호	골짜기의 차원이 랭크 부족분
촐레스키	$S = RR^{\mathsf T}$ . 실패하면 즉시 멈추므로 가장 빠른 판정

다섯 개의 동치 조건을 살펴보았고, 그중 에너지 조건 $\vv{x}^{\mathsf T}S\vv{x} > 0$ 이 가장 본질적이라는 것을 확인하였다. 또한 소거법이 사실은 제곱완성이었다는 것, 그리고 등고선이 타원이며 그 축이 고유벡터 방향이라는 것도 배웠다.

타원 그림을 잘 기억해 두자. 축의 방향은 고유벡터, 축의 길이는 고윳값의 제곱근의 역수였다. 이 그림은 두 강의 뒤 특이값 분해에서 거의 그대로 되돌아온다. 그때는 원이 타원으로 변하는 장면을 보게 될 것이다.

그리고 $A^{\mathsf T}A$ 가 늘 대칭이고 늘 준정부호라는 사실도 기억해 두자. 특이값 분해의 유도 전체가 이 한 줄 위에 서 있다.

다음 강의에서는 오랫동안 미뤄 둔 물음에 답한다. L21에서 고윳값은 둘인데 고유벡터는 하나뿐인 행렬을 만났고, L22에서 그런 행렬은 대각화되지 않는다고 했으며, L23에서 그때 $te^{\lambda t}$ 같은 항이 나타난다고 했다. 세 번 미룬 셈이다. 고유벡터가 모자란 행렬은 대체 어떻게 해야 하는가.

이번 강의의 내용을 파이썬으로 확인해 보려면 L27 실습 노트북으로 넘어가면 된다. 다섯 조건이 정말 동시에 참이 되고 동시에 거짓이 되는지 무작위 행렬로 확인하고, $\vv{x}^{\mathsf T}S\vv{x}$ 의 표면을 슬라이더로 그릇에서 안장으로 바꿔 가며 보고, 조건수가 커질수록 경사하강이 몇 걸음 더 걸리는지 재 볼 수 있다.