younghwanjoo1608

ㅎㅇ

5 minute read

"정의의 행렬, 악의 행렬"


second order optimality condition를 배우려면 먼저 알아야 할 게 있다.


Definition 1.2.1

Symmetric matrix $\textbf{A} \in \mathbb{R}^{n \times n}$에 대해,

(a) 임의의 $\textbf{x} \in \mathbb{R}^n$에 대해 $\textbf{x}^T\textbf{A}\textbf{x} \geq 0$이면, $\textbf{A}$가 positive semidefinite라고 하고, $\textbf{A} \succeq 0$으로 표현한다.

(b) 임의의 $0 \not= \textbf{x} \in \mathbb{R}^n$에 대해 $\textbf{x}^T\textbf{A}\textbf{x} > 0$이면, $\textbf{A}$가 positive definite라고 하고, $\textbf{A} \succ 0$으로 표현한다.


Positive definiteness는 성분들이 positive라는 뜻이 아니다!


Example 1.2.2

\[\textbf{A} = \begin{pmatrix}2 & -1 \\ -1 & 1\end{pmatrix}\]

이면, 임의의 $\textbf{x}=(x_1, x_2)^T \in \mathbb{R}^2$에 대해,

\[\textbf{x}^T\textbf{A}\textbf{x} = \begin{pmatrix}x_1 & x_2\end{pmatrix} \begin{pmatrix}2 & -1 \\ -1 & 1\end{pmatrix} \begin{pmatrix}x_1 \\ x_2\end{pmatrix} = 2x_1^2-2x_1x_2+x_2^2 = x_1^2 + (x_1-x_2)^2 \geq 0\]

그러므로 $\textbf{A}$는 positive semidefinite이다.

게다가, $x_1^2 + (x_1-x_2)^2 = 0$과 $x_1 = x_2 = 0$은 동치이므로, 이 조건 하에서 $\textbf{A}$는 positive definite이다. 물론 $\textbf{A}$의 성분이 모두 positive이지는 않다.


반대로,

\[\textbf{A} = \begin{pmatrix}1 & 2 \\ 2 & 1\end{pmatrix}\]

이라고 하자. 이 matrix는 모든 성분이 positive이지만 $\textbf{x}=(1, -1)^T$에 대해,

\[\textbf{x}^T\textbf{A}\textbf{x} = \begin{pmatrix}1 & -1\end{pmatrix} \begin{pmatrix}2 & -1 \\ -1 & 1\end{pmatrix} \begin{pmatrix}1 \\ -1\end{pmatrix} = -2\]

이므로 $\textbf{A}$는 positive semidefinite가 아니다.


Lemma 1.2.3

(a) $\textbf{A} \in \mathbb{R}^{n \times n}$가 positive definite matrix라고 하자. 그러면 $\textbf{A}$의 모든 대각 성분들은 positive이다.

(b) $\textbf{A} \in \mathbb{R}^{n \times n}$가 positive semidefinite matrix라고 하자. 그러면 $\textbf{A}$의 모든 대각 성분들은 nonnegative이다.


Proof.


[(a)]

$\textbf{A}$가 positive definite이므로, $\textbf{e}_ i^T \textbf{A}\textbf{e}_ i >0 \quad (i \in \{1, 2, \cdots, n\})$이 성립한다. 이 값은 $A_{ii}$와 같다. (b)도 같은 방법으로 증명. $\square$


다음은 반대쪽이다.


Definition 1.2.4

Symmetric matrix $\textbf{A} \in \mathbb{R}^{n \times n}$에 대해,

(a) 임의의 $\textbf{x} \in \mathbb{R}^n$에 대해 $\textbf{x}^T\textbf{A}\textbf{x} \leq 0$이면, $\textbf{A}$가 negative semidefinite라고 하고, $\textbf{A} \preceq 0$으로 표현한다.

(b) 임의의 $0 \not= \textbf{x} \in \mathbb{R}^n$에 대해 $\textbf{x}^T\textbf{A}\textbf{x} < 0$이면, $\textbf{A}$가 negative definite라고 하고, $\textbf{A} \prec 0$으로 표현한다.

(c) $\textbf{x}^T\textbf{A}\textbf{x} > 0$이고 $\textbf{y}^T\textbf{A}\textbf{y} < 0$인 $\textbf{x}, \textbf{y} \in \mathbb{R}^n$가 존재하면, $\textbf{A}$를 indefinite라고 한다.


정의 상 당연히 $\textbf{A}$가 positive (semi)definite인 것과 $-\textbf{A}$가 negative (semi)definite인 것은 동치이다. 물론 다음 Lemma도 당연하다.


Lemma 1.2.5

(a) $\textbf{A} \in \mathbb{R}^{n \times n}$가 negative definite matrix라고 하자. 그러면 $\textbf{A}$의 모든 대각 성분들은 negative이다.

