[MIT 18.065] 1.7. Symmetric Positive Definite Matrices

---

💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.

1. Introduction

1.2절에서, 1장 전체를 통해 5가지 중요한 분해(factorization)를 다룬다고 하였다.

1. $A=LU$: Elimination
2. $A=QR$: Orthogonalization (Gram-Schmidt)
3. $S = Q \Lambda Q^T$: Eigenvalue, Eigenvector (Spectral Theorem)
4. $A=X \Lambda X^{-1}$: Diagonalization
5. $A=U \Sigma V^T$: Singular Value Decomposition (SVD)

여기서는 3번째 분해인 $S = Q \Lambda Q^T$ 즉 Spectral Theorem에 대해 다루고, positive definite matrix에 대해 다룬다.

2. Spectral Theorem

대칭행렬(Symmetric matrix) $S$에 대해 다음이 성립한다.

• $S$의 모든 eigenvalues $\lambda_1, \lambda_2, \cdots, \lambda_n$는 실수(real number)이다.
• $S$의 eigenvectors $q_1, q_2, \cdots, q_n$는 서로 수직인 벡터들로 선택될 수 있다.

따라서 $S$의 eigenvector matrix $Q$는 orthogonal matrix이다. 따라서 1.6절에 따라 $S = Q \Lambda Q^{-1}$인데, orthogonal matrix는 $Q^{-1} = Q^T$이므로 다음과 같이 쓸 수 있다.

\[S = Q \Lambda Q^T\]

모든 real symmetric matrix $S$는 위 식이 성립하며, 이를 Spectral Theorem이라고 한다. 참고로 $S$가 복소수일 때는 $S^H = \bar{S}^ T = S$이면 eigenvalue가 실수이다.

3. Positive Definite Matrix

이제 positive definite matrix(양의 정부호 행렬)에 대해 다뤄보자. 양의 정부호 행렬은 5가지 방법으로 정의(또는 판정)될 수 있는데, 여기서는 먼저 다음을 소개한다.

Test 1: Eigenvalue Test

Test 1. Positive definite matrix의 eigenvalue는 모두 양수이다.

예를 들어 다음 두 행렬을 보자.

\[S_1 = \begin{bmatrix} 2 & 0 \\ 0 & 6 \end{bmatrix}, \quad S_2 = \begin{bmatrix} 2 & 0 \\ 0 & 0 \end{bmatrix}\]

$S_1$의 eigenvalue는 $\lambda_1 = 2, \lambda_2 = 6$으로 모두 양수이므로 positive definite이다. 반면 $S_2$의 eigenvalue는 $\lambda_1 = 2, \lambda_2 = 0$으로 양수가 아니므로 positive definite가 아니다. 대신 이처럼 eigenvalue $\lambda \geq 0$이면 positive semidefinite라고 한다.

Test 2: Energy Test

Test 2. 모든 $x \neq 0$에 대해 $x^T S x > 0$이면 positive definite이다.

즉, $S$가 positive definite이면 $x^T S x > 0$이다. $x^T S x$는 $x$의 energy라고 하는데, 그 이유는 4절에서 이해할 수 있을 것이다. 기하학적으로 이를 해석해보면 $x$와 그것을 선형변환한 $Sx$ 사이의 각도가 항상 예각이라는 것이다.

Test 1과 Test 2는 연결된다. $Sx = \lambda x$라고 하면 $x^T S x = \lambda x^T x$이고 Test 1에 의해 $\lambda x^T x \gt 0$이므로, 모든 eigenvector $x$에 대해 $x^T S x \gt 0$이다. 이때 모든 벡터 $x \mathbb{R}^n$은 eigenvector의 선형결합으로 표현할 수 있다.

\[x = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\]

$x^T S x$를 계산하면 다음과 같다. $S$가 symmetric matrix이므로 eigenvalue는 서로 orthogonal하다.

\[\begin{aligned} x^T S x &= (c_1 x_1 + c_2 x_2 + \cdots + c_n x_n)^T S (c_1 x_1 + c_2 x_2 + \cdots + c_n x_n) \\ &= c_1^2 \lambda_1 x_1^T x_1 + c_2^2 \lambda_2 x_2^T x_2 + \cdots + c_n^2 \lambda_n x_n^T x_n \gt 0 \end{aligned}\]

따라서 Test 1로부터 Test 2도 얻을 수 있다. 그리고 실제로 제일 많이 사용되는 정의는 Test 2의 energy-based definition이다.

