연결 강의: MIT 18.06 Linear Algebra - Lecture 27: Positive Definite Matrices and Minima

1. 이번 강의의 위치

이번 강의는 positive definite matrix를 다룬다.

positive definite matrix는 대칭행렬의 중요한 하위 클래스이다. 지난 강의에서 대칭행렬은 고유값이 실수이고, 고유벡터를 직교하도록 선택할 수 있다는 것을 봤다.

이제는 그 실수 고유값들이 모두 양수인 경우를 본다.

positive definite matrix는 선형대수의 여러 주제를 한 번에 연결한다.

1. pivot
2. determinant
3. eigenvalue
4. quadratic form $x^TAx$
5. minimum
6. ellipse, ellipsoid

이번 강의의 핵심은 다음 질문이다.

어떤 대칭행렬 $A$가 positive definite인지 어떻게 판별할 수 있는가?

그리고 더 중요한 질문은 다음이다.

positive definite라는 조건은 기하적으로, 그리고 최소화 문제에서 무슨 의미를 가지는가?

---

2. Positive Definite Matrix의 정의

행렬 $A$는 기본적으로 대칭행렬이라고 하자.

$$A=A^T$$

이때 $A$가 positive definite라는 것은 모든 0이 아닌 벡터 $x$에 대해 다음이 성립한다는 뜻이다.

$$x^T A x>0 \qquad (x\neq 0)$$

여기서 $x^TAx$는 하나의 숫자이다.

이 값은 $A$가 벡터 $x$ 방향에서 얼마나 “양의 방향으로 휘어 있는지”를 나타낸다고 볼 수 있다.

positive definite matrix는 모든 방향에서 $x^TAx$가 양수이다. 따라서 대응되는 quadratic form의 그래프는 원점에서 위로 열린 bowl 모양이 된다.

---

3. Positive Definite 판별 조건

대칭행렬 $A$가 positive definite인지 확인하는 대표적인 판별 조건은 다음과 같다.

1. 모든 eigenvalue가 양수이다.
2. 모든 pivot이 양수이다.
3. 모든 leading principal minor가 양수이다.
4. 모든 $x\neq 0$에 대해 $x^TAx>0$이다.

이 네 조건은 대칭행렬에서는 같은 내용을 다른 언어로 말하는 것이다.

즉 다음이 동치이다.

$$A \text{ is positive definite}$$ $$\Longleftrightarrow \lambda_1,\lambda_2,\dots,\lambda_n>0$$ $$\Longleftrightarrow \text{all pivots are positive}$$ $$\Longleftrightarrow \text{all leading principal minors are positive}$$ $$\Longleftrightarrow x^TAx>0 \quad (x\neq 0)$$

이 중에서 가장 본질적인 정의로 자주 쓰이는 것은 $x^TAx>0$이다.

하지만 실제 계산에서는 pivot이나 determinant 판별이 더 편할 때가 많다.

---

4. $2\times 2$ 대칭행렬에서의 판별

다음 $2\times 2$ 대칭행렬을 생각하자.

$$A= \begin{bmatrix} a & b \\ b & c \end{bmatrix}$$

이 행렬이 positive definite이려면 다음 조건이 필요하다.

첫 번째 leading principal minor는 $a$이다.

$$a>0$$

두 번째 leading principal minor는 전체 determinant이다.

$$\det A=ac-b^2>0$$

따라서 $2\times 2$ 대칭행렬의 determinant test는 다음이다.

$$a>0, \qquad ac-b^2>0$$

pivot으로 보면 첫 번째 pivot은 $a$이고, 두 번째 pivot은 다음이다.

$$\frac{ac-b^2}{a}$$

따라서 pivot test는 다음이다.

$$a>0, \qquad \frac{ac-b^2}{a}>0$$

$a>0$인 상황에서는 determinant test와 pivot test가 같은 조건을 말한다.

---

5. 예시 1: 경계에 있는 Positive Semidefinite Matrix

다음 행렬을 보자.

$$A= \begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix}$$

첫 번째 leading principal minor는 양수이다.

$$2>0$$

하지만 determinant는 0이다.

$$\det A=2\cdot 18-6\cdot 6=36-36=0$$

따라서 이 행렬은 positive definite가 아니다.

그렇다고 완전히 나쁜 행렬도 아니다. 고유값은 다음과 같다.

$$\lambda_1=0, \qquad \lambda_2=20$$

고유값이 음수는 없고 0이 하나 있다.

이런 행렬을 positive semidefinite matrix라고 한다.

$$x^TAx\geq 0$$

은 성립하지만,

$$x^TAx>0 \quad (x\neq 0)$$

는 성립하지 않는다.

실제로 이 행렬은 rank가 1이다. 두 번째 행은 첫 번째 행의 3배이다.