(b) $\textbf{A} \in \mathbb{R}^{n \times n}$가 negative semidefinite matrix라고 하자. 그러면 $\textbf{A}$의 모든 대각 성분들은 nonpositive이다.


만약 대각 성분에 positive, negative value가 모두 있다면 그 행렬은 indefinite.1


그러나 위와 같은 방식으로 matrix가 positive (semi)definite인지 negative (semi)definite인지를 판정하기는 쉽지 않다. 좀 더 쉬운 방법이 있을 것이다.

Matrix의 성질을 알 수 있는 중요한 요소, 바로 eigenvalue!


Theorem 1.2.7 [Spectral Decomposition Theorem]

$\textbf{A} \in \mathbb{R}^{n \times n}$가 symmetric matrix라고 하자.

그러면 orthogonal matrix $\textbf{U} \in \mathbb{R}^{n \times n}$가 존재하고, diagonal matrix $\textbf{D} = \textrm{diag}(d_1, d_2, \cdots, d_n)$가 존재해서,

\[\textbf{U}^T\textbf{A}\textbf{U}=\textbf{D}\]

가 성립한다. 이때 $\textbf{U}$의 column은 $\textbf{A}$의 eigenvector로 이루어진 orthonormal basis를 구성하며, $\textbf{D}$는 대각 성분으로 이 eigenvector들에 대응되는 $\textbf{A}$의 eigenvalue들을 갖는다.


Proof.


생략. 선형대수 책을 폅시다.

Theorem 1.2.8 [Eigenvalue Characterization Theorem]

$\textbf{A} \in \mathbb{R}^{n \times n}$가 symmetric matrix라고 하자.

(a) $\textbf{A}$가 positive definite $\Leftrightarrow$ $\textbf{A}$의 모든 eigenvalue가 positive.

(b) $\textbf{A}$가 positive semidefinite $\Leftrightarrow$ $\textbf{A}$의 모든 eigenvalue가 nonnegative.

(c) $\textbf{A}$가 negative definite $\Leftrightarrow$ $\textbf{A}$의 모든 eigenvalue가 negative.

(d) $\textbf{A}$가 negative semidefinite $\Leftrightarrow$ $\textbf{A}$의 모든 eigenvalue가 nonpositive.

(e) $\textbf{A}$가 indefinite $\Leftrightarrow$ $\textbf{A}$의 적어도 한 eigenvalue가 positive이며 적어도 한 eigenvalue가 negative.


Proof.


[(a)]

$\textbf{A}$가 symmetric이므로, Thm. 1.2.7(Spectral Decomposition Theorem)에 의해 어떤 orthogonal matrix $\textbf{U} \in \mathbb{R}^{n \times n}$와 diagonal matrix $\textbf{D} = \textrm{diag}(d_1, d_2, \cdots, d_n)$가 존재하여 $\textbf{U}^T\textbf{A}\textbf{U}=\textbf{D}$가 성립한다. 이때 $\textbf{D}$의 대각 성분은 $\textbf{A}$의 eigenvalue들로 이루어진다.


이제 linear transformation $\textbf{x}=\textbf{U}\textbf{y}$를 생각하면 다음을 얻는다.

\[\textbf{x}^T\textbf{A}\textbf{x} =\textbf{y}^T \textbf{U}^T \textbf{A} \textbf{U} \textbf{y} = \textbf{y}^T\textbf{D}\textbf{y} = \sum_{i=1}^n d_i y_i^2\]

이제 $\textbf{U}$의 nonsingularity 조건으로부터, 임의의 $\textbf{x}=0$에 대해 $\textbf{x}^T\textbf{A}\textbf{x} >0$이라는 조건과 다음은 동치이다.

\[\textbf{y}^T\textbf{D}\textbf{y} = \sum_{i=1}^n d_i y_i^2 \qquad \textrm{for any }\textbf{y} \not= 0\]

따라서 위 조건은 모든 $i$에 대해 $d_i>0$과 동치이다. 헷갈리면 $\textbf{y} = \textbf{e}_i$로 두고 생각해보자. 나머지도 비슷하게 증명된다. $\square$


Corollary 1.2.9

$\textbf{A}$가 positive semidefinite(definite) matrix이면 $\textrm{tr}(\textbf{A})$는 nonnegative(positive).


다음은 너무 당연한 내용.


Lemma 1.2.10

$\textbf{D} = \textrm{diag}(d_1, d_2, \cdots, d_n)$에 대해,

(a) $\textbf{D}$가 positive definite $\Leftrightarrow$ 모든 $i$에 대해 $d_i > 0$.

(b) $\textbf{D}$가 positive semidefinite $\Leftrightarrow$ 모든 $i$에 대해 $d_i \geq 0$.

(c) $\textbf{D}$가 negative definite $\Leftrightarrow$ 모든 $i$에 대해 $d_i< 0$.

(d) $\textbf{D}$가 negative semidefinite $\Leftrightarrow$ 모든 $i$에 대해 $d_i \leq 0$.

