공사 중인 페이지입니다! 가독성이 떨어질 수 있습니다.
이번 장에서는 벡터 공간에서의 크기, 혹은 거리에 준하는 개념을 정의하고 공부한다. 이러한 개념을 벡터 공간에 도입하기 위해서는 먼저 inner product space 체계가 필요하다.
6.1. Inner Products and Norms
(Def: Inner Product) Let $V$ be a vector space over $F$. An inner product on $V$ is a function that assigns, to every ordered pair of vectors $x$ and $y$ in $V$, a scalar in $F$, denoted $<x, y>$, such that for all $x, y$ and $z$ and all $c$ in $F$, the following hold.
•
$<x + z, y> = <x, y> + <z, y>$.
•
$<cx, y> = c<x, y>$.
•
$\overline{<x, y>} = <y, x>$, where the bar denotes complex conjugation.
•
$<x, x> > 0$ if $x ≠ 0$.
세 번째 조건을 보면, 실수에서는 $<x, y> = <y, x>$임을 알 수 있다. 또 첫 번째와 두 번째 조건을 보면 내적은 첫 번째 원소에 대해 선형이다.
이제 벡터 공간에서의 다음과 같은 특수한 경우의 내적을 기억해두자.
Standard Inner Product: $<x, y> = \sum{x_i \overline{y_i}}$
또 행렬의 adjoint를 다음과 같이 정의한다.
(Def: Adjoint) Let $A \in M_{m \times n}(F)$. We define the conjugate transpose or adjoint of $A$ to be the $n \times m$ matrix $A^$ such that $(A^{ij}) = \overline{A{ji}}$ for all $i, j$.
행렬에서의 다음과 같은 특수한 경우의 내적을 기억해두자.
Frobenius Inner Product: $<A, B> = tr(B^*A)$
또 앞으로 벡터 공간 $H$를 $[0, 2\pi]$에서 정의된 연속 복소수 함수의 벡터 공간 중 다음과 같은 내적을 가진 내적 공간으로 정의한다.
$$
<f, g> = \frac{1}{2\pi}\int_0^{2\pi}{ f(t) \overline{g(t)} dt }
$$
이제 내적의 정의에 의해 다음과 같은 정리를 쉽게 이끌어낼 수 있다.
(Thm 6.1) Let $V$ be an inner product space. Then for $x, y, z \in V$ and $c \in F$, the following statements are true.
•
$<x, y + z> = <x, y> + <x, z>$.
•
$<x, cy> = \overline{c}<x, y>$.
•
$<x, 0> = <0, x> = 0$.
•
$<x, x> = 0$ if and only if $x = 0$.
•
If $<x, y> = <x, z>$ for all $x \in V$, then $y = z$.
첫 번째와 두 번째와 같은 성질을 가진 연산을 conjugate linear하다고 한다. 내적은 두 번째 원소에 대해 conjugate linear하다.
이제 이러한 내적을 이용해 길이에 대응되는 개념을 도입한다. 사실상 유클리드 공간에서의 2차원(혹은 3차원)의 길이를 확장한 것에 가깝다.
(Def: Norm) Let $V$ be an inner product space. For $x \in V$, we define the norm or length of $x$ by $||x|| = \sqrt{<x, x>}$.
그러면 정의에 의해 다음의 유클리드 길이의 친숙한 정리가 성립한다. 증명은 trivial하다.
(Thm 6.2) Let $V$ be an inner product space over $F$. Then for all $x, y \in V$ and $c \in F$, the following statements are true.
•
$||cx|| = |c| ||x||$.
•
$||x|| = 0$ if and only if $x = 0$. In any case, $||x|| ≥ 0$.
•
(Cauchy-Schwarz Inequality) $|<x, y>| ≤ ||x|| ||y||$.
•
(Triangle Inequality) $||x + y|| ≤ ||x|| + ||y||$.
$<x, y> = ||x|| ||y|| \cos{\theta}$임을 기억할 것이다(?). 두 벡터가 직각을 이룰 때의 내적은 0, 방향이 같을 때의 내적은 두 벡터의 길이의 곱이다. 이러한 개념을 확장함으로써 이번 절을 끝낸다.
(Def: Orthogonality) Let $V$ he an inner product space. Vectors $x$ and $y$ in $V$ are orthogonal (perpendicular) if $<x, y> = 0$. A subset $S$ of $V$ is orthogonal if any two distinct vectors in $S$ are orthogonal. A vector $x$ in $V$ is a unit vector if $||x|| = 1$. Finally, a subset $S$ of $V$ is orthonormal if $S$ is orthogonal and consists entirely of unit vectors.
즉 orthonormal set에서의 내적의 결과는 Kronecker delta이다.
마지막으로 다음의 특수한 orthonormal set을 기억해둘 필요가 있다.
먼저 $e^{int} = \cos{nt} + i\sin{nt}$임을 참고하자. 그러면 함수 $f_n(t) = e^{int}$에 대해 위에서 정의한 $H$의 부분집합 $S = \{ f_n: n \in Z \}$를 정의하자. $<f_n, f_m> = ( 1/2\pi )\int{ e^{i(n - m)t} } = \delta_{nm}$이므로, $S$는 orthonormal set이다.
6.2. The Gram-Schmidt Orthogonalization Process and Orthogonal Complements
이번 절에서는 orthonormal basis를 형성하는 방법과, orthogonality와 공간의 관계를 공부한다.
먼저 orthonormal basis를 정의한다.
(Def: Orthonormal Basis) Let $V$ be an inner product space. A subset of $V$ is an orthonormal basis for $V$ if it is an ordered basis that is orthonormal.
벡터 공간의 임의의 벡터는 그 기저의 선형 조합으로 나타낼 수 있다. 그런데 그 기저가 만약 orthogonal일 경우, 실제로 이러한 조합의 계수를 알아낼 수 있다. 예컨대 $\beta = \{ v_1, v_2, ..., v_k \}$와 $y \in V$에 대해 $<y, v_j> = <\sum{a_i v_i}, v_j> = a_j ||v_j||^2$이다.
(Thm 6.3) Let $V$ be an inner product space and $S = \{ v_1, v_2, ..., v_k \}$ be an orthogonal subset of $V$ consisting of nonzero vectors. If $y \in span(S)$, then
$$
y = \sum_{i = 1}^k{ \frac{<y, v_i>}{||v_i||^2} v_i }
$$
그러면 다음의 두 정리가 따른다.
(Cor 1) If, in addition to the hypotheses of Theorem 6.3, $S$ is orthonormal and $y \in span(S)$, then $y = \sum{ <y, v_i> v_i }$.
(Cor 2) Let $V$ be an inner product space, and let $S$ be an orthogonal subset of $V$ consisting of nonzero vectors. Then S is linearly independent.
사실 모든 유한 차원의 벡터 공간은 orthonormal basis를 가지며, 임의의 basis로부터 이러한 orthonormal basis를 도출해낼 수 있다. 다음의 정리가 핵심적인 역할을 한다. 증명은 귀납법에 의해 가능하다.
(Thm 6.4) Let $V$ be an inner product space and $S = \{ w_1, w_2, ..., w_n \}$ be a linearly independent subset of $V$. Define $S' = \{ v_1, v_2, ..., v_n \}$, where $v_1 = w_1$ and $v_k$ for $2 ≤ k ≤ n$ is as follows. Then $S'$ is an orthogonal set of nonzero vectors such that $span(S') = span(S)$.
$$
v_k = w_k - \sum_{j = 1}^{k - 1}{ \frac{<w_k, v_j>}{||v_j||^2} v_j }
$$
위의 정리를 이용해 임의의 basis로부터 orthonormal basis를 만들어낼 수 있다. 이를 Gram-Schmidt process라 한다.
정리 6.4와 정리 6.3에 의해 다음의 정리가 당연하게도 증명된다.
(Thm 6.5) Let $V$ be a nonzero finite-dimensional inner product space. Then $V$ has an orthonormal basis $\beta$. Furthermore, if $\beta = \{ v_1, v_2,..., v_n \}$ and $x \in V$, then $x = \sum{<x, v_i> v_i}$.
위의 결과에 따라 orthonormal basis $\beta$에 의한 선형 연산자의 matrix representation이 매우 쉬워진다.
(Cor) Let $V$ be a finite-dimensional inner product space with an orthonormal basis $\beta = \{ v_1, v_2, ..., v_n \}$. Let $T$ be a linear operator on $V$, and let $A = [T]{\beta}$. Then for any $i$ and $j$, $A{ij} = <T(v_j), v_i>$.
위의 정리에서 나타난 scalar를 다음과 같이 정의한다.
(Def: Fourier Coefficient) Let $\beta$ be an orthonormal subset (possibly infinite) of an inner product space $V$, and let $x \in V$. We define the Fourier coefficients of $x$ relative to $\beta$ to be the scalars $<x, y>$, where $y \in \beta$.
이제 orthogonal complement를 다음과 같이 정의한다.
(Def: Orthogonal Complement) Let $S$ be a nonempty subset of an inner product space $V$. We define $S^{\perp}$ (read "S perp") to be the set of all vectors in $V$ that are orthogonal to every vector in $S$; that is, $S^{\perp} = \{ x \in V: <x, y> = 0 \ \forall y \in S \}$. The set $S^{\perp}$ is called the orthogonal complement of $S$.
어떤 점 $P$와 평면 $W$의 거리를 찾는다고 해보자. 이는 사실 $P$와 가장 가까운 $W$위의 점과 $P$의 거리를 찾는 문제이다. 점 $P$로 인한 벡터를 $y$, $W$위의 찾는 점에 의한 벡터를 $u$라 하면, 벡터 $z = y - u$는 $W^{\perp}$의 원소이며, 이러한 원소는 유일하다. 다음의 정리는 이러한 점들을 찾는 방법을 제시한다.
(Thm 6.6) Let $W$ be a finite-dimensional subspace of an inner product space $V$, and let $y \in V$. Then there exist unique vectors $u \in W$ and $z \in W^{\perp}$ such that $y = u + z$. Furthermore, if $\{ v_1, v_2, ..., v_k \}$ is an orthonormal basis for $W$, then $u = \sum{<y, v_i> v_i}$.
(Cor) In the notation of Theorem 6.6. the vector $u$ is the unique vector in $W$ that is "closest" to $y$; that is, for any $x \in W$, $||y - x|| ≥ ||y - u||$, and this inequality is an equality if and only if $x = u$.
이러한 벡터 $u$를 orthogonal projection of $y$ on $W$라 말한다.
마지막으로 임의의 linearly independent set은 basis로 확장될 수 있는데, 임의의 orthonormal set역시 마찬가지의 결과가 성립한다.
(Thm 6.7) Suppose that $S = \{ v_1, v_2, ..., v_k \}$ is an orthonormal set in an $n$-dimensional inner product space $V$. Then
•
$S$ can be extended to an orthonormal basis $\{ v_1, v_2, ..., v_k, v_{k + 1}, ..., v_n \}$ for $V$.
•
If $W = span(S)$, then $S_1 = \{ v_{k + 1},v_{k + 2}, ..., v_n \}$ is an orthonormal basis for $W^{\perp}$ (using the preceding notation).
•
If $W$ is any subspace of $V$, then $dim(V) = dim(W) + dim(W^{\perp})$.
6.3. The Adjoint of a Linear Operator
이번 절에서는 행렬의 conjugate transpose에 대응되는 선형 사상의 개념인 adjoint에 대해 공부한다.
먼저 $y = \sum{ \overline{ g(v_i) } v_i }$와 선형 사상 $h(x) = <x, y>$이 주어졌을 때, $g$와 $h$의 orthonormal basis에 대한 행동이 같음으로 인해, 다음이 증명된다.
(Thm 6.8) Let $V$ be a finite-dimensional inner product space over $F$, and let $g: V \rightarrow F$ be a linear transformation. Then there exists a unique vector $y \in V$ such that $g(x) = <x, y>$ for all $x \in V$.
이제 $g(x) = <T(x), y>$에 대해 위의 정리와 같은 벡터 $y' \in V$를 찾으면, $T^(y) = y'$인 $T^$에 대해 다음이 정립한다. 이러한 $T^*$를 adjoint of $T$라 한다.
(Thm 6.9) Let $V$ be a finite-dimensional inner product space, and let $T$ be a linear operator on $V$. Then there exists a unique function $T^: V \rightarrow V$ such that $<T(x), y> = <x, T^(y)>$ for all $x, y \in V$. Furthermore, $T^*$ is linear.
그러면 다음 식이 성립한다.
$$
<x, T(y)> = \overline{ <T(y), x> } = \overline{ <y, T^(x)> } = <T^(x), y>
$$
정리 6.5에 의하면 $B = [T^]{\beta}$인 $B$에 대해 $B{ij} = <T^(v_j), v_i>$였다. 이를 이용해 다음의 정리가 증명된다. 이는 adjoint의 계산에 편의를 준다.
(Thm 6.10) Let $V$ be a finite-dimensional inner product space, and let $\beta$ be an orthonormal basis for $V$. If $T$ is a linear operator on $V$, then $[T^]{\beta} = [T]{\beta}^$.
(Cor) Let $A$ be an $n \times n$ matrix. Then $L_{A^} = (L_A)^$.
다음의 정리도 어찌 저찌 증명이 가능하다. 복소수의 conjugate과 선형 사상의 adjoint가 대응된다.
(Thm 6.11) Let $V$ be an inner product space, and let $T$ and $U$ be linear operators on $V$. Then
•
$(T + U)^* = T^* + U^*$
•
$(cT)^* = \overline{c}T^*$
•
$(TU)^* = U^* T^*$
•
$T^{**} = T$
•
$I^* = I$
행렬의 conjugate transpose에도 마찬가지의 결과가 성립한다.
(Cor) Let $A$ and $B$ be $n \times n$ matrices. Then
•
$(A + B)^* = A^* + B^*$
•
$(cA)^* = \overline{c} A^*$
•
$(AB)^* = B^* A^*$
•
$A^{**} = A$
•
$I^* = I$
Least Squares Approximation
이러한 특성을 통해 회귀 분석 문제를 풀어낼 수 있다. 예컨대, 독립 변수 matrix $A$와 parmeter vector $x$, 그리고 종속 변수 벡터 $y$에 대해 $E = ||y - Ax||^2$를 최소화하는 문제이다.
먼저 선형 사상의 adjoint와 마찬가지로 다음의 정리가 증명된다.
(Lem 1) Let $A \in M_{m \times n}(F)$, $x \in F^n$, and $y \in F^m$. Then $<Ax, y>_m = <x, A^* y>_n$.
또 $Ax = 0$과 $A^* Ax = 0$이 필요충분조건임을, 즉 $A$와 $A^* A$의 null space가 같음을 보이면, dimension theorem에 의해 다음의 정리가 성립한다.
(Lem 2) Let $A \in M_{m \times n}(F)$. Then $rank(A^*A) = rank(A)$.
(Cor) If $A$ is an $m \times n$ matrix such that $rank(A) = n$, then $A^*A$ is invertible.
이제 $W = \{ Ax: x \in F^n \}$ 평면 위에, 벡터 $y$와 가장 가까운 단 하나의 점 $x_0$이 존재한다. 위에서 증명한 바와 같이 $Ax_0 - y \in W^{\perp}$이며, 이에 따라 임의의 벡터 $x$에 대해 $<Ax, Ax_0 - y> = 0$이다. 즉 $<x, A^(Ax_0 - y)> = 0$이고, $x$는 임의의 벡터이므로 $A^(Ax_0 - y) = 0$이다.
현실 세계(?)에서 대부분의 $A$는 full rank이므로, $A^*A$는 역행렬이 존재한다. 따라서 $x_0 = (A^*A)^{-1}A^*y$이다. 회귀 분석 수업에서 보던 아주 친숙한 식이다.
(Thm 6.12) Let $A \in M_{m \times n}(F)$ and $y \in F^m$. Then there exists $x_0 \in F^n$ such that $(A^*A)x_0 = A^*y$ and $||Ax_0 - y|| ≤ ||Ax - y||$ for all $x \in F^n$. Furthermore, if $rank(A) = n$, then $x_0 = (A^*A)^{-1}A^*y$.
Minimal Solutions to Systems of Linear Equations
또 이러한 성질들을 이용해 linear system $Ax = b$의 가장 작은 norm을 가진 해를 찾아낼 수 있다. 이러한 해를 minimal solution이라 하며, 놀랍게도 유일하게 존재한다.
먼저 $W = R(L_{A^*})$라 했을 때, $N(L_A) = W^{\perp}$임을 이용해 다음의 정리를 증명할 수 있다.
(Thm 6.13) Let $A \in M_{m \times n}(F)$ and $b \in F^m$. Suppose that $Ax = b$ is consistent. Then the following statements are true.
•
There exists only one minimal solutions $s$ of $Ax = b$, and $s \in R(L_{A^*})$.
•
The vector $s$ is the only solution to $Ax = b$ that lies in $R(L_{A^})$; that is, if $u$ satisfies $(AA^)u = b$, then $s = A^*u$.
6.4. Normal and Self-adjoint Operators
5장에서 대각화 가능성의 중요성에 대해 논했다. 이러한 대각화 가능성은 eigenvector로 이루어진 basis가 존재하는가의 문제로 치환된다. 또 이번 장에서는 orthonormal vector로 이루어진 basis의 존재의 중요성에 대해 논했다. 이번 절에서는 자연스럽게, eigenvector로 이루어진 orthonormal basis의 존재성에 대해 공부한다.
먼저 $T$가 eigenvector $v$를 가진다면, $0 = <0, x> = <(T - \lambda I)(v), x> = <v, (T - \lambda I)^(x)> = <v, (T^ - \lambda I)(x)>$에서 $T^*$가 eigenvector를 가짐을 알 수 있다.
(Lem) Let $T$ be a linear operator on a finite-dimensional inner product space $V$. If $T$ has an eigenvector, then so does $T^*$.
이제 귀납법에 의해 다음의 정리를 증명할 수 있다.
(Thm 6.14: Schur) Let $T$ be a linear operator on a finite-dimensional inner product space $V$. Suppose that the characteristic polynomial of $T$ splits. Then there exists an orthonormal basis $\beta$ for $V$ such that the matrix $[T]_{\beta}$ is upper triangular.
한편 $T$가 대각화 가능하다고 하자. 그러면 eigenvector로 이루어진 기저 $\beta$에 대해 $[T]{\beta}$는 대각 행렬이고, $[T]{\beta}^$역시 대각 행렬이다. 따라서 이 두 행렬의 곱의 교환 법칙이 성립한다. 그러면 당연히 선형 사상 $T$에서도 마찬가지이다. 즉 $T^ T = T T^*$. 이러한 선형 사상을 정의한다.
(Def: Normality) Let $V$ be an inner product space, and let $T$ be a linear operator on $V$. We say that $T$ is normal if $TT^* = T^T$. An $n \times n$ real or complex matrix $A$ is normal if $AA^ = A^*A$.
하지만 이러한 normality가 eigenvector로 이루어진 orthonormal basis의 존재를 보장해주지는 않는다. 하지만, 사실 벡터 공간 $V$가 complex inner product space라면 이야기가 달라진다.
먼저 다음의 정리는 normal operator의 대표적인 성질을 말한다.
(Thm 6.15) Let $V$ be an inner product space, and let $T$ be a normal operator on $V$. Then the following statements are true.
•
$||T(x)|| = ||T^*(x)||$ for all $x \in V$.
•
$T - cI$ is normal for every $c \in F$.
•
If $x$ is an eigenvector of $T$, then $x$ is also an eigenvector of $T^$. In fact, if $T(x) = \lambda x$, then $T^(x) = \overline{\lambda} x$.
•
If $\lambda_1$ and $\lambda_2$ are distinct eigenvalues of $T$ with corresponding eigenvectors $x_1$ and $x_2$, then $x_1$ and $x_2$ are orthogonal.
그러면 다음의 정리가 성립한다! 즉 complex inner product space에서 정의된 선형 연산자에 대해서는, 우리가 찾는 그 기저의 존재와 normality가 서로 필요충분하다.
(Thm 6.16) Let $T$ be a linear operator on a finite-dimensional complex inner product space $V$. Then $T$ is normal if and only if there exists an orthonormal basis for $V$ consisting of eigenvectors of $T$.
한편, real inner product space에서 마찬가지의 논의를 하기 위해서는, 조금 더 강력한 조건을 정의해야 한다.
(Def: Self-adjoint) Let $T$ be a linear operator on an inner product space $V$. We say that $T$ is self-adjoint (Hermitian) if $T = T^$. An $n \times n$ real or complex matrix $A$ is self-adjoint (Hermitian) if $A = A^$.
선형 연산자 $T$가 self-adjoint일 필요충분조건은 당연히 orthonormal basis $\beta$에 대해 $A = [T]_{\beta}$가 self-adjoint임이다. 실수에서 정의된 행렬에서는 self-adjoint와 symmetric이 같다.
이제 다음의 정리를 살펴보자.
(Lem) Let $T$ be a self-adjoint operator on a finite-dimensional inner product space $V$. Then
•
Every eigenvalue of $T$ is real.
•
Suppose that $V$ is a real inner product space. Then the characteristic polynomial of $T$ splits.
이제 두 번째 조건에 의해 Schur의 정리를 이용할 수 있다. Upper triangular matrix가 동시에 self-adjoint이므로, 당연하게도 대각 행렬이다.
(Thm 6.17) Let $T$ be a linear operator on a finite-dimensional real inner product space $V$. Then $T$ is self-adjoint if and only if there exists an orthonormal basis $\beta$ for $V$ consisting of eigenvectors of $T$.
6.5. Unitary and Orthogonal Operators and Their Matrices
Conjugate와 adjoint가 그렇듯, 이번 절에서도 선형 연산자와 복소수의 대응성에 대해 계속 공부한다.
먼저, $z\overline{z} = 1$인 복소수에 대응되는 선형 연산자 $T$에 대해 공부한다. 즉 $T^T = TT^ = I$. 특히, 이러한 선형 연산자는 벡터의 길이를 보전한다.
(Def: Unitary) Let $T$ be a linear operator on a finite-dimensional inner product space $V$ (over $F$). If $||T(x)|| = ||x||$ for all $x \in V$, we call $T$ a unitary operator if $F = C$ and an orthogonal operator if $F = R$.
이러한 unitary operator 정의와 동치가 되는 조건들은 다음과 같다. 증명은 생략한다.
(Thm 6.18) Let $T$ be a linear operator on a finite-dimensional inner product space $V$. Then the following statements are equivalent.
•
$TT^* = T^*T = I$.
•
$<T(x), T(y)> = <x, y>$ for all $x, y \in V$.
•
If $\beta$ is an orthonormal basis for $V$, then $T(\beta)$ is an orthonormal basis for $V$.
•
There exists an orthonormal basis $\beta$ for $V$ such that. $T(\beta)$ is an orthonormal basis for $V$.
•
$||T(x)|| = ||x||$ for all $x \in V$.
위를 증명하기 위해서는 다음의 준비정리가 필요하다. 정리 6.16과 정리 6.17에 의해 self-adjoint operator는 eigenvector로 이루어진 orthonormal basis가 존재하는데, $x \in \beta$라 하면 $0 = <x, U(x)> = \overline{\lambda} <x, x>$이므로 $\lambda = 0$이다. 즉 임의의 벡터 $x \in \beta$에 대해 $U(x) = 0$이다. 다음의 정리가 증명되었다.
(Lem) Let $U$ be a self-adjoint operator on a finite-dimensional inner product space $V$. If $<x, U(x)> = 0$ for all $x \in V$, then $U = T_0$.
어쨌거나 정리 6.18에 의해 unitary(orthogonal) operator의 eigenvalue는 1의 절댓값을 가짐을 알 수 있다. 심지어, 정의에 의해 다음의 정리도 성립한다.
(Cor 1) Let $T$ be a linear operator on a finite-dimensional real inner product space $V$. Then $V$ has an orthonormal basis of eigenvectors of $T$ with corresponding eigenvalues of absolute value 1 if and only if $T$ is both sell-adjoint and orthogonal.
또한 unitary operator는 normal operator임을 기억($T^T = TT^ = I$)하면, 다음도 마찬가지이다.
(Cor 2) Let $T$ be a linear operator on a finite-dimensional complex inner product space $V$. Then $V$ has an orthonormal basis of eigenvectors of $T$ with corresponding eigenvalues of absolute value 1 if and only if $T$ is unitary.
Unitary(orthogonal) operator의 예시로 다음과 같은 reflection을 정의한다.
(Def: Reflection) Let $L$ be a one-dimensional subspace of $R^2$. We may view $L$ as a line in the plane through the origin. A linear operator $T$ on $R^2$ is called a reflection of $R^2$ about $L$ if $T(x) = x$ for all $x \in L$ and $T(x) = -x$ for all $x \in L^{\perp}$.
다음의 unitary(orthogonal) operator의 행렬 버전이다.
(Def: Unitary Matrix) A square matrix $A$ is called an orthogonal matrix if $A^tA = AA^t = I$ and unitary if $A^A = AA^ = I$.
정의에 의해, unitary matrix $A$의 각 행은 $F^n$의 orthonormal basis를 이룬다. 즉
$$
\delta_{ij} = (AA^){ij} = \sum_k{ A{ik}A^{kj} } = \sum_k{ A{ik} \overline{ A_{jk} } }
$$
$A^*A = I$를 이용하면 각 열에 대해서도 마찬가지이다.
Complex normal(혹은 real symmetric) 행렬 $A$에 대해, $A$의 eigenvector로 이루어진 $F^n$의 orthonormal basis $\beta$가 존재한다. 그러면 $A$는 어떤 대각 행렬 $D$와 닮음, 즉 $D = Q^{-1}DQ$인데, 이 때의 $Q$가 바로 $\beta$의 벡터들이 열을 이루어 만들어진 행렬이다. $\beta$는 eigenvector로 이루어진 orthonormal basis였기 때문에, 당연히 $Q$는 unitary(orthogonal) matrix이다. 이러한 상황을 unitarily(orthogonally) equivalent하다고 한다.
위 문단은 아래 두 정리의 한쪽 방향을 증명한다. 나머지 방향도 꽤 간단히 증명할 수 있다.
(Thm 6.19) Let $A$ be a complex $n \times n$ matrix. Then $A$ is normal if and only if $A$ is unitarily equivalent to a diagonal matrix.
(Thm 6.20) Let $A$ be a real $n \times n$ matrix. Then $A$ is symmetric if and only if $A$ is orthogonally equivalent to a real diagonal matrix.
또 정리 6.14(Schur's Theorem)에 의해 다음의 정리는 당연하다. 행렬 버전이다.
(Thm 6.21: Schur) Let $A \in M_{n \times n}(F)$ be a matrix whose characteristic polynomial splits over F.
•
If $F = C$, then $A$ is unitarily equivalent to a complex upper triangular matrix.
•
If $F = R$, then $A$ is orthogonally equivalent to a real upper triangular matrix.
Rigid Motions
길이를 보전하는 연산자가 unitary(orthogonal) operator였다면, 모형을 보전하는 연산자는 rigid motion이다. 모형을 보전한다는 것이 무엇인고 하니, 바로 거리를 보전한다는 것이다.
(Def: Rigid Motion) Let $V$ be a real inner product space. A function $f: V \rightarrow V$ is called a rigid motion if $|| f(x) - f(y) || = || x - y ||$.
예를 들어, 유한 차원의 real inner product space에서 정의된 임의의 orthogonal operator가 rigid motion임은 쉽게 보일 수 있다. 한편 또 다른 종류의 rigid motion인 translation을 다음과 같이 정의한다.
(Def: Translation) A function $g: V \rightarrow V$, where $V$ is a real inner product space, is called a translation if there exists a vector $v_0 \in V$ such that $g(x) = x + v_0$ for all $x \in V$.
임의의 두 orthogonal operator와 translation의 합성은 rigid motion이다. 특히 rigid motion은 이러한 orthogonal operator과 translation의 unique composite으로 특징지어진다.
(Thm 6.22) Let $f: V \rightarrow V$ be a rigid motion on a finite-dimensional real inner product space $V$. Then there exists a unique orthogonal operator $T$ on $V$ and a unique translation $g$ on $V$ such that $f = g \circ T$.
Orthogonal Operators on $R^2$
Rigid motion의 이해를 위해서는 orthogonal operator를 특징지을 필요가 있었다. 이번 절에서는 평면에서의 orthogonal operator를 특징짓는 일을 한다.
먼저 다음의 정리가 성립한다. $T$가 orthogonal operator이기 때문에, $T(\beta)$는 orthonormal basis이다. 따라서 $T(e_1) = (\cos{\theta}, \sin{\theta})$인 각 $\theta$가 정해지는데, $T(\beta)$는 orthogonal set이므로 $T(e_2)$는 $(-\sin{\theta}, \cos{\theta})$이거나 $(\sin{\theta}, -\cos{\theta})$이다. 전자의 경우가 첫 번째 조건, 후자의 경우가 두 번째 조건에 해당한다.
(Thm 6.23) Let $T$ be an orthogonal operator on $R^2$, and let $A = [T]_{\beta}$, where $\beta$ is the standard ordered basis for $R^2$. Then exactly one of the following conditions is satisfied:
•
$T$ is a rotation, and $det(A) = 1$.
•
$T$ is a reflection about a line through the origin, and $det(A) = -1$.
이제 정리 6.22와 6.23을 합치면 다음과 같이 말할 수 있다.
(Cor) Any rigid motion on $R^2$ is either a rotation followed by a translation or a reflection about a line through the origin followed by a translation.
Conic Sections
이번 절에서는 associated quadratic form $ax^2 + 2bxy + cy^2$에서 지저분한 $xy$-term을 제거하는 방법을 배운다.
먼저 $A = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$와 $X = \begin{pmatrix} x \\ y \end{pmatrix}$에 대해, 위의 식을 $X^t A X = <AX, X>$로 쓸 수 있다. 이 때 $X$가 symmetric matrix라는 것이 핵심이다.
정리 6.20에 따르면, $A$는 어떤 대각 행렬 $D$와 orthogonally equivalent하다. 즉 $P^tAP = D$인 orthogonal matrix $P$를 찾을 수 있다.
이제 $PX' = PP^tX = X$인 $X' = (x' \ \ y')^t$를 정의하자. 그러면 $X^tAX = (PX')^tA(PX') = X'^t(P^tAP)X' = X'^tDX'$이다. 즉 $P$의 각 열을 $v_1, v_2$라고 한다면, 이에 상응하는 eigenvalue $\lambda_1, \lambda_2$에 대해 $\lambda_1 (x')^2 + \lambda_2 (y')^2$이다.
한편 $P$는 orthogonal matrix이므로, $det(P) = 1$ 혹은 $det(P) = -1$이다. 그런데 열의 순서를 바꿈으로써 항상 $det(P) = 1$인 $P$를 얻을 수 있다. 참고로 이는 $P$가 어떤 각도에 대한 rotation임을 나타낸다.
정리하자면 $A$는 symmetric matrix이므로 eigenvalue를 찾은 후 eigenvector로 구성된 basis를 찾으면 orthonormal할 것이다. 이 때 이 basis의 벡터들을 열로 포함하는 행렬 $P$를 구하면, $PX' = X$인 $X'$에 대해 $X^t A X = X'^t D X'^t$이다. 당연히 $D$는 관련된 eigenvalue들로 이루어진 대각 행렬이다.
6.6. Orthogonal Projections and the Spectral Theorem
이번 절에서는 normal(if $F = C$) operator 혹은 self-adjoint (if $F = R$) operator $T$를 decompose하는 방법을 배운다. 바로 spectral decomposition이다.
먼저 2장에서 보았던 projection (on $W_1$ along $W_2$)를 떠올리자. 이러한 projection $T$에 대해, $W_1 = R(T)$, $W_2 = N(T)$임을 알 수 있다. 또한 $T$가 projection일 필요충분조건은 $T^2 = T$이다.
(Def: Orthogonal Projection) Let $V$ be an inner product space, und let $T: V \rightarrow V$ be a projection. We say that $T$ is an orthogonal projection if $R(T)^{\perp} = N(T)$ and $N(T)^{\perp} = R(T)$.
하지만 projection은 그 range에 의해 특정지어지지는 않는다. 하지만 orthogonal projection은 그 정의상 range에 의해 특정지어진다. 이러한 결과가 다음의 정리에 담겨있다.
(Thm 6.24) Let $V$ be an inner product space, and let $T$ be a linear operator on $V$. Then $T$ is an orthogonal projection if and only if $T$ has an adjoint $T^$ and $T^2 = T = T^$.
이제 $V$에서 정의된 $T$가 $W$에 대한 projection이라고 하고, $V$의 orthonormal basis $\beta = \{ v_1, ..., v_n \}$을 잡되, $\{ v_1, ..., v_k \}$가 $W$의 orthonormal basis가 되도록 하자. 그러면 $[T]_{\beta}$는 다음의 형태를 가진다.
$$
[T]_{\beta} = \begin{pmatrix}
I_k & O_1 \\
O_2 & O_3
\end{pmatrix}
$$
다음은 이 절의 핵심 정리이다.
(Thm 6.25: The Spectral Theorem) Suppose that $T$ is a linear operator on a finite-dimensional inner product space $V$ over $F$ with the distinct eigenvalues $\lambda_1, ..., \lambda_k$. Assume that $T$ is normal if $F = C$ and that $T$ is self-adjoint if $F = R$. For each $i (1 ≤ i ≤ k)$, let $W_i$ be the eigenspace of $T$ corresponding to the eigenvalue $\lambda_i$, and let $T_i$ be the orthogonal projection of $V$ on $W_i$. Then the following statements are true.
•
$V = W_1 \oplus ... \oplus W_k$.
•
If $W_i'$ denotes the direct sum of the subspaces $W_j$ for $i ≠ j$, then $W_i^{\perp} = W_i'$.
•
$T_iT_j = \delta_{ij}T_i$ for $1 ≤ i, j ≤ k$.
•
$I = T_1 + T_2 + ... + T_k$.
•
$T = \lambda_1 T_1 + \lambda_2 T_2 + ... + \lambda_k T_k$.
이 때 $\{ \lambda_1, ..., \lambda_k \}$를 $T$의 spectrum, $I = T_1 + ... + T_k$를 resolution of the identity operator induced by $T$, 그리고 $T = \lambda_1 T_1 + ... + \lambda_k T_k$를 spectral decomposition of $T$라 한다.
또 $\beta$를 $W_i$의 orthonormal basis의 합집합이라 하고, 또 $m_i = dim(W_i)$라 하자. 그러면 $[T]_{\beta}$는 다음과 같은 형태를 띈다.
$$
[T]{\beta} = \begin{pmatrix}
\lambda_1 I{m_1} & O & ... & O \\
O & \lambda_2 I_{m_2} & ... & O \\
... & ... & ... & ... \\
O & O & ... & \lambda_k I_{m_k}
\end{pmatrix}
$$
이제 몇 가지 흥미로운 따름정리들을 나열한다.
(Cor 1) If $F = C$, then $T$ is normal if and only if $T^* = g(T)$ for some polynomial $g$.
(Cor 2) If $F = C$, then $T$ is unitary if and only if $T$ is normal and $|\lambda| = 1$ for every eigenvalue $\lambda$ of $T$.
(Cor 3) If $F = C$ and $T$ is normal, then $T$ is self-adjoint if and only if every eigenvalue of $T$ is real.
(Cor 4) Let $T$ he as in the spectral theorem with spectral decomposition $T = \lambda_1 T_1 + ... + \lambda_k T_k$. Then each $T_j$ is a polynomial in $T$.
6.7. The Singular Value Decomposition and the Pseudoinverse
드디어 대망의 SVD에 도착했다. Pseudoinverse도 그렇고 SVD도 그렇고, 머신 러닝에서 간간히 보이는 테크닉이다. 사실 그 간단해보이는 테크닉이 이렇게 길고 지루한 이론의 끝에 있는 것이었다...
이전 절에서 complex space에서는 normal operator, real space에서는 self-adjoint operator을 eigenvector로 이루어진 orthonormal basis의 관점에서 다루었다. 이번 절에서는 이전 절과 상응하는, 그러나 모든 linear transformation으로 확장되는 정리인 singular value theorem을 배운다.
•
우선 선형 연산자에서 정의되었던 adjoint의 개념을 전체 선형 사상으로 확장한다. 유한 차원의 inner product space에서 정의된 선형 사상 $T: V \rightarrow W$의 adjoint $T^: W \rightarrow V$는 각각 $V$와 $W$의 orthonormal basis $\beta$, $\gamma$에 대해 $[T^]^{\beta}{\gamma} = ([T]{\beta}^{\gamma})^*$이다.
•
또한 선형 연산자인 $T^*T$는 positive semidefinite이며 $rank(T^*T) = rank(T)$이다.
이 때 positive definite은 symmetric(혹은 complex space에서 Hermetian) matrix $A$가 임의의 열벡터 $v$에 대해 $z^TAz > 0$인 경우를 말한다. Positive semidefinite은 부등식에서 0을 포함하는 것으로 정의된다.
이제 다음의 핵심 정리를 증명할 수 있다.
(Thm 6.26: Singular Value Theorem) Let $V$ and $W$ be finite-dimensional inner product spaces, and let $T: V \rightarrow W$ be a linear transformation of rank $r$. Then there exist orthonormal bases $\{ v_1, v_2, ..., v_n \}$ for $V$ and $\{ u_1, u_2, ..., u_m \}$ for $W$ and positive scalars $\sigma_1 ≥ \sigma_2 ≥ ... ≥ \sigma_r$ such $T(v_i) = \sigma_i u_i$ for $1 ≤ i ≤ r$ and $T(v_i) = 0$ for $i > r$.
Conversely, suppose that the preceding conditions are satisfied. Then for $1 ≤ i ≤ n$, $v_i$ is an eigenvector of $T^*T$ with corresponding eigenvalue $\sigma_i^2$ if $1 ≤ i ≤ r$ and $0$ if $i > r$. Therefore the scalars $\sigma_1, \sigma_2, ..., \sigma_r$ are uniquely determined by $T$.
위의 정리에서 등장한 scalar들을 singular value라고 부른다.
(Def: Singular Value) The unique scalars $\sigma_1, ..., \sigma_r$ in Theorem 6.26 are called the singular values of $T$. If $r$ is less than both $m$ and $n$, then the term singular value is extended to include $\sigma_{r + 1} = ... = \sigma_k = 0$, where $k$ is the minimum of $m$ and $n$.
Singular value는 $T$에 의해 유일하게 결정되지만, $T^T$의 orthonormal basis는 여러 개 있을 수 있다. 또한 $T$와 $T^$는 singular value를 공유한다.
이제 위 정리에 따라 $V$의 orthonormal basis $\beta$와 $T^*T$의 eigenvalue, 그리고 그에 상응하는 $\beta$의 eigenvector를 찾으면 $W$의 orthonormal basis $\gamma$를 찾을 수 있다.
또 이러한 singular value를 통해 도형이 선형 사상에 의해 어떻게 변하는지를 확인할 수 있다. 예컨대 평면에서의 invertible linear operator $T$와 orthonormal basis $\beta = \{ v_1, v_2 \}$, $\gamma = \{ u_1, u_2 \}$가 있어서 $T(v_1) = \sigma_1 u_1$, $T(v_2) = \sigma_2 u_2$라 하자. 그러면 $T$는 $\beta$-coordinate의 벡터 $v = x_1 v_1 + x_2 v_2$를 $u = x_1' u_1 + x_2' u_2 = x_1 \sigma_1 u_1 + x_2 \sigma_2 u_2$로 사상한다. 예컨대 단위원 $S$와 $S' = T(S)$에 대해 $u \in S'$일 필요충분조건은 $v \in S$이고, 이는 $(x_1')^2/\sigma_1^2 + (x_2')^2/\sigma_2^2 = x_1^2 + x_2^2 = 1$을 의미한다.
이제 이러한 singular value를 행렬의 개념으로 가져오면 계산이 보다 수월해진다.
(Def: Singular Value) Let $A$ be an $m \times n$ matrix. We define the singular values of $A$ to be the singular values of the linear transformation $L_A$.
(Thm 6.27: Singular Value Decomposition) Let $A$ be an $m \times n$ matrix of rank $r$ with the positive singular values $\sigma_1 ≥ \sigma_2 ≥ ... ≥ \sigma_r$, and let $\Sigma$ be the $m \times n$ matrix defined by $\Sigma_{ij} = \sigma_i$ if $i = j ≤ r$ and $\Sigma_{ij} = 0$ otherwise. Then there exists an $m \times m$ unitary matrix $U$ and an $n \times n$ unitary matrix V such that $A = U \Sigma V^*$.
(Def: Singular Value Decomposition) Let $A$ be an $m \times n$ matrix of rank $r$ with positive singular values $\sigma_1 ≥ ... ≥ \sigma_r$. A factorization $A = U \Sigma V^*$ where $U$ and $V$ are unitary matrices and $\Sigma$ is the $m \times n$ matrix defined as in Theorem 6.27 is called a singular value decomposition of $A$.
이 때 $T = L_A: F^n \rightarrow F^m$에서 $\beta$를 $F^n$의 orthonormal basis, $\gamma$를 $F^m$의 orthonormal basis라 하자. 그러면 $V$의 열은 $\beta$의 원소, $U$의 열은 $\gamma$의 원소이다. 또한 $A$의 singular value는 $A^A = AA^$의 nonzero eigenvalue의 제곱근이다.
The Polar Decomposition of a Square Matrix
먼저 SVD를 이용해 정사각 행렬을 unitary matrix와 positive semidefinite matrix로 decompose할 수 있다. $A = U \Sigma V^* = U V^* V \Sigma V^$를 생각해보면, $UV^$는 unitary marix이고, $V \Sigma V^*$는 positive semidefinite이다. 즉
(Thm 6.28: Polar Decomposition) For any square matrix $A$, there exists a unitary matrix $W$ and a positive semidefinite matrix $P$ such that $A = WP$.
The PseudoInverse
이제 역사상이 존재하지 않는 어떤 선형 사상 $T$에 대해, 역사상의 성질을 가지고 있는 어떤 역사상 비슷한 사상을 정의해보고자 한다. 역행렬이 존재하지 않는 이유는 정의역과 치역이 일대일 대응하지 않기 때문이다. 즉 선형 사상 $T$의 정의역을 $N(T)^{\perp}$로, 치역을 $R(T)$로 제한하면, 그 사상은 역사상이 존재한다. 이를 이용해 다음의 정의를 내린다.
(Def: Pseudoinverse) Let $V$ and $W$ be finite-dimensional inner product spaces over the same field, and let $T: V \rightarrow W$ be a linear transformation. Let $L: N(T)^{\perp} \rightarrow R(T)$ be the linear transformation defined by $L(x) = T(x)$ for all $x \in N(T)^{\perp}$. The pseudoinverse (or Moore-Penrose generalized inverse) of $T$, denoted by $T^{\dagger}$, is defined as the unique linear transformation from $W$ to $V$ such that $T^{\dagger}(y) = L^{-1}(y)$ for $y \in R(T)$ and $T^{\dagger}(y) = 0$ for $y \in R(T)^{\perp}$.
이러한 pseudoinverse는 $T$가 invertible하지 않을때도 존재하며, $T$가 invertible하다면 당연히 $T^{-1} = T^{\dagger}$이다.
한편 singular value theorem으로 이러한 pseudoinverse를 설명할 수 있다. $\beta$와 $\gamma$, 그리고 $T$는 정리 6.26에서와 같이 정의하자. 그러면 $\{ v_1, v_2, ..., v_r \}$은 $N(T)^{\perp}$의 orthonormal basis이고, $\{ v_{r + 1}, ..., v_{n} \}$은 $N(T)$의 orthonormal basis이다. 한편 $\{ u_1, u_2, ..., u_r \}$은 $R(T)$의 orthonormal basis이고, $\{ u_{r + 1}, ..., u_m \}$은 $R(T)^{\perp}$의 orthonormal basis이다. 이제 $L$을 pseudoinverse의 정의에서와 같이 $T$의 $N(T)^{\perp}$에 대한 restriction이라고 정의하면, $T^{\dagger}(u_i) = \frac{1}{\sigma_i}v_i$ for $1 ≤ i ≤ r$, $0$ otherwise이다.
선형 사상의 pseudoinverse에 대응하는 행렬이 딱 하나 있는데, 다음과 같이 마찬가지로 정의할 수 있다.
(Thm 6.29) Let $A$ be an $m \times n$ matrix of rank $r$ with a singular value decomposition $A = U \Sigma V^$ and nonzero singular values $\sigma_1 ≥ ... ≥ \sigma_r$. Let $\Sigma^{\dagger}$ be the $n \times m$ matrix defined by $\Sigma^{\dagger}_{ij} = \frac{1}{\sigma_i}$ for $i = j ≤ r$ and $0$ otherwise. Then $A^{\dagger} = V \Sigma^{\dagger} U^$, and this is a singular value decomposition of $A^{\dagger}$.
The Pseudoinverse and Systems of Linear Equations
Linear system $Ax = b$에서, $A$가 invertible할 경우 linear system은 단 하나의 해를 가진다. 이 때의 해는 $A^{-1}b$이다. 그런데, pseudoinverse에 대해서는 어떤 관계가 성립할까? 즉 $A^{\dagger}b$는 linear system에서 어떤 역할을 할까?
먼저 다음의 준비정리를 보자. 생각해보면 쉽게 증명할 수 있다.
(Lem) Let $V$ and $W$ be finite-dimensional inner product spaces, and let $T: V \rightarrow W$ be linear. Then
•
$T^{\dagger}T$ is the orthogonal projection of $V$ on $N(T)^{\perp}$.
•
$TT^{\dagger}$ is the orthogonal projection of $W$ on $R(T)$.
이제 다음의 정리를 증명할 수 있다.
(Thm 6.30) Consider the system of linear equations $Ax = b$, where $A$ is an $m \times n$ matrix and $b \in F^m$. If $z = A^{\dagger}b$, then $z$ has the following properties.
•
If $Ax = b$ is consistent, then $z$ is the unique solution to the system having minimum norm. That is, $z$ is a solution to the system, and if $y$ is any solution to the system, then $||z|| ≤ ||y||$ with equality if and only if $z = y$.
•
If $Ax = b$ is inconsistent, then $z$ is the unique best approximation to a solution having minimum norm. That is, $||Az - b|| ≤ ||Ay - b||$ for any $y \in F^n$, with equality if and only if $Az = Ay$. Furthermore, if $Az = Ay$, then $||z|| ≤ ||y||$ with equality if and only if $z = y$.