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

$ $

$ $

증명. 우선 $Q$가 대칭행렬_{(symmetric matrix)}이므로 $Q$는 대각화 가능_{(diagonalizable)}하다. 이제, 고윳값 분해 정리_{(eigenvalue decomposition theorem)}에 의하여 $Q = U\Lambda U^{\top}$으로 대각화되었다고 하자. (여기서, $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$가 어떤 값을 가져야 하는지는 정확하게 정의하지 않았다.) 그러면 다음을 얻는다.

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

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

$ $

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

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

여기서 $\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)}이다.) 그러므로,

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

$ $