[선형대수] Lecture 27: Positive definite matrices and minima

https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/

이번 강의에서는 다음과 같은 내용을 다룬다.

• Postiive Definite Matrix
  • 증명 방법
  • 기하학적 측면

---

우선 Positive Definite Matrix 의 특징은 다음과 같다.

위와 같은 $A$ 행렬이 주어질 때, 해당 행렬이 Positive Definite Matrix 인지를 확인하는 방법은 다음과 같다.

1. $\lambda_1>0,\lambda_2>0$

   • 모든 고유값이 0보다 큰지.

2. $a>0,ac-b^2>0$

   • 모든 determinations 가 0보다 큰지

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

   • 모든 pivtos 이 0보다 큰지

4. $x^TAx>0$ (except at $x=0$)

   • 이 조건이 가장 중요하다. 이 조건을 통해서 위 조건들이 나온다.

---

예시를 통해서 알아보자.
ex.

위 행렬이 PDM (Positive Definite Matrix) 이기 위해서는 $?$ 가 어떤 값이어야 할까?

아마 위 조건(2, 3)을 따져봤을 때, $?>18$ 이어야 할 것이다.
그렇다면 18일 경우에는 어떨까? 값을 대입해보자.

위 행렬은 singular matrix 이다. 따라서 determination(=0)을 통해 $\lambda_1=0$ 일 것이고, trace(=20)를 통해서 $\lambda_2=20$ 이라는 것을 알 수가 있다. 그리고 $pivot=2$ 이다.

• $\lambda_1=0,\lambda_2=1$
• $pivot=2$

다음으로 $x=\begin{bmatrix}x_1 \\ x_2\end{bmatrix}$ 라고 해보자.
그리고 4번 조건 $x^TAx>0$ 를 보자.

그리고 아까 $A=\begin{bmatrix}a & b \\ b & c\end{bmatrix}=\begin{bmatrix} 2 & 6 \\ 6 & 18 \\ \end{bmatrix}$ 를 봤을 때 다음과 같다는 것을 알 수 있다.

(위 수식은 linear form 이 아닌 quadratic form 임을 알 수 있다.)

위 조건을 잘 기억해두고 다음 예시들을 보자.

---

만약 $A$가 다음과 같다면 어떨까?

이 경우 $(x_1,x_2)=(-1,-1)$ 에서 $2x_1^2+12x_1x_2+7x_2^2 <0$ 임을 알 수가 있으며, 따라서 PDM 가 아님을 알 수 있다.
그리고 이를 그래프로 그려보면 아래와 같은 모양으로 나올 것이다.
(https://davidlibland.github.io/posts/2018-11-10-saddle-points-and-sdg.html)

즉, (0,0) 을 기준으로 positive 부분과 negative 부분이 나뉘게 되며, 이때 (0,0)을 saddle point 라고 부른다.

---

다음으로 만약 $A$가 다음과 같다면 어떨까?

우선 determination(=4) 와 trace(=22) 를 보고 $\lambda_1,\lambda_2>0$ 임을 알 수가 있다.
그리고 $f(x_1,x_2)$를 그래프로 그리면 다음과 같은 모양일 것이다.

(https://stackoverflow.com/questions/45650695/how-to-plot-the-typical-bowl-shape-when-illustrating-gradient-descent-with-matpl)

이러한 모양의 함수를 bowl-shaped function 이라고 한다.
그리고 minimum (minima) point가 (0,0) 임을 알 수가 있다. 즉, 첫 번째 미분값은 0이다.

그리고 두 번째 미분값은 0보다 클 것이다.

그리고 2nd Derives Matrix 행렬로 표현하면,

이 되고, 이 행렬은 Positive Definite Matrix 일 것이다. ($f_{x_1x_2}=f_{x_2x_1}$)

그리고 이어서 아까의 수식을 보자.

위 수식에서 다음과 같은 정보를 알 수가 있다.

• 아까 $A = \begin{bmatrix} 2 & 6 \\ 6 & 18 \\ \end{bmatrix}$ 에서의 18은 $2(x_1+3x_2)^2$ 에서 $x_2^2$의 계수가 된다.
• 그리고 $2(x_1+3x_2)^2+2x_2^2$ 에서 각각의 $2$ 는 $A\to\begin{bmatrix} 2 & 6 \\ 0 & 2 \\ \end{bmatrix}$ 에서 pivot 값이다.
• 그리고 $2(x_1+3x_2)^2$ 에서 $3$ 은 $L=\begin{bmatrix} 1 & 0 \\ 3 & 1 \\ \end{bmatrix}$의 3으로, 즉 multiplier 를 의미한다.

따라서, 아까 $A=A=\begin{bmatrix} 2 & 6 \\ 6 & ? \\ \end{bmatrix}$에서, $?=18$인 $2x_1^2+12x_1x_2+18x_2^2$ 식을 정리하면 다음과 같이 나오고,

이 값이 0보다 크기 위해서는 뒤에 나오는 pivot 값이 0보다 커야 한다는 것을 알 수가 있다..

---

그리고 $f(x_1,x_2)=2x_1^2+12x_1x_2+20x_2^2=2(x_1+3x_2)^2+2x_2^2$ 과 같은 bowl-shaped function 에서 $z=1$ 꼴로 평면을 그어보면,
$f(x_1,x_2)=2x_1^2+12x_1x_2+20x_2^2=2(x_1+3x_2)^2+2x_2^2=1$
해당 그래프 모양은 타원형을 가짐을 알 수가 있다.

---

다음으로 3x3 행렬을 예시로 해보자.

다음과 같이 정리할 수 있다.

• determinations : $2,3,4$

  • $\det \begin{bmatrix} 2 \end{bmatrix}= 2$

  • $\det \begin{bmatrix} 2 & -1 \\ -1 & 2 \\ \end{bmatrix}= 3$

  • $\det\begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \\ \end{bmatrix} = 4$

• pivots : $2,\frac{2}{3},\frac{3}{4}$

  • $\det_1:2$

  • $\frac{\det_1}{\det_2}=\frac{2}{3}$

  • $\frac{\det_2}{\det_3}=\frac{3}{4}$

• eigenvalues : $2-\sqrt 2, 2, 2 + \sqrt 2$

  • $2+2+2=2-\sqrt 2+ 2+ 2 + \sqrt 2$

  • $4=(2-\sqrt 2) \times (2) \times (2 + \sqrt 2)$

• $x^TAx=2x_1^2+2x_2^2+2x_3^2-2x_1x_2-2x_2x_3>0?$