2020년 8월 30일 일요일

양의 정부호 행렬(陽의 正符號, Positive Definite Matrix)

[경고] 아래 글을 읽지 않고 "양의 정부호 행렬"을 보면 바보로 느껴질 수 있습니다.


[그림 1] 최소값을 가진 함수(출처: wikipedia.org)

2차 형식(quadratic form) $q({\bf x})$가 열 벡터(column vector) $\bf x$에 관계없이 항상 $0$보다 크다면, 2차 형식을 구성하는 대칭 행렬(symmetric matrix) $\bf A$를 양의 정부호 행렬(陽의 正符號, positive definite matrix)이라 한다.

                  (1)

양의 정부호 행렬을 정의한 식 (1)에도 약점은 있다. 식 (1)은 임의의 열 벡터 $\bf x$에 대해 성립하지만, 안되는 경우가 딱 하나 존재한다. 바로 $\bf x$ = $\bf 0$이 문제이다. 만약 열 벡터가 $0$이라면, 식 (1)은 당연히 $0$이 되어서 양의 정부호가 될 수 없다. 그래서 2차 형식이 항상 $0$보다 크고 $0$이 되는 예외는 열 벡터가 $0$인 조건을 강조해서 엄격한 양의 정부호 행렬(strictly positive definite matrix)이란 표현도 쓴다. 하지만 열 벡터는 $0$이 아니라는 상태에서 식 (1)을 보기 때문에, 엄격한이란 수식어는 양의 정부호 행렬에서는 불필요해서 생략한다. 또한 식 (1)에서 $\bf A$를 대칭 행렬로 제한했지만 반대칭 행렬(skew-symmetric matrix)2차 형식이 0이므로, 임의 행렬을 가지고 2차 형식을 구성해도 결국은 식 (1)처럼 대칭 행렬에 대한 2차 형식으로 바뀐다. 여러 특성을 가진 2차 형식 중에서 항상 $0$보다 큰 양의 정부호를 고려하는 이유는 무엇일까? [그림 1]과 같은 최소값을 가진 함수를 고려하자. 이 함수는 항상 $0$보다 크기 때문에 항상 최소값을 가진다. 어디가 최소인지는 구체적으로 모르지만, 양의 정부호 함수(positive definite function)라서 최소값의 존재성은 보장된다. 따라서 양의 정부호 행렬로 구성한 2차 형식은 항상 최소값이 존재한다. 이런 특성은 비용 함수(cost function)의 최적화(optimization)를 할 때 매우 편리하다. 우리가 고려하는 행렬이 양의 정부호를 가진다면, 이 행렬로 만든 2차 형식은 항상 최소값이 존재한다. 그래서 적절한 최적화 방법을 사용해서 비용 함수의 최소값을 탐색할 수 있다. 
양의 정부호 행렬의 정의는 식 (1)처럼 매우 간단하다. 하지만 영 벡터(zero vector) $\bf 0$을 제외한 임의의 $\bf x$에 대해 식 (1)이 성립해야 양의 정부호이므로, 실제 적용에는 어려움이 많다. 그래서 간단하게 양의 정부호 행렬을 판정하는 방법을 알아본다.

[양의 정부호 행렬의 판정법] [1]
(a) 대칭 행렬 $\bf A$의 모든 고유치(eigenvalue)는 $0$보다 크다.
(b) 모든 선행 주부분 행렬(leading principal submatrix)의 행렬식은 $0$보다 크다.
(c) 행을 교환하지 않은 모든 추축(pivot)은 $0$보다 크다.

[명제 (a)의 증명]
대칭 행렬의 고유치는 항상 실수이어서 고유치의 대소를 구별할 수 있다. 제$i$번째 단위 고유 벡터(unit eigenvector) $\hat {\bf x}_i$에 대해 다음이 성립한다.

                  (2)

만약 고유치 $\lambda_i$가 $0$보다 크다면, $\hat {\bf x}_i$에 대해서 $\bf A$는 양의 정부호가 된다. 다음 단계로 임의의 열 벡터를 고유 벡터의 선형 결합(linear combination)으로 표현하자.

                  (3)

식 (3)을 이용해 2차 형식을 만들면 다음과 같다.

                  (4)

여기서 단위 고유 벡터는 서로 직교한다. 식 (4)는 상수 $\alpha_i$에 대해 항등 관계이므로, 양의 정부호가 되기 위해서는 모든 고유치가 항상 $0$보다 커야 한다. 혹은 고유치가 $0$보다 크면, $\bf A$는 양의 정부호 행렬이 된다.

[명제 (b)의 증명]
선행 주부분 행렬은 좌측 상단 원소를 반드시 포함하는 주부분 행렬(principal submatrix)이다. 예를 들어 3행 3열인 행렬의 모든 선행 주부분 행렬은 다음과 같다.

                          (5)

