[MIT 18.065] 1.5. Orthogonal Matrices and Subspaces

Date: 2024.03.19 Updated: 2024.03.20

카테고리: MIT 18.065

💡 이 글은 MIT의 선형대수학 강의 MIT 18.065 Spring 2018 및 Gilbert Strang 교수님의 책 『Linear Algebra and Learning from Data』을 따라 정리했습니다. 강의 내용과 일부 연습문제 풀이를 포함합니다.

1. Introduction

1.2절에서, 1장 전체를 통해 5가지 중요한 분해(factorization)를 다룬다고 하였다.

$A=LU$: Elimination
$A=QR$: Orthogonalization (Gram-Schmidt)
$S = Q \Lambda Q^T$: Eigenvalue, Eigenvector (Spectral Theorem)
$A=X \Lambda X^{-1}$: Diagonalization
$A=U \Sigma V^T$: Singular Value Decomposition (SVD)

여기서는 2번째 분해인 $A=QR$에 대해 다룬다.

2. Orthogonal Matrices and Subspaces

“Orthogonal” 혹은 “perpendicular”는 선형대수학 전반에 걸쳐 사용되는 용어이다. 이를 정리해보자.

2.1. Orthogonal vectors

두 벡터 $x$와 $y$가 orthogonal이라는 것은, 두 벡터의 내적이 0이라는 것을 의미한다.

\[x^T y = x_1 y_1 + x_2 y_2 + \cdots + x_n y_n = 0\]

$x$, $y$가 복소수이면 다음과 같이 나타낼 수 있다. 여기서 $x^H$는 $x$의 에르미트 전치(Hermitian transpose)이다.

\[x^H y = \bar{x}^ T y = \bar{x}_1 y_1 + \bar{x}_2 y_2 + \cdots + \bar{x}_n y_n = 0\]

2.2. Orthogonal basis

벡터들의 집합이 orthogonal basis라는 것은, 그 벡터들이 서로 orthogonal하다는 것이다. 즉 임의의 basis vectors $v_i, v_j$에 대하여 $v_i ^T v_j = 0$이다. 그리고 orthonormal basis는, orthogonal basis에서 각 벡터들의 길이가 1인 경우, 즉 $v_i ^T v_i = 1$인 경우이다. Orthogonal basis로부터 orthonormal basis를 만들기 위해서는 각 벡터 $v_i$를 그 길이 $\Vert v_i \Vert$로 나누어주면 된다.

만약 basis가 서로 orthogonal하지 않으면, Gram-Schmidt process를 통해 orthogonal basis로 변환할 수 있다. 예를 들어 basis vectors $a, b$가 주어졌을 때, 다음과 같이 orthogonal basis vectors $a, c$로 만들어줄 수 있다.

\[c = b - \frac{a^T b}{a^T a} a \quad \rightarrow \quad a^T c = 0\]

2.3. Orthogonal subspaces

두 subspace $\mathbf{R}$과 $\mathbf{N}$가 orthogonal하다는 것은, $\mathbf{R}$에 속하는 모든 벡터들이 $\mathbf{N}$에 속하는 모든 벡터들과 orthogonal하다는 것이다. 예를 들어, row space $\mathbf{C}(A^T)$와 nullspace $\mathbf{N}(A)$는 서로 orthogonal하다.

같은 방식으로 다음과 같이 정리할 수 있다.

여기서 증명할 것은 아니지만 SVD(Singular Value Decomposition)를 통해 row space의 orthonormal basis $v_1, v_2, \cdots, v_r$와 column space의 orthonormal basis $u_1, u_2, \cdots, u_r$를 구할 수 있다. 그리고 둘 사이에는 다음과 같은 관계가 있다.

\[Av_1 = \sigma_1 u_1, \quad Av_2 = \sigma_2 u_2, \quad \cdots, \quad Av_r = \sigma_r u_r\]

즉, orthogonal basis $v$에 $A$를 곱하면 orthogonal basis $u$를 얻게 된다.

2.4. Tall thin matrices