$$\begin{bmatrix} 6 & 18 \end{bmatrix} = 3 \begin{bmatrix} 2 & 6 \end{bmatrix}$$

따라서 pivot도 하나만 존재하고, 두 번째 pivot은 0이 된다.

---

6. Quadratic Form $x^TAx$

이제 $x^TAx$가 실제로 어떤 식이 되는지 보자.

벡터를 다음처럼 둔다.

$$x= \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$$

행렬을

$$A= \begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix}$$

라고 하면,

$$x^TAx = \begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 2 & 6 \\ 6 & 18 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$$

이다.

먼저 행렬과 벡터를 곱하면,

$$Ax= \begin{bmatrix} 2x_1+6x_2 \\ 6x_1+18x_2 \end{bmatrix}$$

따라서,

$$x^TAx = x_1(2x_1+6x_2) +x_2(6x_1+18x_2)$$

정리하면,

$$x^TAx = 2x_1^2+12x_1x_2+18x_2^2$$

이다.

이는 다음처럼 완전제곱식으로 쓸 수 있다.

$$2x_1^2+12x_1x_2+18x_2^2 = 2(x_1+3x_2)^2$$

따라서 항상 0 이상이다.

하지만 $x_1=-3x_2$이면 값이 0이 된다. 예를 들어,

$$x= \begin{bmatrix} -3 \\ 1 \end{bmatrix}$$

이면,

$$x^TAx=0$$

이다.

그래서 이 행렬은 positive semidefinite이지 positive definite는 아니다.

---

7. 예시 2: Indefinite Matrix와 Saddle Point

이번에는 다음 행렬을 보자.

$$A= \begin{bmatrix} 2 & 6 \\ 6 & 7 \end{bmatrix}$$

첫 번째 pivot은 양수이다.

$$d_1=2$$

하지만 determinant는 음수이다.

$$\det A=2\cdot 7-6\cdot 6=14-36=-22$$

두 번째 pivot은 다음이다.

$$d_2=\frac{\det A}{d_1} = \frac{-22}{2} = -11$$

따라서 pivot 중 하나가 음수이다. 이 행렬은 positive definite가 아니다.

quadratic form은 다음이다.

$$x^TAx=2x_1^2+12x_1x_2+7x_2^2$$

예를 들어 $x_1=1$, $x_2=-1$을 넣으면,

$$2(1)^2+12(1)(-1)+7(-1)^2 = 2-12+7 = -3$$

이다.

즉 어떤 방향에서는 $x^TAx$가 음수가 된다.

이런 행렬은 indefinite matrix이다.

그래프 관점에서 보면 $x^TAx$는 어떤 방향으로는 올라가고, 어떤 방향으로는 내려간다.

이런 점을 saddle point라고 한다.

원점에서 1차 미분은 0이지만, 모든 방향에서 최소가 되는 것은 아니다. 어떤 방향에서는 minimum처럼 보이고, 다른 방향에서는 maximum처럼 보이는 형태이다.

---

8. 예시 3: Positive Definite Matrix

이제 다음 행렬을 보자.

$$A= \begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}$$

첫 번째 leading principal minor는 양수이다.

$$2>0$$

전체 determinant도 양수이다.

$$\det A=2\cdot 20-6\cdot 6=40-36=4$$

따라서 $A$는 positive definite이다.

pivot도 모두 양수이다.

첫 번째 pivot은 다음이다.

$$d_1=2$$

두 번째 pivot은 다음이다.

$$d_2=\frac{\det A}{d_1} = \frac{4}{2} = 2$$

따라서,

$$d_1>0, \qquad d_2>0$$

이다.

고유값도 모두 양수이다.

고유값의 곱은 determinant이다.

$$\lambda_1\lambda_2=4$$

고유값의 합은 trace이다.

$$\lambda_1+\lambda_2=22$$

곱이 양수이면 두 고유값은 둘 다 양수이거나 둘 다 음수이다. 그런데 합이 $22$로 양수이므로 둘 다 양수이다.

---

9. Positive Definite와 Bowl Shape

위 행렬의 quadratic form은 다음이다.

$$x^TAx=2x_1^2+12x_1x_2+20x_2^2$$

이 식은 항상 양수이다. 이를 보려면 완전제곱을 하면 된다.

$$2x_1^2+12x_1x_2+20x_2^2 = 2(x_1+3x_2)^2+2x_2^2$$

오른쪽은 제곱들의 양의 가중합이다.

$$2(x_1+3x_2)^2\geq 0, \qquad 2x_2^2\geq 0$$

그리고 $x\neq 0$이면 두 항이 동시에 0이 될 수 없다.

따라서,

$$x^TAx>0 \qquad (x\neq 0)$$

이다.

그래프 관점에서 보면 이 함수는 원점에서 위로 열린 bowl 모양이다.