(e) $\textbf{D}$가 indefinite $\Leftrightarrow$ 어떤 $i, j$가 존재해서 $d_i>0$이고 $d_j < 0$.


즉 eigenvalue로부터 우리는 matrix의 부호에 대한 정보를 알 수 있다. 여기서 더 나아가자.

$2 \times 2$ case부터 시작하자.


Proposition 1.2.11

$\textbf{A}$가 $2 \times 2$ symmetric matrix라고 하자.

$\textbf{A}$가 positive semidefinite(definite) $\Leftrightarrow$ $\textrm{tr}(\textbf{A}), \det(\textbf{A}) \geq 0$($>0$)


Proof.


Positive semidifinite case만 증명하자. Thm. 1.2.8에 의해 $\textbf{A}$가 positive semidefinite인 것과 $\lambda_1(\textbf{A}) \geq 0, \lambda_2(\textbf{A}) \geq 0$인 것은 동치.

그러므로 $\textbf{A}$가 positive semidefinite인 것과 $\textrm{tr}(\textbf{A}) = \lambda_1(\textbf{A}) + \lambda_2(\textbf{A}) \geq 0$이고 $\det(\textbf{A}) = \lambda_1(\textbf{A}) \cdot \lambda_2(\textbf{A}) \geq 0$인 것은 동치. $\square$


이제 슬슬 positive definiteness를 판정할 방법을 소개한다. 바로 principal minors criterion이다. 주어진 $n \times n$ 행렬에 대해, 왼쪽 위에 존재하는 $k \times k$ submatrix의 $\det$를 $k$-th principal minor라고 부르며 $D_k(\textbf{A})$로 나타낸다.

예를 들어,

\[\textbf{A} = \begin{pmatrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33}\end{pmatrix}\]

이면,

\[D_1(\textbf{A}) = a_{11}, \quad D_2(\textbf{A}) = \det \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}, \quad D_3(\textbf{A}) = \det \begin{pmatrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33}\end{pmatrix}\]

이다.

Theorem 1.2.12

$\textbf{A}$가 $n \times n$ symmetric matrix라고 하자.

$\textbf{A}$가 positive definite $\Leftrightarrow$ $D_1(\textbf{A}) > 0, D_2(\textbf{A}) > 0, \cdots, D_n(\textbf{A}) > 0$


이번엔 더더욱 단순한 방법이다.


Definition 1.2.13

$\textbf{A}$가 $n \times n$ symmetric matrix라고 하자.

(a) 모든 $i=1,2, \cdots , n$에 대해

\[\vert A_{ii} \vert \geq \sum_{j \not= i} \vert A_{ij} \vert\]

이면, $\textbf{A}$가 diagonally dominant라고 한다.

(b) 모든 $i=1,2, \cdots , n$에 대해

\[\vert A_{ii} \vert > \sum_{j \not= i} \vert A_{ij} \vert\]

이면, $\textbf{A}$가 strictly diagonally dominant라고 한다.


Theorem 1.2.14

(a) $\textbf{A}$가 $n \times n$ symmetric matrix이고 diagonally dominant이며 모든 대각 성분이 nonnegative이면 $\textbf{A}$는 positive semidefinite.

(b) $\textbf{A}$가 $n \times n$ symmetric matrix이고 strictly diagonally dominant이며 모든 대각 성분이 positive이면 $\textbf{A}$는 positive definite.


Proof.


[(a)]

$\textbf{A}$의 negative eigenvalue $\lambda$가 존재한다고 가정하고 모순을 보이자. $\lambda$에 해당되는 eigenvector는 $\textbf{u}$라고 하자.

Index $i \in \{1, 2, \cdots, n\}$를 $\vert u_i \vert$가 $\vert u_1 \vert, \vert u_2 \vert, \cdots , \vert u_n \vert$ 중 가장 큰 값이 되도록 선택하자. 그러면 등식 $\textbf{A}\textbf{u} = \lambda \textbf{u}$로부터,

\[\vert A_{ii}-\lambda \vert \cdot \vert u_i \vert = \vert \sum_{j \not= i}A_{ij}u_j \vert \leq ( \sum_{j \not= i} \vert A_{ij} \vert )\vert u_i \vert \leq \vert A_{ii} \vert \vert u_i \vert\]

이고, 따라서 $\vert A_{ii}-\lambda \vert \leq \vert A_{ii} \vert$를 얻는다. $\lambda$가 음수이므로 이는 eigenvalue $A_{ii}$의 nonnegativity에 위배된다.

[(b)]

(a)의 증명과 비슷, 다만 $\textbf{A}$가 zero eigenvalue를 갖지 않는다는 것만 더 보이면 된다. Zero eigenvalue가 존재하면 어떤 $\textbf{u} \not= 0$가 존재해서 $\textbf{A}\textbf{u}=0$이고, $\vert A_{ii} \vert \cdot \vert u_i \vert$를 풀어 쓰면…. $\square$


  1. 앗, 역은 성립하지 않는다! ↩

You may also enjoy