Orthogonal matrices에 대해 이야기하기 전에, orthonormal columns로 구성된 tall thin matrix, 즉 $m \times n (m \leq n)$ 행렬 $Q$에 대해 알아보자. 이 행렬은 $Q^T Q = I$를 만족한다. 참고로, $m \gt n$이면 $n$차원의 orthonormal columns $m$개가 존재할 수 없으므로 성질을 만족하지 않는다. 즉, $m \times n (m \leq n)$ 행렬 $Q$는 $Q^T Q = I$를 만족하지만, $Q Q^T \neq I$이다.

이러한 $Q$의 성질은, 임의의 벡터 $x$에 $Q$를 곱해도 벡터의 길이가 달라지지 않는다는 것이다. 즉 $\Vert Qx \Vert = \Vert x \Vert$이다. 이는 $Q$가 길이를 보존한다는 것을 의미한다.

\[\Vert Qx \Vert = \sqrt{(Qx)^T Qx} = \sqrt{x^T Q^T Qx} = \sqrt{x^T x} = \Vert x \Vert\]

한편 matrix $P = Q Q^T$는 projection matrix이다. 즉, $P^2 = (Q Q^T)(Q Q^T) = Q Q^T = P = P^T$이다. 실제로는 다음과 같은 명제가 성립한다.

$P^2 = P = P^T$이면, $Pb$는 벡터 $b$의 $P$의 column space에의 orthogonal projection이다.

이러한 projection matrix는 least squares 문제를 풀 때 사용된다. 이에 대해서는 나중에 다룰 것이다. 여기서는 간단한 예시를 들어보자. 다음과 같은 tall thin matrix $Q_1, Q_2, Q_3$를 생각해보자.

각각 $P_1 = Q_1 Q_1^T$, $P_2 = Q_2 Q_2^T$, $P_3 = Q_3 Q_3^T$라고 하고, 벡터 $b=(3,3,3)$에 대해 projection을 시각화하면 다음과 같다. 이때 $e = (I - P_i)b$이다.

한편 $P_3 = Q_3 Q_3^T = I$이다. 즉, 전체 3차원 공간 $\mathbb{R} ^ 3$에 orthogonal projection을 한다는 것은 곧 자기 자신에 대한 projection이라는 것이다. 따라서 $P_3b = b$이고, $e = (I - P_3)b = 0$이다.

2.5. Orthogonal matrices

Orthogonal matrices는 orthonormal columns로 구성된 $n \times n$ 행렬 $Q$이며, $Q^T Q = Q Q^T = I$를 만족한다. 즉, $Q^T = Q^{-1}$이다. 이러한 행렬은 길이를 보존하고, orthogonal하다. 스트랭 교수님은 orthogonal matrices가 아니라 orthonormal matrices가 더 맞는 표현이라고 하시는데, 나 또한 동의한다. 그리고 orthogonal matrices의 곱도 orthogonal matrix이다. 즉, $Q_1 Q_2$도 orthogonal matrix이다.

\[(Q_1 Q_2)^T (Q_1 Q_2) = Q_2^T Q_1^T Q_1 Q_2 = Q_2^T Q_2 = I\]

$2 \times 2$ orthogonal matrix $Q$는 rotation 또는 reflection matrix이다. 둘의 구분은 determinant로 할 수 있다. $\det Q_{\text{rotate}} = 1$이지만, $\det Q_{\text{reflect}} = -1$이다.

아래 그림은 각각 rotation, reflection을 직관적으로 나타낸 그림이다.

책에서는 reflection matrix의 예시로 Householder matrix를 들었다. 이는 unit vector $u$ (즉, $u^T u = 1$)에 대해 다음과 같이 나타낼 수 있다. 모든 $u$에 대해 만들 수 있지만, 여기서는 $u = (1, 1, \cdots, 1) / \sqrt{n}$로 하였다.

\[H_n = I - 2uu^T = I - \frac {2}{n} \text{ones} (n, n)\]

