양의 정부호 행렬(positive definite matrix)

참고1
참고2

1. 양의 정부호 행렬(positive definite matrix)의 정의

양의 정부호 행렬(positive definite matrix)는 영벡터가 아닌 임의의 열벡터 x와 대칭 행렬 A에 대해 다음이 성립한다면 A는 양의 정부호(positive definite) 행렬이다.
$x^TAx >0$

2. 양의 정부호(positive definite)의 의미

변수가 하나인 다음과 같은 이차 함수가 있다고 하자.
$y=x^2+4x+8$
이 함수를 다시 정리하면,
$y=(x+2)^2+4$
x=-2일 때 극값 4를 갖는다는 것을 알 수 있다. 이 극값 4는 극소값이면서 또 이 함수의 최소값이다.
극값을 알기 위해서는 함수를 일차 미분한다.
$\cfrac{dy}{dx}=2x+4=0$
x가 -2일 때 극점을 갖는다는 것을 알 수 있다. x=-2를 y에 대입하면 y=4가 나오므로 점(-2,4)가 극점이고 4가 극값이다.
이 극점이 극소점인지 극대점인지 결정하기 위해서 y를 이차미분한다.
$\cfrac{d^2y}{dx^2}=2>0$
두번 미분한 결과 양수가 나왔으므로 점(-2, 4)는 극소점임을 알 수 있다. 그러니까 일차미분을 통해서 어디에서 극점이 존재하는지를 알 수 있고, 이차미분을 통해서는 그 점이 극소점인지 극대점인지 판단할 수 있다.
이번에는 변수가 2개인 이차함수(이변수함수) 를 생각해 보자.
$f(x,y)=2x^2+4xy+4y^2$
이와 같은 이변수함수는 극소점 또는 극대점을 가질 수도 있고, 아니면 안장점(saddle point)를 가질 수도 있다. 안장점(saddle point)는 극값을 중심으로 x축으로는 극소값, y축으로는 극대값 혹은 그 반대가 되는 점이다. 다음 그림에서 좌표(0,0)이 안장점이다.

이변수 함수에서도 마찬가지로 극점을 찾으려면 1차 미분을 해야 한다. 변수가 2개라서 x, y 각각에 대해 편미분을 해야 한다.
$\cfrac{\delta f}{\delta x}=4x+4y=0 \\ \cfrac{\delta f}{\delta y}=4x+8y=0$
위 두 식을 0으로 만드려면 x와 y가 모두 0이어야 한다. 즉, 점(0, 0)에서 극소점 또는 극대점 또는 안장점을 갖는다. 이 점을 정류점(stationary point) 또는 임계점(critical point)이라고 부른다. 즉, 정류점은 극소점, 극대점, 안장점 모두를 포함하는 개념이다.
그러면 이처럼 변수가 두개인 함수의 정류점이 극소점인지 극대점인지 안장점인지 결정하기 위해서는 어떻게 해야할까? 변수가 하나일 때와 다르게 단순히 이차미분하는 것으로는 결정할 수 없다. 일단 식을 다음과 같이 변형시켜 보자.
$f(x,y)=2x^2+4xy+4y^2 \\ =2(x^2+2xy+y^2)+2y^2 \\ =2(x+y)^2+2y^2$
두 항 모두 제곱의 형태이므로 0보다 크거나 같다. f(x, y)는 점(0, 0)을 제외하고는 모두 다 0보다 큰 값을 갖는다. 이것을 두고 바로 양의 정부호(positive definite) 라고 칭한다.

그림과 같이 양의 정부호인 경우에는 그래프가 그릇과 같은 형태가 된다. 점(0, 0)에서 최소값을 갖고 나머지는 모두 다 0보다 크다.

3. 이변수함수가 양의 정부호(positive definite), 음의 정부호(negative definite), 안장(saddle) 중에 무엇인지 판단하는 방법