모든 고유치의 곱은 행렬식과 같으므로 $\bf A$가 양의 정부호라면, 명제 (a)에 의해 고유치가 $0$보다 커서 행렬식은 항상 $0$보다 크다. 모든 선행 주부분 행렬을 고려하기 위해, 열 벡터에서 처음 $k$개의 성분은 $x_i$이고 마지막 $n-k$개의 성분은 항상 $0$이라 생각한다.[∵ $\bf x$는 임의의 열 벡터이기 때문이다.] 그러면 2차 형식은 다음처럼 간략화된다.

                  (6)

여기서 ${\bf x}_k$는 크기가 $k$인 열 벡터, ${\bf A}_k$는 차원이 $k \times k$인 행렬이다. 행렬 $\bf A$가 양의 정부호라면, 식 (6)의 우변이 항상 $0$보다 커야 한다. 그러면 ${\bf A}_k$의 행렬식이 반드시 $0$보다 커야 한다. 따라서 모든 선행 주부분 행렬의 행렬식이 $0$보다 커야만 $\bf A$는 양의 정부호를 가진다.

[명제 (c)의 증명]
가우스 소거법(Gaussian elimination)을 적용하면 상삼각 행렬(upper triangular matrix)이 자연스럽게 얻어진다. 그래서 제$k$번째 추축(樞軸, pivot) $d_k$는 행렬식의 비율 $|{\bf A}_k|/|{\bf A}_{k-1}|$와 같다. 명제 (b)에 의해 $\bf A$가 양의 정부호라면, 모든 선행 주부분 행렬의 행렬식은 양수이다. 따라서 추축도 항상 $0$보다 커야 한다. 반대로 추축이 $0$보다 클 경우, $\bf A$의 특성을 살펴보자. 행렬 $\bf A$는 대칭이므로, 다음 관계를 얻을 수 있다.

                  (7)

여기서 ${\bf A}$ = ${\bf LD}{\bf L}^T$, $\bf D$ = $\operatorname{diag}(d_1, d_2, \cdots, d_n)$, ${\bf R}_i$는 ${\bf L}^T$의 제$i$번째 행 벡터이다. 따라서 제$i$번째 추축 $d_i$가 $0$보다 크면, $\bf A$는 양의 정부호가 된다.
______________________________

선행 주부분 행렬로 만든 식 (6)을 다음처럼 뒤집어도 성립한다.

                  (8)

즉, 처음 행이 아닌 마지막 행에서 커지는 부분 행렬을 만들어도 양의 정부호 행렬을 판정할 수 있다.
식 (1)과는 조금 다르게 2차 형식이 음수가 되지 않는 행렬은 양의 준정부호 행렬(陽의 準定符號行列, positive semidefinite matrix)이라 부른다.

                  (9)

양의 준정부호 행렬은 양의 정부호 행렬과 비슷하게 다음 성질을 가진다.

[양의 준정부호 행렬의 판정법] [1]
(a) 대칭 행렬 $\bf A$의 모든 고유치는 음수가 아니다[혹은 $0$이거나 양수이다].
(b) 모든 선행 주부분 행렬의 행렬식은 음수가 아니다.
(c) 행을 교환하지 않은 모든 추축은 음수가 아니다.

양의 정부호 행렬의 판정법과 거의 유사한 방식은 위 성질을 증명할 수 있다. 양의 준정부호 행렬은 2차 형식이 $0$이 될 수도 있다는 특성을 제외하고는 양의 정부호 행렬과 동일하다. 그렇다면 굳이 양의 준정부호 행렬을 따로 정의할 필요가 있을까? 이 의문에 대한 해답은 2차 형식에서 찾을 수 있다. 양의 정부호 행렬은 2차 형식이 항상 $0$보다 크기 때문에, 2차 형식이 $0$인 경우는 $\bf x$ = $\bf 0$일 때 뿐이다. 하지만 양의 준정부호 행렬은 $\bf x$ $\ne$ $\bf 0$이더라도 행렬 $\bf A$의 특성에 의해 2차 형식이 $0$이 될 수도 있다.
양의 정부호 행렬이 유용한 이유는 연립 방정식의 해법에서도 찾을 수 있다. 벡터가 아닌 스칼라 $x$를 사용해서 다음 다항식 함수 $p(x)$를 정의한다.

                  (10)

여기서 함수 $p(x)$의 극점은 $Ax$ = $b$가 된다. 만약 $A > 0$이라면, $p(x)$는 극점 $x$ = $b/A$에서 최소값을 가진다. 식 (10)의 논의를 스칼라서 벡터로 확장하면 식 (1)에 나온 2차 형식을 만나게 된다[1].

                  (11)

제$i$번째 성분 $x_i$에 대한 편미분(partial differentiation)을 이용해서 함수 $p({\bf x})$의 극점을 구하면 다음과 같다.

                  (12)

여기서 $\bf x$ = $[x_1~\cdots~x_i~\cdots~x_n]$, $b_i$는 열 벡터 $\bf b$의 성분, $a_{ik}$는 행렬 $\bf A$ 원소이며 $a_{ik}$ = $a_{ki}$를 만족한다. 모든 성분 $x_i$에 대해 식 (12)를 만족한다면, 극점이 생기는 위치 $\bf x$는 다음 연립 방정식에 의해 결정된다.

                  (13)