그리고 이로부터 다음 성질도 얻을 수 있다.

$S_1$과 $S_2$가 positive definite이면 $S_1 + S_2$도 positive definite이다.

이유는 다음과 같다.

\[x^T (S_1 + S_2) x = x^T S_1 x + x^T S_2 x \gt 0\]

Test 3. Cholesky Factorization

Test 3. $S$가 positive definite이면 $S = A^T A$로 표현할 수 있는 independent columns로 이루어진 $A$가 존재한다.

$S = LU$ decomposition을 다시 생각해보자. 일부 symmetric matrix는 다음과 같이 분해될 수 있다. 아이디어는 $L L^T$가 symmetric하다는 것과 $LU$ decomposition을 합친 것이다.

\[S = L L^T = L^T L\]

이러한 분해가 가능한 symmetric matrix의 조건을 찾기 위해 $\vert L x \vert \geq 0$임을 생각해보자.

\[\begin{aligned} \vert L x \vert ^2 &= (L x)^T (L x) = x^T L^T L x = x^T S x \geq 0 \end{aligned}\]

따라서 $S$가 positive semidefinite이면 $S = L^T L$로 표현할 수 있는데, 실제로 positive definite인 조건은 조금 더 까다로워서 $L$의 columns가 서로 독립이어야 한다. 따라서 Test 3과 같은 서술이 가능하다. 이러한 분해를 Cholesky factorization이라고 한다.

이번에는 energy 관점에서 서술해보자. $S = A^T A$로 표현할 수 있는 $A$가 존재한다면, $x^T S x = x^T A^T A x = \vert A x \vert^2 \gt 0$이다. 따라서 $S$가 positive definite이려면 $Ax \neq 0$이어야 하므로, $A$의 columns는 서로 독립이다. 그렇지 않다면 $S$는 positive semidefinite이다.

Test 4. Determinant Test

Test 4. $S$가 positive definite이면 leading determinants $D_1, D_2, \cdots, D_n$는 모두 양수이다.

예를 들어 다음과 같다.

Test 5. Pivot Test

Test 5. $S$가 positive definite이면 $S$의 pivot은 모두 양수이다.

Pivot은 elimination 후 diagonal에 남은 수들이다. 예를 들어 determinant test에 사용했던 S에서 첫 번째 pivot은 2이고, $\frac{1}{2}$(row 1)을 row 2에 더하면 두 번째 pivot은 $\frac{3}{2}$가 되는 식이다. 그 다음 pivot은 순서대로 $\frac{4}{3}$, $\frac{5}{4}$이다. 이는 각각 determinant의 비율이다. 즉 다음과 같이 말할 수 있다.

\[k \text{th pivot} = \frac{D_k}{D_{k-1}}\]

따라서 pivot test는 determinant test와 연결되어 있다. 이제 이것들이 어떻게 Cholesky factorization과 연결되는지 살펴보자. 예시 행렬 $S$에 대해 Cholesky factorization을 적용하면 다음과 같다.

$S = LDL^T$로 표현하면, diagonal matrix $D$는 pivot을 가지고 있다. 그리고 $A = \sqrt{D} L^T$이므로 pivot이 양수여야 한다. 따라서 pivot test는 Cholesky factorization과 연결되어 있다.

실제로 $S = A^T A$에서 $A$를 선택하는 방법은 다양하지만, 여기서는 지금까지 공부한 것을 활용하여 두 가지 방법으로 선택할 수 있다.

1. Symmetric: $S = Q \Lambda Q^T$이므로, $A = A^T = Q \sqrt{\Lambda} Q^T$
2. Triangular: $S = LDL^T$이므로, $A = \sqrt{D} L^T$

지금까지 공부한 positive definite matrix의 정의와 판정 방법은 다음과 같다.

1. Eigenvalue Test: 모든 eigenvalue가 양수
2. Energy Test: $x^T S x > 0$
3. Cholesky Factorization: $S = A^T A$ (w/ independent columns)
4. Determinant Test: leading determinants $D_1, D_2, \cdots, D_n$이 모두 양수
5. Pivot Test: $S$의 pivot이 모두 양수

4. Interpretation of Positive Definite Matrix

4.1. Minimum Problems

다음 symmetric positive definite matrix $S$에 대해, 각각의 테스트를 적용할 수 있다.