당연히 $H_n$은 symmetric하고, 2번의 reflection $H^2 = I$인 것을 다음 식으로부터 알 수 있다.

\[H^T H = H^2 = (I - 2uu^T) (I - 2uu^T) = I - 4uu^T + 4uu^Tuu^T = I\]

예를 들어 $H_3$은 다음과 같다.

$H_n u = (I-2uu^T)u = u - 2u = -u$이다. 그런데 $H_n$은 reflection matrix이므로, $w \perp u$에 대해 $H_n w = w$이다. 따라서, $H_n$의 eigenvalue는 1번의 -1 ($u$)과 $n-1$번의 1 ($w$)이다. 이와 같은 방식으로 다음 명제가 성립한다.

모든 reflection matrices의 eigenvalue는 1과 -1이다.

그 외의 orthogonal matrices의 예시로는 permutation matrix를 들 수 있다. 여기서도 $P^T P = I$, $P^{-1} = P$이다. 예를 들어 $3 \times 3$ permutation matrix $P$는 다음과 같다.

\[P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

2.6. Orthogonal Basis = Orthogonal Axes

Orthonormal basis에 대해서는 orthogonal matrix를 이용해 coefficient를 한 번에 구할 수 있다. 즉, $n \times n$ orthogonal matrix $Q$의 columns를 $q_1, q_2, \cdots, q_n$이라고 하면, 임의의 벡터 $v \in \mathbb{R}^ n$에 대해 다음과 같이 나타낼 수 있을 것이다.

\[v = c_1 q_1 + c_2 q_2 + \cdots + c_n q_n\]

이때 각각의 coefficient는 다음과 같이 나타낼 수 있다. $q_i ^T q_j = 0$이기 때문이다.

\[c_1 = q_1^T v, \quad c_2 = q_2^T v, \quad \cdots, \quad c_n = q_n^T v\]

$c^ \ast = (c_1, c_2, \cdots, c_n)$라고 하면, $v = Qc$로 나타낼 수 있고, $Q^T$를 곱하면 다음과 같이 된다.

\[Q^T v = Q^T Q c = c\]

즉, $Q^T v$를 구하면 모든 coefficient $c_k = q_k^T v$를 한 번에 구할 수 있다. 즉, basis vector가 서로 orthonormal하면, 모든 coefficient를 한 번에, 분리하여 구할 수 있다.

3. Gram-Schmidt Process

이제 Gram-Schmidt process에 대해 알아보자. 이는 orthonormal basis를 만들기 위한 방법이다. 방법은 간단하다. 행렬 $A$에 independent columns $a_1, a_2, \cdots, a_n$이 주어졌을 때, 다음과 같이 orthogonal basis $q_1, q_2, \cdots, q_n$를 만들 수 있다.

$q_1 = a_1 / \Vert a_1 \Vert$
$A_2 = a_2 - (a_2^T q_1)q_1$, $q_2 = A_2 / \Vert A_2 \Vert$
$A_3 = a_3 - (a_3^T q_1)q_1 - (a_3^T q_2)q_2$, $q_3 = A_3 / \Vert A_3 \Vert$

따라서 $q_k$는 $a_1$부터 $a_k$까지의 linear combination으로 나타낼 수 있고, 반대로 $a_k$는 $q_1$부터 $q_k$까지의 linear combination으로 나타낼 수 있다. 즉 다음과 같다.

\[\begin{aligned} a_1 &= \Vert a_1 \Vert q_1 \\ a_2 &= (a_2^T q_1)q_1 + \Vert A_2 \Vert q_2 \\ a_3 &= (a_3^T q_1)q_1 + (a_3^T q_2)q_2 + \Vert A_3 \Vert q_3 \end{aligned}\]

여기서 $r_{ij} = q_i^T a_j$라고 하면, 다음과 같이 나타낼 수 있다. 여기서 당연히 $r_{ii} = \Vert A_i \Vert$이다.

\[\begin{aligned} a_1 &= r_{11} q_1 \\ a_2 &= r_{12} q_1 + r_{22} q_2 \\ a_3 &= r_{13} q_1 + r_{23} q_2 + r_{33} q_3 \end{aligned}\]

따라서 다음과 같이 upper triangular matrix $R$로 나타낼 수 있고, 이것이 $A=QR$ 분해이다.

\[\begin{bmatrix} & & \\ a_1 & a_2 & a_3 \\ & & \end{bmatrix} = \begin{bmatrix} & & \\ q_1 & q_2 & q_3 \\ & & \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & r_{13} \\ 0 & r_{22} & r_{23} \\ 0 & 0 & r_{33} \end{bmatrix}\]

4. Selected Solutions to Problems

Problem 3.

Q. Orthogonal matrix $Q$에 대하여, $(Qx)^T (Qy) = x^T y$임을 증명하라.

이 문제에서 중요한 것은, $Q$에 의해서는 벡터의 길이도 변하지 않고, 벡터 사이의 각도도 변하지 않는다는 것이다.

\[(Qx)^T (Qy) = x^T Q^T Qy = x^T y\]

이때 벡터 사이의 각도 $\cos \theta$는 다음과 같이 나타낼 수 있고, 따라서 각도는 $Q$를 곱한 뒤에도 보존된다.

\[\cos \theta = \frac{x^T y}{\Vert x \Vert \Vert y \Vert}\]

Problem 6.

Q. Symmetric matrix 또는 orthogonal matrix의 eigenvector가 모두 orthogonal하다는 것을 증명하라.

먼저 symmetric matrix $S$의 정의는 $S^T = S$이다. 그리고 서로 다른 eigenvalue를 가지는 다음 두 식이 있다고 가정하자.

\[Sx_1 = \lambda_1 x_1, \quad Sx_2 = \lambda_2 x_2 \quad (\lambda_1 \neq \lambda_2)\]

이때 $\lambda_1 x_1 ^T x_2$를 생각하면, 다음과 같이 나타낼 수 있다.

\[\lambda_1 x_1 ^T x_2 = (Sx_1) ^T x_2 = x_1 ^T S^T x_2 = x_1 ^T Sx_2 = \lambda_2 x_1 ^T x_2 \\\]

따라서 다음과 같고, $\lambda_1 \neq \lambda_2$이므로 $x_1 ^T x_2 = 0$이다.

\[\therefore \quad (\lambda_1 - \lambda_2) x_1 ^T x_2 = 0, \quad x_1 ^T x_2 = 0\]

다음으로 orthogonal matrix $Q$의 특징은 $Q^T = Q^{-1}$이다. 역시 다음과 같이 가정하자.

\[Qx_1 = \lambda_1 x_1, \quad Qx_2 = \lambda_2 x_2 \quad (\lambda_1 \neq \lambda_2)\]

이때 $\lambda_1 x_1 ^T x_2$를 생각하면, 다음과 같이 나타낼 수 있다.

\[\lambda_1 x_1 ^T x_2 = (Qx_1) ^T x_2 = x_1 ^T Q^T x_2 = x_1 ^T Q^{-1} x_2 = \frac{1}{\lambda_2} x_1 ^T x_2 \\\]

한편, $\Vert Qx_1 \Vert = \Vert x_1 \Vert$, $\Vert Qx_2 \Vert = \Vert x_2 \Vert$이므로, $\lambda_1 = \pm 1$, $\lambda_2 = \pm 1$이다. 위 식으로부터 $\lambda_1 \lambda_2 = 1$이거나 $x_1 ^T x_2 = 0$인데, $\lambda_1 = \pm 1$, $\lambda_2 = \pm 1$과 $\lambda_1 \lambda_2 = 1$를 동시에 만족하는 서로 다른 $\lambda_1, \lambda_2$는 없으므로 $x_1 ^T x_2 = 0$이다.

따라서 다음과 같이 정리할 수 있다.

Symmetric matrix 또는 orthogonal matrix의 eigenvector는 모두 orthogonal하게 결정할 수 있다.

I'm rubatoyeong