원점은 minimum point이다.

---

10. 완전제곱과 Elimination의 관계

완전제곱은 Gaussian elimination과 같은 정보를 담고 있다.

행렬

$$A= \begin{bmatrix} 2 & 6 \\ 6 & 20 \end{bmatrix}$$

에 대해 elimination을 해보자.

첫 번째 pivot은 2이다.

$$d_1=2$$

아래쪽의 6을 없애기 위한 multiplier는 다음이다.

$$\ell=\frac{6}{2}=3$$

즉 두 번째 행에서 첫 번째 행의 3배를 뺀다.

$$R_2 \leftarrow R_2-3R_1$$

그러면 두 번째 pivot은 다음이 된다.

$$d_2=20-3\cdot 6=2$$

완전제곱식은 다음이었다.

$$2(x_1+3x_2)^2+2x_2^2$$

여기서 바깥의 $2$, $2$는 pivot이고, 안쪽의 $3$은 multiplier와 연결된다.

즉 완전제곱은 quadratic form 버전의 elimination이다.

positive pivots가 나온다는 것은 quadratic form을 양의 계수를 가진 제곱들의 합으로 쓸 수 있다는 뜻이다.

---

11. Minimum과 Second Derivative

positive definite matrix가 minimum과 연결되는 이유는 calculus의 second derivative test와 같다.

1변수 함수에서 $x=x_0$가 minimum이 되려면 먼저 1차 미분이 0이어야 한다.

$$f'(x_0)=0$$

하지만 이것만으로는 minimum인지 maximum인지 알 수 없다.

minimum을 판별하려면 두 번째 미분이 양수여야 한다.

$$f''(x_0)>0$$

여러 변수 함수에서는 두 번째 미분 하나가 아니라 second derivative matrix가 등장한다.

이를 Hessian matrix라고 한다.

2변수 함수 $f(x,y)$의 Hessian은 다음이다.

$$H= \begin{bmatrix} f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{bmatrix}$$

보통 충분히 매끄러운 함수에서는 mixed partial derivative가 같다.

$$f_{xy}=f_{yx}$$

따라서 Hessian은 대칭행렬이다.

minimum 판별은 다음처럼 정리된다.

1. gradient가 0이어야 한다.
2. Hessian이 positive definite이어야 한다.

즉,

$$\nabla f(x_0)=0$$

이고,

$$H(x_0) \text{ is positive definite}$$

이면 $x_0$는 local minimum이다.

quadratic form $f(x)=x^TAx$의 Hessian은 $2A$이다. $2$는 양수 상수이므로, $A$가 positive definite인지와 $2A$가 positive definite인지는 같은 문제이다.

---

12. Level Curve와 Ellipse

positive definite quadratic form은 level curve가 ellipse가 된다.

예를 들어 다음 식을 생각하자.

$$2x_1^2+12x_1x_2+20x_2^2=1$$

이 식은 positive definite quadratic form을 1로 고정한 것이다.

그래프 $z=x^TAx$가 bowl 모양이라면, 높이 $z=1$에서 잘랐을 때 나오는 단면은 ellipse이다.

반대로 indefinite matrix의 quadratic form은 saddle 모양이고, 같은 방식으로 자르면 hyperbola가 나온다.

즉,

1. positive definite $\rightarrow$ bowl $\rightarrow$ ellipse
2. indefinite $\rightarrow$ saddle $\rightarrow$ hyperbola

로 볼 수 있다.

---

13. $3\times 3$ 예시

다음 행렬을 보자.

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

이 행렬은 대칭행렬이다.

positive definite인지 확인하기 위해 leading principal minors를 보자.

첫 번째 leading principal minor는 다음이다.

$$D_1=2$$

두 번째 leading principal minor는 다음이다.

$$D_2= \begin{vmatrix} 2 & -1 \\ -1 & 2 \end{vmatrix} = 4-1 = 3$$

세 번째 leading principal minor는 전체 determinant이다.

$$D_3=\det A=4$$

따라서,

$$D_1=2>0, \qquad D_2=3>0, \qquad D_3=4>0$$

이다.

모든 leading principal minor가 양수이므로 이 행렬은 positive definite이다.

---

14. $3\times 3$ 예시의 Pivot과 Eigenvalue

위 행렬의 pivot은 다음과 같다.

$$d_1=2$$

두 번째 pivot은 다음이다.

$$d_1d_2=D_2$$

따라서,

$$d_2=\frac{D_2}{D_1} = \frac{3}{2}$$

세 번째 pivot은 다음 관계에서 나온다.

$$d_1d_2d_3=D_3$$

따라서,

$$d_3= \frac{D_3}{D_2} = \frac{4}{3}$$

즉 pivot은 다음과 같다.