앞에서 설명한 것은 변수가 2개인 이차함수(이변수함수) 중 양의 정부호(positive definite)에 해당하는 특정한 함수를 예로 든 것이고 이를 좀 더 일반화시키면 다음과 같다.
$f(x,y)=ax^2+2bxy+cy^2$
이 함수도 제곱항들로만 구성되게 식을 만들어 보면,
$f(x,y)=ax^2+2bxy+cy^2 \\ =a(x^2+\cfrac{2b}{a}xy+\cfrac{b^2}{a^2}y^2-\cfrac{b^2}{a^2}y^2)+cy^2 \\ =a(x+\cfrac{b}{a}y)^2+(c-\cfrac{b^2}{a})y^2$
$f(x,y)$가 양의 정부호가 될려면 우선 a > 0이어야 한다.그러면 첫번째 항은 (0,0)을 제외하고 항상 0보다 커진다. 두번째 항도 0보다 커질려면 계수가 0보다 커야한다. 즉 $c-\cfrac{b^2}{a}>0$이어야 한다.
정리하면,
$c-\cfrac{b^2}{a}>0 \\ \Leftrightarrow c>\cfrac{b^2}{a} \\ \Leftrightarrow ac>b^2\,(\because a>0)$
반대로 음의 정부호(negative definite)가 되려면,
일단 $a<0$이어야 하고,
$c-\cfrac{b^2}{a}<0 \\ \Leftrightarrow c<\cfrac{b^2}{a} \\ \Leftrightarrow ac>b^2\,(\because a<0)$

• 양의 정부호(positive definite)가 되는 조건
  $a>0,\,ac>b^2$ 이면, $f(x,y)=ax^2+2bxy+cy^2$은 양의 정부호(positive definite)이다.
• 음의 정부호(negative definite)가 되는 조건
  $a<0,\,ac>b^2$ 이면, $f(x,y)=ax^2+2bxy+cy^2$은 음의 정부호(negative definite)이다.

앞에서 $f(x,y)=2x^2+4xy+4y^2$는 양의 정부호를 갖는다 했는데 -1을 곱하면 음의 정부호인 함수가 된다. 그래프를 그리면 다음과 같다.

위의 그림과 같이 $f(x,y)=-2x^2-4xy-4y^2$는 그릇이 뒤집어진 형태의 그래프를 갖는다. 또한 점(0, 0)이 극대점이고, 그 외의 모든 점은 음수값을 갖는다.
다음은 안장(saddle)점을 갖는 경우이다.
양의 정부호, 음의 정부호 모두 $ac>b^2$이었는데, 안장점인 경우는 $ac<b^2$인 경우이다.
$f(x,y)=x^2-y^2$은 a=1, b=0, c=-1인 경우이다. 따라서 $ac<b^2(1*(-1)<0^2)$인 경우이다.

그래프를 보니 말 안장같이 생겼다. 이 그래프 모양때문에 이러한 특성의 함수에 안장이라는 이름이 붙여진 것이다. 점(0, 0)에서 안장점을 갖는데, 흥미로운 것은 x축 방향에서 이 그래프를 보면 점(0, 0)은 극소점처럼 보인다. 그런데 y축 방향에서 보면 점(0, 0)은 극대점처럼 보인다.

• 안장(saddle)이 되는 조건
  $ac<b^2$이면 $f(x,y)=ax^2+2bxy+cy^2$은 안장(saddle)이다.

4. 다변수 함수일때 양의 정부호인지 음의 정부호인지 안장인지 판단하는 방법

4.1 이변수 함수 또는 다변수 함수를 행렬로 표현하기

$ax^2+2bxy+cy^2=x^TAx \\ =\begin{bmatrix} x &y \\ \end{bmatrix} \begin{bmatrix} a &b \\ b &c \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix}$
예를 들어보면,
$A=\begin{bmatrix} 2 &2 \\ 2 &1 \\ \end{bmatrix}$
인 경우, a=2, b=2, c=1이므로 $a>0$ 이고 $ac<b^2$이다. 따라서 행렬 A는 안장(saddle) 행렬이다.

다음은 다변수인 경우이다.
$\begin{bmatrix} x_1 &x_2 &... &x_n \\ \end{bmatrix} \begin{bmatrix} a_{11} &a_{12} &... &a_{1n} \\ a_{21} &a_{21} &... &a_{2n} \\ \vdots &\vdots &\ddots &\vdots \\ a_{n1} &a_{n2} &... &a_{nn} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{bmatrix} \\ =\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}x_ix_j \\ =a_{11}x_1^2+2a_{12}x_1x_2+...+a_{nn}x_n^2$
행렬 A가 $3\times 3$이상인 경우는 이변수 함수처럼 a,b,c변수를 이용해서 판단할 수 없다.
x가 0벡터인 경우를 제외하고 $x^TAx>0$이면 양의 정부호(positive definite)인데 이를 어떻게 알 수 있을까?

5. 어떤 행렬이 양의 정부호인지를 알 수 있는 방법

아래 5가지 방법 중 하나를 통과하면 그 행렬은 바로 양의 정부호(positive definite)행렬이다.

1. 0이 아닌 모든 실수 벡터에 대해서 $x^TAx>0$을 만족한다.
   <증명>
   이것은 별도로 증명할 필요가 없다. 단지 양의 정부호 행렬에 대한 정의이기 때문이다.
