재미있는 증명 하나

이번에 증명하고자 하는 정리는, 정리의 내용 자체만으로도 흥미로울 뿐만 아니라, 정리를 증명하는 방법 또한 매우 신기해서 이곳에 그 내용을 정리해서 올려보고자 한다. 이 정리는 Quadratic Semidefinite Programming 분야에서 S-lemma라고 불리는 정리를 증명할 때에 보조정리로써 사용되는데, 그 내용은 다음과 같다.

Theorem.

두 행렬 $P$와 $Q$가 모두 $n \times n$ symmetric matrix라 하자. 만약 $\operatorname{tr}(P) \geq 0$ 이고 $\operatorname{tr}(Q) < 0$이면, $\bar{x}^{\top}P\bar{x} \geq 0$과 $\bar{x}^{\top}Q\bar{x} < 0$을 동시에 만족하는 $\bar{x} \in \mathbb{R}^n$이 존재한다.

Proof: 우선 $Q$가 symmetric matrix이므로 $Q$는 diagonalizable하다. 이제, eigenvalue decomposition theorem에 의하여 $Q = U\Lambda U^{\top}$으로 diagonalize되었다고 하자. (당연히, $U$는 orthogonal matrix, $\Lambda$는 $Q$의 eigenvalue들로 이루어진 diagonal matrix이다.) 이제 $x := Uz$로 정의하는데, 이때 $z = (z_1,\, z_2,\, \ldots,\, z_n) \in \mathbb{R}^n$의 모든항 $z_i$는 $1$ 또는 $-1$의 값을 가진다고 하자. (아직 $z_i$가 어떤 값을 가져야 하는지는 정확하게 정의하지 않았다.) 그러면 다음을 얻는다.

\[ x^{\top}Qx = x^{\top}U\Lambda U^{\top}x = (U^{\top}x)^{\top}\Lambda (U^{\top}x) = z^{\top}\Lambda z = \operatorname{tr}(\Lambda) = \operatorname{tr}(Q) < 0. \]

이제 문제는 수많은 $z$의 후보들 중에서 매우 현명하게 $z$를 택하여, 다음의 부등식

\[ x^{\top}Px = (Uz)^{\top}P (Uz) = z^{\top}U^{\top}PUz \geq 0 \]

을 만족하도록 해야 한다. 여기서 문제는 위 식에서, $U^{\top}PU$이 반드시 diagonal matrix는 아닐 수도 있다는 점에 있다. ($P$ 또한 symmetrix matrix이므로, $P = V \Gamma V^{\top}$로 diagonalize될 수 있지만, 이때 $V$가 반드시 $U$와 같을 이유는 없다.)

이제 여기서 매우 특별한 방법이 이용되는데, 바로 $z$를 모든 항 $z_i$의 값이 $1/2$의 확률로 $1$ 또는 $-1$을 가지는 random vector으로 간주하는 것이다. 그렇게 하면 $z$의 각각의 항 $z_i$의 값의 expectation은 $\mathbb{E}(z_i) =0$이 된다. 하지만, $z_iz_j$의 expectation을 살펴보면,

\[ \mathbb{E}(z_iz_j) = \left\{ \begin{aligned} 1, \qquad & \text{if} \quad i = j, \\ 0, \qquad & \text{otherwise}. \end{aligned} \right. \]

임을 알 수 있다. 따라서 $\mathbb{E}(z_iz_j) = \delta{ij}$로 생각할 수 있다. 이제 $\mathbb{E}(x^{\top}Px)$의 값을 생각해 보자. 우선,

\[ \begin{aligned} \mathbb{E}(x^{\top}Px) & =\mathbb{E}(z^{\top}U^{\top}PUz) \\ & = \mathbb{E}\left( \sum_{i=1}^{n} z_iz^{\top} (\mbox{the $i$th row of $U^{\top}PU$}) \right) \\ & = \sum_{i=1}^{n} \mathbb{E}(z_iz^{\top}) (\mbox{the $i$th row of $U^{\top}PU$}). \end{aligned} \]

여기서 $\mathbb{E}(z_iz_j) = \delta{ij}$이므로, $\mathbb{E}(z_iz^{\top}) = e_i^{\top}$가 됨을 알 수 있다. (이 때, $\{e_1,\, e_2,\, \ldots,\, e_n\}$은 $\mathbb{R}^n$의 standard basis이다.) 그러므로,

\[ \begin{aligned} \mathbb{E}(x^{\top}Px) & = \sum_{i=1}^{n} e_i^{\top} (\mbox{the $i$th row of $U^{\top}PU$})\\ & = \sum_{i=1}^{n} (\mbox{the $i$th diagonal of $U^{\top}PU$}) \\ & = \operatorname{tr}(U^{\top}PU) \\ & = \operatorname{tr}(P) \\ & \geq 0. \end{aligned} \]

따라서 $\mathbb{E}(x^{\top}Px) \geq 0$을 얻게 되고, 적어도 하나의 $\bar{z}$가 존재하여 $\bar{x} = U\bar{z}$로 정의하면, $\bar{x}^{\top}P\bar{x} \geq 0$이 된다. 따라서 증명이 완료된다. ■