$$2,\quad \frac{3}{2},\quad \frac{4}{3}$$

모두 양수이다.

이 행렬의 고유값은 다음이다.

$$\lambda_1=2-\sqrt{2}, \qquad \lambda_2=2, \qquad \lambda_3=2+\sqrt{2}$$

이 값들도 모두 양수이다.

trace를 확인하면,

$$(2-\sqrt{2})+2+(2+\sqrt{2})=6$$

이고, 이는 행렬의 trace와 같다.

$$\operatorname{tr}(A)=2+2+2=6$$

determinant도 확인할 수 있다.

$$(2-\sqrt{2})\cdot 2\cdot (2+\sqrt{2}) = 2(4-2) = 4$$

이는 전체 determinant와 같다.

---

15. $3\times 3$ 예시의 Quadratic Form

위 행렬에 대한 quadratic form은 다음이다.

$$x^TAx = 2x_1^2+2x_2^2+2x_3^2 -2x_1x_2-2x_2x_3$$

대각성분 $2,2,2$는 각각 $2x_1^2$, $2x_2^2$, $2x_3^2$를 만든다.

대각선 밖의 $-1$은 대칭 위치에 두 번 등장하므로 cross term은 다음처럼 $-2$가 붙는다.

$$-2x_1x_2, \qquad -2x_2x_3$$

이 식은 완전제곱으로 다음처럼 쓸 수 있다.

$$x^TAx = 2\left(x_1-\frac{1}{2}x_2\right)^2 +\frac{3}{2}\left(x_2-\frac{2}{3}x_3\right)^2 +\frac{4}{3}x_3^2$$

바깥 계수는 pivot이다.

$$2,\quad \frac{3}{2},\quad \frac{4}{3}$$

모두 양수이므로 이 quadratic form은 $x\neq 0$에서 항상 양수이다.

따라서 $A$는 positive definite이다.

---

16. Ellipsoid와 Principal Axes

$3\times 3$ positive definite matrix에서는 level set

$$x^TAx=1$$

이 ellipsoid가 된다.

2차원에서는 ellipse였고, 3차원에서는 ellipsoid이다. 쉽게 말하면 중심이 원점에 있는 찌그러진 공 모양이다.

대칭행렬은 다음처럼 spectral decomposition을 가진다.

$$A=Q\Lambda Q^T$$

여기서 $Q$의 열벡터들은 orthonormal eigenvectors이고, $\Lambda$는 eigenvalue를 대각성분으로 갖는다.

변수변환

$$x=Qy$$

를 하면,

$$x^TAx = y^T\Lambda y$$

가 된다.

즉,

$$x^TAx = \lambda_1y_1^2+\lambda_2y_2^2+\lambda_3y_3^2$$

이다.

따라서 level set은 다음 형태가 된다.

$$\lambda_1y_1^2+\lambda_2y_2^2+\lambda_3y_3^2=1$$

이 식에서 각 축의 방향은 eigenvector가 결정한다.

각 축의 길이는 eigenvalue가 결정한다.

정확히는 $i$번째 principal axis의 반지름은 다음이다.

$$\frac{1}{\sqrt{\lambda_i}}$$

eigenvalue가 클수록 그 방향의 축 길이는 짧고, eigenvalue가 작을수록 그 방향의 축 길이는 길다.

이것이 principal axis theorem의 기하적 의미이다.

---

17. 전체 흐름 정리

positive definite matrix는 대칭행렬 중에서도 모든 방향에서 quadratic form이 양수인 행렬이다.

가장 본질적인 조건은 다음이다.

$$x^TAx>0 \qquad (x\neq 0)$$

이를 판별하는 방법은 여러 가지이다.

1. 모든 eigenvalue가 양수이다.
2. 모든 pivot이 양수이다.
3. 모든 leading principal minor가 양수이다.
4. quadratic form이 모든 0이 아닌 방향에서 양수이다.

positive definite matrix는 최소화 문제와 직접 연결된다.

1변수 calculus에서 minimum을 판별할 때 second derivative가 양수인지 보는 것처럼, 다변수에서는 Hessian matrix가 positive definite인지 본다.

$$f''(x_0)>0 \quad \longrightarrow \quad H(x_0) \text{ is positive definite}$$

기하적으로는 다음과 같다.

1. positive definite이면 그래프는 bowl 모양이다.
2. level curve는 ellipse 또는 ellipsoid이다.
3. eigenvectors는 principal axes의 방향이다.
4. eigenvalues는 principal axes의 길이를 결정한다.

이번 강의의 핵심은 선형대수의 여러 도구가 positive definite matrix에서 하나로 모인다는 점이다.

pivot, determinant, eigenvalue, quadratic form, minimum, geometry가 모두 같은 현상을 다른 관점에서 설명하고 있다.