2. 행렬 A의 모든 고유값들이 0보다 크다.
   <증명>
   행렬 A가 양의 정부호($x^TAx>0$)라는 가정하에 행렬 A의 모든 고유값들이 양수라는 것을 증명하면 된다.
   $Ax=\lambda x$ 이므로
   $x^TAx=x^T\lambda x=\lambda\left\|x \right\|^2=\lambda(x_1^2+x_2^2+...+x_n^2)$
   여기서 $x^TAx>0$이면 $\lambda$는 반드시 양수가 되어야 한다. 즉 행렬 A가 양의 정부호이면 A가 고유값, 고유벡터로 표현될 때 모든 고유값은 양수이다.
3. 행렬 A의 모든 서브행렬들(상위 왼쪽 서브행렬들)의 행렬식들이 0보다 크다.
   왼쪽 상위 서브행렬(submatrix)은 선행 주부분 행렬(leading principal submarix)라고도 하며 좌측 상단 1행 1열을 시작점으로 차원을 하나씩 키운 모든 정방행렬(square matrix) 중의 하나이다.
   예를 들어 $3\times 3$행렬의 모든 선행 주부분 행렬은 다음과 같다.
   $\begin{bmatrix} a_{11} \end{bmatrix},\, \begin{bmatrix} a_{11} &a_{12} \\ a_{21} &a_{22} \\ \end{bmatrix},\, \begin{bmatrix} a_{11} &a_{12} &a_{13} \\ a_{21} &a_{22} &a_{23} \\ a_{31} &a_{32} &a_{33} \\ \end{bmatrix}$
   <증명>
   행렬 A가 양의 정부호라면 A의 모든 고유값들은 양수이다.(바로 앞의 2번에서 증명하였다.) 그리고 A의 행렬식은 모든 고유값들의 곱이므로($det(A)=\lambda_1\lambda_2,...,\lambda_n$) 행렬식도 양수이다.(증명은 여기를 참조하라.)
   모든 선행 주부분 행렬(leading principal submarix)을 고려하기 위해, 열벡터에서 처음 $k$개의 성분은 $x_i$이고 마지막 $n-k$개의 성분은 항상 0이라고 생각하자.(x는 임의의 열 벡터이기 때문이다.) 그러면 식은 다음처럼 간략화된다.
   $\mathbf{ x^TAx}= \begin{bmatrix} x_k^T &0 \\ \end{bmatrix} \begin{bmatrix} A_k &* \\ \ast &* \\ \end{bmatrix} \begin{bmatrix} x_k \\ 0 \end{bmatrix} =\mathbf{x_k^TA_kx_k}$
   (위 식에서 x, A, 0는 모두 vector라 굵은 글자로 표현되어야 하는데 markdown에서는 matrix의 bold font처리가 안되어 일반 폰트로 표기하였다. 특히 0은 0하나가 아니라 0이 1개 이상의 vector이다.)
   $x^TAx$가 양수라면 $x^TAx$의 subset인 두 번째 식도 양수이고(x가 전부가 0이 아니면 어떠한 실수도 올 수있는 임의의 열 벡터이기 때문이라 일부분이 0인 형태도 $x^TAx$이다.), 두번째 식을 계산한 세번째 식 $x_k^TA_kx_k$도 양수이다.
   $x_k^TA_kx_k$가 양수이므로 $A_k$는 양의 정부호이고 동시에 모든 고유값이 양수이다. 따라서 $A_k$의 행렬식(determinant)도 양수이다. $det(A_k)>0$이므로 A가 양의 정부호일때 A의 모든 선행 주부분 행렬(leading principal submatrix)의 행렬식은 양수이다.
   정리하면 A가 양의 정부호이면, 1) $x^TAx$>0 $\rightarrow$ 2) $x^TAx$에서 처음 k개 다음이 0인 형태도 양수 $\rightarrow$ 3) $x_k^TA_kx_k$>0 $\rightarrow$ 4) $A_k$는 양의 정부호 $\rightarrow$ 5) $det(A_k)>0$