\[S = \begin{bmatrix} a & b \\ b & c \end{bmatrix}\]

1. Determinants: $a \gt 0, ac - b^2 \gt 0$
2. Eigenvalues: $\lambda_1 \gt 0, \lambda_2 \gt 0$
3. Pivots: $a \gt 0, ac - b^2 / a \gt 0$
4. Energy: $x^T S x = ax^2 + 2bxy + cy^2 \gt 0$

여기서는 편의상 $a=c=5$, $b=4$로 가정하였다. $S$의 eigenvalue는 $\lambda = 9$, $\lambda=1$이다. Energy를 그래프로 나타내면 아래로 볼록한 그릇 모양임을 알 수 있다. 이것이 $x^T S x$가 에너지인 이유이고, $x=y=0$일 때 energy가 최소가 된다.

그리고 최솟값, 극솟값을 찾기 위해서도 positive definite matrix가 이용된다. 함수 $f(x)$가 있을 때 minimum은 다음과 같이 찾을 수 있다.

\[\frac{d f}{d x} = 0, \quad \frac{d^2 f}{d x^2} \gt 0\]

다변수함수에서는 다음과 같다. 먼저 함수 $f(x,y)$가 있을 때 헤시안 행렬(Hessian matrix) $H$를 다음과 같이 정의한다.

\[H = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{bmatrix}\]

이때 minimum은 다음과 같이 찾을 수 있다.

\[\frac{\partial f}{\partial x} = 0, \quad \frac{\partial f}{\partial y} = 0, \quad H \text{ is positive definite}\]

반대로 $H$가 negative definite, 즉 eigenvalue $\lambda \lt 0$이면 maximum이 되고, $H$가 indefinite, 즉 eigenvalue가 양수와 음수가 섞여있으면 saddle point가 된다.

$H$가 모든 점에서 positive definite 혹은 semidefinite이면 convex이고, 특히 eigenvalue가 어떤 양수 $\delta$보다 크면 strictly convex이다. 이러한 함수들은 최적화하기에 아주 좋다.

머신러닝에서도 이를 활용할 수 있다. 즉 minimum을 찾기 위해서는 두 조건을 만족한다.

1. Gradient: $\nabla f(x) = 0$
2. Hessian: $H$ is positive definite

그러나 실제로 머신러닝에는 너무 많은 변수가 있기 때문에 gradient descent를 사용한다. 이는 gradient만 사용하여 minimum을 찾는 방법이다. 즉 $\nabla f(x)$의 방향으로 이동하면서 minimum을 찾는 방법이다.

4.2. Principal Axis Theorem

이제 energy의 한 부분을 보고자 한다. Bowl을 높이 1에서 자르자. 즉 $x^T S x = 1$을 보도록 하자. 그럼 다음과 같은 식을 얻는다.

\[5 x^2 + 8 xy + 5 y^2 = 1\]

이는 ellipse이고, 아래와 같이 나타난다.

$S$의 eigenvector는 다음과 같다.

\[q_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad q_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}\]

이때 energy $x^T S x$는 다음과 같이 나타낼 수 있다.

\[\begin{aligned} x^T S x &= x^T (Q \Lambda Q^T) x = (Q^T x)^T \Lambda (Q^T x) \\ &= (x^T Q) \begin{bmatrix} 9 & 0 \\ 0 & 1 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} \\ &= 9 \left( \frac{x+y}{\sqrt{2}} \right)^2 + 1 \left( \frac{x-y}{\sqrt{2}} \right)^2 \end{aligned}\]

따라서 ellipse의 axes는 $q_1, q_2$, 그 길이는 $\frac{1}{\sqrt{\lambda_1}}, \frac{1}{\sqrt{\lambda_2}}$이다. 이를 보고 $S = Q \Lambda Q^T$를 principal axis theorem이라고도 한다. Eigenvector는 axes를 나타내고, eigenvalue는 길이를 나타낸다.

5. Selected Solutions to Problems

Problem 10.

Q. $A: m \times n$ matrix, $S: m \times m$ symmetric matrix일 때 $A^T S A$도 symmetric matrix임을 보여라. $S$의 eigenvalue와 $A^T S A$의 eigenvalue가 같은가?

$A^T S A$는 다음과 같은 이유로 symmetric하다.

\[(A^T S A)^T = A^T S^T (A^T)^T = A^T S A\]