또한 2차 형식이 최소값을 가지는 조건인 양의 정부호 행렬을 만족하는 $\bf A$는 식 (13)의 위치 $\bf x$에서 $p({\bf x})$에 최소값을 만든다. 왜냐하면 임의의 열 벡터 $\bf y$에 대해 다음 2차 형식이 성립하기 때문이다.

                  (14)

여기서 극점 조건에 의해 ${\bf Ax}$ = ${\bf b}$이다. 식 (14)는 2차 형식이며 $\bf A$는 양의 정부호 행렬이므로, $\bf y$ = $\bf x$에서만 최소값을 가진다. 즉, 식 (11)의 최소값을 추적하면 연립 방정식 (13)의 해를 손쉽게 구할 수 있다. 조건을 더욱 약화해서 $\bf A$가 양의 준정부호 행렬이라 해본다. 그러면 식 (11)의 최소값이 생기는 위치는 항상 식 (13)일까? 양의 준정부호 행렬은 최소값과 극점의 관계가 성립하지 않는 경우가 생긴다. 왜냐하면 $\bf x$가 $0$이 아닌데도 ${\bf x}^T{\bf Ax}$가 $0$이 나올 수 있기 때문이다. 따라서 $p({\bf x})$의 최소값 위치가 확실하게 연립 방정식의 해가 되려면, $\bf A$는 반드시 양의 정부호 행렬이어야 한다.

양의 정부호 행렬의 정의인 식 (1)을 시작으로 다양한 양의 정부호 행렬의 성질을 증명할 수 있다.

[양의 정부호 행렬의 연산]
(a) 대칭 행렬 ${\bf A}, {\bf B}$가 양의 정부호 행렬이면, ${\bf A} + {\bf B}$도 양의 정부호 행렬이 된다.
(b) 대칭이며 양의 정부호인 행렬 ${\bf A}, {\bf B}$가 교환 법칙 ${\bf AB} = {\bf BA}$를 만족하면, $\bf AB$도 양의 정부호 행렬이다.
(c) 대칭 행렬 ${\bf A}$가 양의 정부호 행렬이면, ${\bf A}^{-1}$도 양의 정부호 특성을 가진다.

[명제 (a)의 증명]
행렬의 합 ${\bf A} + {\bf B}$에 대해 식 (1)과 같은 2차 형식을 적용한다.

                  (15)

즉, ${\bf A}, {\bf B}$가 양의 정부호를 만족하므로, ${\bf A} + {\bf B}$도 자동적으로 양의 정부호가 된다.

[명제 (b)의 증명]
행렬 $\bf A$를 제곱근으로 바꾸어서 행렬의 곱을 다시 쓴다.

                  (16)

여기서 교환 법칙이 성립하기 때문에 대칭 행렬 ${\bf A}^{1/2}$과 $\bf B$가 서로 교환될 수 있다. 식 (16)의 결과를 하나의 행렬로 보고 식 (1)과 같은 2차 형식을 만든다.

                  (17)

여기서 $\bf B$는 양의 정부호 행렬이라서 임의의 $\bf x$에 대해 2차 형식이 항상 $0$보다 크다.

[명제 (c)의 증명]
역행렬의 고유치는 $\bf A$에 대한 고유치의 역수[= $1/\lambda_i$]이기 때문에, 역행렬의 고유치는 항상 양수이다. 따라서 역행렬도 양의 정부호 행렬이 된다.
______________________________

명제 (a)를 더 확장해서 스칼라 곱으로 만든 $k_1 {\bf A} + k_2 {\bf B}$도 양의 정부호 행렬이 된다. 여기서 $k_1, k_2$는 양수인 스칼라이다.

[참고문헌]
[1] G. Strang, Linear Algebra and its Applications, 4th ed., Brooks/Cole, 2006.

[다음 읽을거리]

댓글 5개 :

  1. 안녕하세요~ 항상 감사드립니다
    (5)에서 3번째 행렬 2,2에서 a22가 a12로 오타가 난 거 같아요
    그리고 질문이 두 개 있습니다.
    하나는 명제 (b)에서 마지막 n-k개 의 성분을 항상 0이라 생각하고 푸는 건 열벡터 x에 관계가 없어서 가능한건가요?
    다른 하나는 선행 주부분 행렬과 반대로 우측 하단에 처음 n-k개는 0으로 두고 k개는 xi로 해도 항상 0보다 큰 게 맞나요?

    답글삭제
    답글
    1. 오타 지적 정말 감사합니다, Unknown님 👍

      1. 맞습니다. 열 벡터 $\bf x$는 임의로 선택할 수 있어요.

      2. 맞습니다. 이번에 추가한 식 (8)을 보세요.

      삭제
  2. 답변 정말 감사합니다! ^^

    답글삭제
  3. 안녕하세요 선형대수학 공부할때 좋은 참고를 하고 있습니다. 감사합니다.
    다름 아니라 positive-definite matrix 와 positive-semi-definite matrix 차이에 대해 0 포함유무에 대한 개념을 부탁드려도 될까요?

    답글삭제
    답글
    1. 식 (9) 밑에 내용을 간단히 추가했어요.

      삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.