4. 행렬 A의 모든 피봇들이 0보다 크다.
   <증명>
   가우스 소거법(Gaussian Elimination)은 선형대수학(linear algebra)에서 연립일차방적식을 행렬을 이용해서 푸는 방법인데, 행렬에 가우스 소거법을 이용하면 상삼각 행렬(upper triangular matrix)이 자연스럽게 얻어진다. 여기서 k번째 pivot(행렬의 대각 원소)은 행렬식의 비율($\frac{det(A_k)}{det(A_{k-1})}$)와 같다. 앞의 증명 3에 의하여 행렬 A가 양의 정부호이면 모든 선행 주부분 행렬의 행렬식($det(A_k)$)는 양수이기 때문에 행렬 A의 모든 pivot값은 양수이다.
   k번째 pivot(행렬의 대각 원소)은 행렬식의 비율과 같다의 증명
   다음과 같은 $2\times 2$ 행렬 A가 있다고 하자.
   $A=\begin{bmatrix} a &b \\ b &a \\ \end{bmatrix}$
   가우스 소거법에 의해 첫번째 pivot인 1행1열의 a를 2행1열의 b로 나누고 이를 1행에 곱하여 2행에 빼준다.($R(2)-R(1)*(\frac{b}{a})$)
   $\begin{bmatrix} a &b \\ b &c \\ \end{bmatrix} \rightarrow \begin{bmatrix} a &b \\ 0 &c-\cfrac{b^2}{a} \\ \end{bmatrix} = \begin{bmatrix} a &b \\ 0 &\cfrac{ac-b^2}{a} \\ \end{bmatrix}$
   가우스 소거법에 의한 상삼각 행렬에서 첫번째 pivot $d_1$은 $a=det(A_1)$이고, 두번째 pivot $d_2$는 $\cfrac{ac-b^2}{a}=\cfrac{det(A_2)}{det(A_1)}$이다. 따라서 가우스 소거법에 의한 행렬의 k번째 pivot은 $\cfrac{det(A_k)}{det(A_{k-1})}$ 이다.
5. 행렬 A가 $R^TR$로 분해되고 행렬 R이 선형독립인 열벡터를 가지는 행렬 R이 존재한다.
   $\mathbf{x^TAx=x^TR^TRx=(Rx)^TRx=\left\|Rx \right\|^2>0}$
   즉 $A=R^TR$을 만족하며 R이 선형독립인 열벡터를 가지고 있는 R이 존재한다면 $x^TAx>0$이고 행렬 A는 양의 정부호(positive definite) 이다.

6. 양의 정부호(positive definite) 행렬 예제

<예제1>
다음 행렬이 양의 정부호 행렬인가?
$A=\begin{bmatrix} 2 &-1 &0 \\ -1 &2 &-1 \\ 0 &-1 &2 \\ \end{bmatrix}$
앞의 5가지 방법 중 3번째 방법으로 확인해보자.
모든 선행 주부분 행렬(leading principal submatrix)의 행렬식이 0보다 큰지를 확인하면 되므로,
$det(A_1)=\begin{vmatrix}2\end{vmatrix}=2$
$det(A_2)= \begin{vmatrix} 2 &-1 \\ -1 &2 \\ \end{vmatrix}= 2\cdot2-(-1)\cdot(-1)=4-1=3$
$det(A_3)= \begin{vmatrix} 2 &-1 &0 \\ -1 &2 &-1 \\ 0 &-1 &2 \\ \end{vmatrix} = 2\begin{vmatrix} 2 &-1 \\ -1 &2 \\ \end{vmatrix} -(-1)\begin{vmatrix} -1 &-1 \\ 0 &2 \\ \end{vmatrix} +0\begin{vmatrix} -1 &2 \\ 0 &-1 \\ \end{vmatrix}=2(4-1)+(-2-0)+0=6-2=4$
모든 선행 주부분 행렬(leading principal submatrix)이 2, 3, 4로 0보다 크므로 행렬 A는 양의 정부호이다.

이번에는 2번째 방법인 모든 고유값이 0보다 큰지를 통해서 확인해 보겠다.
$Av=\lambda v$에서 $(A-\lambda I)v=0$이므로 고유벡터 v가 0이 아니려면 $(A-\lambda I)$의 역행렬이 존재하지 않아야 한다.
$det(A-\lambda I)= \begin{vmatrix} 2-\lambda &-1 &0 \\ -1 &2-\lambda &-1 \\ 0 &-1 &2-\lambda \\ \end{vmatrix}=0$
$(2-\lambda)\begin{vmatrix} 2-\lambda &-1 \\ -1 &2-\lambda \\ \end{vmatrix} -(-1)\begin{vmatrix} -1 &-1 \\ 0 &2-\lambda \\ \end{vmatrix} +0 =(2-\lambda)((2-\lambda)^2-1)-(2-\lambda)\\=(2-\lambda)^3-2(2-\lambda)=(2-\lambda)(2-4\lambda+\lambda^2)=0$
$\lambda=2,\,2\pm \sqrt{2}$
모든 고유값들이 0보다 크다. 따라서 행렬 A는 양의 정부호이다.