그리고 $S$의 eigenvalue와 $A^T S A$의 eigenvalue는 다르다. 그러나 $A$가 square matrix이고 invertible이면 $A^T S A$는 $S$에 congruent(합동)이라고 하고, eigenvalue의 값은 같지 않지만 부호는 같다. 이를 Law of Inertia(관성의 법칙)이라고도 한다.

Problem 11.

Q. $S$의 eigenvalue $\lambda_1, \lambda_2$ 사이에 $a$가 존재함을 보여라.

\[S = \begin{bmatrix} a & b \\ b & c \end{bmatrix}\]

$\det(S - \lambda I) = 0$을 풀면 다음과 같다.

\[\begin{aligned} \det(S - \lambda I) &= \begin{vmatrix} a - \lambda & b \\ b & c - \lambda \end{vmatrix} \\ &= (a - \lambda)(c - \lambda) - b^2 \\ &= \lambda^2 - (a+c) \lambda + ac - b^2 = 0 \end{aligned}\]

이를 이차함수 $f(\lambda)$로 나타내면 다음과 같다.

\[f(\lambda) = \lambda^2 - (a+c) \lambda + ac - b^2\]

그런데 $f(\lambda=a) = -b^2 \lt 0$이므로 $a$는 두 근 $\lambda_1, \lambda_2$ 사이에 존재한다. 이를 일반화하면 다음과 같다.

$A$의 $n-1$개의 eigenvalue는 $S$의 $n$개의 eigenvalue 사이에 있다.

\[S = \begin{bmatrix} A & b \\ b^T & c \end{bmatrix}\]

Problem 19.

Q. Symmetric matrix $S$의 diagonal entry $s_{jj}$는 임의의 eigenvalue $\lambda$보다 작을 수 없음을 보여라.

$Sq = \lambda q$라고 하면, $(S - s_{jj}I)q = (\lambda - s_{jj})q$이다. 만약 $s_{jj} \lt \lambda$라면, eigenvalue $\lambda - s_{jj} \gt 0$이 되어 $S - s_{jj}I$는 positive definite가 된다. 그러나 $S - s_{jj}I$의 $j$번째 행, $j$번째 열의 diagnonal entry는 $s_{jj} - s_{jj} = 0$이므로 positive definite가 아니다. 따라서 $s_{jj} \geq \lambda$이다.

Problem 26.

Q. 다음 $S$에 대하여 determinant, eigenvalues, eigenvectors를 구하고 $S$가 symmetric positive definite인지 판정하라.

\[S = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 5 \end{bmatrix} \begin{bmatrix} \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{bmatrix}\]

여기서 rotation matrix $Q$를 다음과 같이 나타낼 수 있다.

\[Q = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}\]

따라서 $S = Q \Lambda Q^T$이다. 그러므로 $S$의 determinant는 $\det(S) = \det(Q \Lambda Q^T) = \det(Q) \det(\Lambda) \det(Q^T) = \det(\Lambda) = 10$이다. 그리고 eigenvalues는 $\lambda_1 = 2, \lambda_2 = 5$이다. 마지막으로 eigenvectors는 다음과 같다.

\[\begin{aligned} q_1 = \begin{bmatrix} \cos \theta \\ \sin \theta \end{bmatrix}, \quad q_2 = \begin{bmatrix} -\sin \theta \\ \cos \theta \end{bmatrix} \end{aligned}\]

모든 $\lambda$가 양수이므로 $S$는 positive definite이다. 또는 energy test에 의해 $x^T S x = (x^T Q) \Lambda (Q^T x)$이므로 positive definite임을 알 수 있다.

Problem 28.

Q. Positive definite matrix $S$의 eigenvalues $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$일 때 다음에 답하라.

(a) $\lambda_1 I - S$의 eigenvalue를 구하고, positive semidefinite인지 판정하라. (b) $x^T S x / x^T x$의 최댓값을 구하라.

(a) $\lambda_1 I - S$의 eigenvalue는 $\lambda_1 - \lambda_i$이다. 이는 $\lambda_1 - \lambda_i \geq 0$이므로 positive semidefinite이다. (b) (a)에서 $\lambda_1 I - S$가 semidefinite이므로 다음이 성립한다.

\[x^T (\lambda_1 I - S) x \geq 0 \therefore \lambda_1 x^T x \geq x^T S x\]

따라서 $x^T S x / x^T x$의 최댓값은 $\lambda_1$이다.

MIT 18.065 카테고리 내 다른 글 보러가기