이번 포스트에서는 orthogonal set에 대해서 알아보겠습니다.
1) Orthogonal set
Definition : Orthogonal set
A set of vectors { u 1 , . . . , u p } \{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} { u 1 , . . . , u p } R n \mathbb R^n R n
u i ⋅ u j = 0 f o r a l l i ≠ j \boldsymbol{u_i} \cdot \boldsymbol{u_j} =0 \ \ for \ \ all \ \ i\neq j u i ⋅ u j = 0 f o r a l l i = j set에 속한 벡터들간 orthogonal하면, orthogonal set이라고 합니다.
example
u 1 = [ 3 1 1 ] , u 2 = [ − 1 2 1 ] , u 3 = [ − 1 2 − 2 7 2 ] \boldsymbol{u_1} = \begin{bmatrix}3 \\ 1 \\ 1 \end{bmatrix}, \ \ \boldsymbol{u_2} = \begin{bmatrix}-1 \\ 2 \\ 1 \end{bmatrix}, \ \ \boldsymbol{u_3} = \begin{bmatrix}-\frac{1}{2} \\ -2 \\ \frac{7}{2}\end{bmatrix} u 1 = ⎣ ⎢ ⎡ 3 1 1 ⎦ ⎥ ⎤ , u 2 = ⎣ ⎢ ⎡ − 1 2 1 ⎦ ⎥ ⎤ , u 3 = ⎣ ⎢ ⎡ − 2 1 − 2 2 7 ⎦ ⎥ ⎤ 일 때
u 1 ⋅ u 2 = u 1 ⋅ u 3 = u 2 ⋅ u 3 = 0 \boldsymbol{u_1} \cdot \boldsymbol{u_2} = \boldsymbol{u_1}\cdot \boldsymbol{u_3} = \boldsymbol{u_2}\cdot \boldsymbol{u_3}=0 u 1 ⋅ u 2 = u 1 ⋅ u 3 = u 2 ⋅ u 3 = 0 을 만족하기 때문에,
{ u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 } 는 orthogonal set입니다.
Theorem
If S = { u 1 , . . . , u p } S=\{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} S = { u 1 , . . . , u p } R n \mathbb R^n R n S S S S S S
Orthogonal set의 특징입니다. Orthogonal set은 linearly independent set이 되고, 따라서 orthogonal set S S S S S S
Definition : Orthogonal basis
An orthogonal basis for a subspace W W W R n \mathbb R^n R n W W W
subspace W W W
orthogonal basis를 알면, W W W
Theorem
Let { u 1 , . . . , u p } \{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} { u 1 , . . . , u p } W W W R n \mathbb R^n R n y \boldsymbol{y} y W W W
y = c 1 u 1 + ⋯ + c p u p \boldsymbol{y}=c_1\boldsymbol{u_1}+\cdots + c_p\boldsymbol{u_p} y = c 1 u 1 + ⋯ + c p u p and
c j = u j ⋅ y u j ⋅ u j , j = 1 , . . . , p c_j = \frac{\boldsymbol{u_j}\cdot \boldsymbol{y}}{\boldsymbol{u_j}\cdot\boldsymbol{u_j}}, \ \ \ j=1, ..., p c j = u j ⋅ u j u j ⋅ y , j = 1 , . . . , p 일반적인 basis를 이용했다면, linear combination의 coefficient를 구하기 위해서는 linear system을 풀어야 coefficient를 구할 수 있었습니다. 하지만, 만약 basis가 orthogonal basis라면, orthogonal의 성질과 inner product를 이용하여 linear combination의 coefficients를 쉽게 구할 수 있습니다.
example
u 1 = [ 3 1 1 ] , u 2 = [ − 1 2 1 ] , u 3 = [ − 1 2 − 2 7 2 ] , y = [ 6 1 − 8 ] \boldsymbol{u_1} = \begin{bmatrix}3 \\ 1 \\ 1 \end{bmatrix}, \boldsymbol{u_2} = \begin{bmatrix}-1 \\ 2 \\ 1 \end{bmatrix}, \boldsymbol{u_3}=\begin{bmatrix}-\frac{1}{2} \\ -2 \\ \frac{7}{2} \end{bmatrix}, \boldsymbol{y}=\begin{bmatrix}6 \\ 1\\ -8 \end{bmatrix} u 1 = ⎣ ⎢ ⎡ 3 1 1 ⎦ ⎥ ⎤ , u 2 = ⎣ ⎢ ⎡ − 1 2 1 ⎦ ⎥ ⎤ , u 3 = ⎣ ⎢ ⎡ − 2 1 − 2 2 7 ⎦ ⎥ ⎤ , y = ⎣ ⎢ ⎡ 6 1 − 8 ⎦ ⎥ ⎤ { u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 } R 3 \mathbb R^3 R 3 y \boldsymbol{y} y u 1 , u 2 , u 3 \boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3} u 1 , u 2 , u 3
y = c 1 u 1 + c 2 u 2 + c 3 u 3 \boldsymbol{y}=c_1\boldsymbol{u_1}+c_2\boldsymbol{u_2}+c_3\boldsymbol{u_3} y = c 1 u 1 + c 2 u 2 + c 3 u 3 만약 { u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 } c 1 , c 2 , c 3 c_1, c_2, c_3 c 1 , c 2 , c 3 { u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 }
y ⋅ u 1 = c 1 u 1 ⋅ u 1 y ⋅ u 2 = c 2 u 2 ⋅ u 2 y ⋅ u 3 = c 3 u 3 ⋅ u 3 \boldsymbol{y}\cdot\boldsymbol{u_1} = c_1\boldsymbol{u_1}\cdot\boldsymbol{u_1} \\ \boldsymbol{y}\cdot\boldsymbol{u_2} = c_2\boldsymbol{u_2}\cdot\boldsymbol{u_2} \\ \boldsymbol{y}\cdot\boldsymbol{u_3} = c_3\boldsymbol{u_3}\cdot\boldsymbol{u_3} y ⋅ u 1 = c 1 u 1 ⋅ u 1 y ⋅ u 2 = c 2 u 2 ⋅ u 2 y ⋅ u 3 = c 3 u 3 ⋅ u 3 가 성립합니다 따라서
c 1 = y ⋅ u 1 u 1 ⋅ u 1 = 1 , c 2 = y ⋅ u 2 u 2 ⋅ u 2 = − 2 , c 3 = y ⋅ u 3 u 3 ⋅ u 3 = − 2 c_1 = \frac{\boldsymbol{y}\cdot \boldsymbol{u_1}}{\boldsymbol{u_1}\cdot \boldsymbol{u_1}} =1 , c_2 = \frac{\boldsymbol{y}\cdot \boldsymbol{u_2}}{\boldsymbol{u_2}\cdot \boldsymbol{u_2}} =-2, c_3=\frac{\boldsymbol{y}\cdot\boldsymbol{u_3}}{\boldsymbol{u_3}\cdot\boldsymbol{u_3}} =-2 c 1 = u 1 ⋅ u 1 y ⋅ u 1 = 1 , c 2 = u 2 ⋅ u 2 y ⋅ u 2 = − 2 , c 3 = u 3 ⋅ u 3 y ⋅ u 3 = − 2 가 되고,
y = u 1 − 2 u 2 − 2 u 3 \boldsymbol{y}=\boldsymbol{u_1}-2\boldsymbol{u_2}-2\boldsymbol{u_3} y = u 1 − 2 u 2 − 2 u 3 임을 알 수 있습니다.
2) Orthonormal set
Definition : Orthonormal set
A set { u 1 , . . . , u p } \{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} { u 1 , . . . , u p }
orthogonal set 조건을 만족하면서 set에 속한 각 벡터의 length가 1인 경우, orthonormal set이라고 합니다.
Standard basis { e 1 , . . . , e n } \{\boldsymbol{e_1}, ..., \boldsymbol{e_n}\} { e 1 , . . . , e n } R n \mathbb R^n R n
e 1 = [ 1 0 ⋮ 0 ] , e 2 = [ 0 1 ⋮ 0 ] , . . . , e n = [ 0 0 ⋮ 1 ] \boldsymbol{e_1}=\begin{bmatrix}1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \boldsymbol{e_2}=\begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{bmatrix}, ..., \boldsymbol{e_n}=\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1\end{bmatrix} e 1 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 ⋮ 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ , e 2 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 ⋮ 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ , . . . , e n = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 0 0 ⋮ 1 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ 일 때, 각 벡터들끼리 orthogonal하고 length가 1이므로, standard basis는 orthonormal set입니다.
example
u 1 = [ 3 11 1 11 1 11 ] , u 2 = [ − 1 6 2 6 1 6 ] , u 3 = [ − 1 66 − 2 66 7 66 ] , \boldsymbol{u_1} = \begin{bmatrix}\frac{3}{\sqrt {11}} \\ \frac{1}{\sqrt{11}} \\ \frac{1}{\sqrt{11}} \end{bmatrix}, \boldsymbol{u_2} = \begin{bmatrix}-\frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt6} \end{bmatrix}, \boldsymbol{u_3}=\begin{bmatrix}-\frac{1}{\sqrt{66}} \\ -\frac{2}{\sqrt{66}} \\ \frac{7}{\sqrt{66}} \end{bmatrix}, u 1 = ⎣ ⎢ ⎢ ⎡ 1 1 3 1 1 1 1 1 1 ⎦ ⎥ ⎥ ⎤ , u 2 = ⎣ ⎢ ⎢ ⎡ − 6 1 6 2 6 1 ⎦ ⎥ ⎥ ⎤ , u 3 = ⎣ ⎢ ⎢ ⎡ − 6 6 1 − 6 6 2 6 6 7 ⎦ ⎥ ⎥ ⎤ , 위의 예시에서 length를 1로 normalizing시킨 u 1 , u 2 , u 3 \boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3} u 1 , u 2 , u 3
{ u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 } 는 orthonormal set입니다.
Theorem
An m × n m\times n m × n U U U U T U = I U^TU=I U T U = I
U T U = I U^TU=I U T U = I U U U n × n n\times n n × n
가 성립되기 때문에, U T = U − 1 U^T = U^{-1} U T = U − 1
Theorem
Let U U U m × n m\times n m × n x , y \boldsymbol{x}, \boldsymbol{y} x , y R n \mathbb R^n R n
∥ U x ∥ = ∥ x ∥ \|U\boldsymbol{x}\|=\|\boldsymbol{x}\| ∥ U x ∥ = ∥ x ∥ ( U x ) ⋅ ( U y ) = x ⋅ y (U\boldsymbol{x})\cdot(U\boldsymbol{y})=\boldsymbol{x}\cdot\boldsymbol{y} ( U x ) ⋅ ( U y ) = x ⋅ y ( U x ) ⋅ ( U y ) = 0 (U\boldsymbol{x})\cdot(U\boldsymbol{y})=0 ( U x ) ⋅ ( U y ) = 0 x ⋅ y = 0 \boldsymbol{x}\cdot\boldsymbol{y}=0 x ⋅ y = 0
U U U T U T_U T U T U T_U T U
Orthonormal 개념을 n × n n\times n n × n
Definition : Orthogonal matrix
An orthogonal matrix is a square matrix U U U U − 1 = U T U^{-1}=U^T U − 1 = U T
Such a matrix has orthonormal columns
U U T = U T U = I UU^T = U^TU = I U U T = U T U = I U U U U T U^T U T
Theorem
An orthogonal matrix have orthonormal rows
orthogonal matrix는 orthogonal한 column을 가지고 있습니다. 그리고 inverse가 해당 matrix의 transpose인 것을 생각하면, 해당 matrix는 orthonormal한 row를 가지고 있는 것을 알 수 있습니다.(자세한 증명은 appendix 참고)
example
u 1 = [ 3 11 1 11 1 11 ] , u 2 = [ − 1 6 2 6 1 6 ] , u 3 = [ − 1 66 − 2 66 7 66 ] , \boldsymbol{u_1} = \begin{bmatrix}\frac{3}{\sqrt {11}} \\ \frac{1}{\sqrt{11}} \\ \frac{1}{\sqrt{11}} \end{bmatrix}, \boldsymbol{u_2} = \begin{bmatrix}-\frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt6} \end{bmatrix}, \boldsymbol{u_3}=\begin{bmatrix}-\frac{1}{\sqrt{66}} \\ -\frac{2}{\sqrt{66}} \\ \frac{7}{\sqrt{66}} \end{bmatrix}, u 1 = ⎣ ⎢ ⎢ ⎡ 1 1 3 1 1 1 1 1 1 ⎦ ⎥ ⎥ ⎤ , u 2 = ⎣ ⎢ ⎢ ⎡ − 6 1 6 2 6 1 ⎦ ⎥ ⎥ ⎤ , u 3 = ⎣ ⎢ ⎢ ⎡ − 6 6 1 − 6 6 2 6 6 7 ⎦ ⎥ ⎥ ⎤ , 다음 vector로 이루어진 set { u 1 , u 2 , u 3 } \{\boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3}\} { u 1 , u 2 , u 3 } u 1 , u 2 , u 3 \boldsymbol{u_1}, \boldsymbol{u_2}, \boldsymbol{u_3} u 1 , u 2 , u 3
U = [ u 1 u 2 u 3 ] U = \begin{bmatrix} \boldsymbol{u_1} & \boldsymbol{u_2} & \boldsymbol{u_3} \end{bmatrix} U = [ u 1 u 2 u 3 ] 은 orthogonal matrix입니다. 즉
U T U = U U T = I U^TU = UU^T = I U T U = U U T = I 를 만족합니다.
지금까지 orthogonal set에 대해 알아보았습니다. 다음 포스트에서는 orthogonal projection에 대해서 알아보겠습니다. 질문이나 오류 있으면 댓글 남겨주세요! 감사합니다!
Appendix : Proof of theorem
Theorem
If S = { u 1 , . . . , u p } S=\{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} S = { u 1 , . . . , u p } R n \mathbb R^n R n S S S S S S
S S S
c 1 u 1 + ⋯ c p u p = 0 c_1\boldsymbol{u_1} + \cdots c_p\boldsymbol{u_p}=0 c 1 u 1 + ⋯ c p u p = 0 을 생각해봅시다. 양변에 u j \boldsymbol{u_j} u j
c j u j ⋅ u j = 0 ⟺ c j ∥ u j ∥ 2 = 0 c_j\boldsymbol{u_j} \cdot \boldsymbol{u_j} = 0 \iff c_j\|\boldsymbol u_j\|^2 =0 c j u j ⋅ u j = 0 ⟺ c j ∥ u j ∥ 2 = 0 임을 알 수 있습니다. u j \boldsymbol{u_j} u j
임을 뜻합니다. 따라서 j = 1 , . . . , p j=1,...,p j = 1 , . . . , p c j = 0 c_j=0 c j = 0
c 1 u 1 + ⋯ c p u p = 0 c_1\boldsymbol{u_1} + \cdots c_p\boldsymbol{u_p}=0 c 1 u 1 + ⋯ c p u p = 0 은 trivial solution을 가집니다. 즉 S S S
Theorem
Let { u 1 , . . . , u p } \{\boldsymbol{u_1}, ..., \boldsymbol{u_p}\} { u 1 , . . . , u p } W W W R n \mathbb R^n R n y \boldsymbol{y} y W W W
y = c 1 u 1 + ⋯ + c p u p \boldsymbol{y}=c_1\boldsymbol{u_1}+\cdots + c_p\boldsymbol{u_p} y = c 1 u 1 + ⋯ + c p u p and
c j = u j ⋅ y u j ⋅ u j , j = 1 , . . . , p c_j = \frac{\boldsymbol{u_j}\cdot \boldsymbol{y}}{\boldsymbol{u_j}\cdot\boldsymbol{u_j}}, \ \ \ j=1, ..., p c j = u j ⋅ u j u j ⋅ y , j = 1 , . . . , p y = c 1 u 1 + ⋯ + c p u p \boldsymbol{y}=c_1\boldsymbol{u_1}+\cdots + c_p\boldsymbol{u_p} y = c 1 u 1 + ⋯ + c p u p 의 양변에 u j \boldsymbol{u_j} u j
u j ⋅ y = c j u j ⋅ u j \boldsymbol{u_j}\cdot \boldsymbol{y} = c_j\boldsymbol{u_j}\cdot \boldsymbol{u_j} u j ⋅ y = c j u j ⋅ u j 이 됩니다. basis의 원소 u j \boldsymbol{u_j} u j u j ≠ 0 \boldsymbol{u_j}\neq0 u j = 0
c j = u j ⋅ y u j ⋅ u j c_j=\frac{\boldsymbol{u_j}\cdot \boldsymbol y}{\boldsymbol{u_j} \cdot \boldsymbol{u_j}} c j = u j ⋅ u j u j ⋅ y 가 됩니다.
Theorem
An m × n m\times n m × n U U U U T U = I U^TU=I U T U = I
U = [ u 1 ⋯ u n ] U = \begin{bmatrix}\boldsymbol{u_1} & \cdots & \boldsymbol{u_n} \end{bmatrix} U = [ u 1 ⋯ u n ] 일 때,
U T = [ u 1 T ⋮ u n T ] U^T = \begin{bmatrix}\boldsymbol{u_1}^T \\ \vdots \\ \boldsymbol{u_n}^T \end{bmatrix} U T = ⎣ ⎢ ⎢ ⎡ u 1 T ⋮ u n T ⎦ ⎥ ⎥ ⎤ 입니다. 두 matrix를 곱하면
U T U = [ u 1 T ⋮ u n T ] [ u 1 ⋯ u n ] U^TU = \begin{bmatrix}\boldsymbol{u_1}^T \\ \vdots \\ \boldsymbol{u_n}^T \end{bmatrix} \begin{bmatrix}\boldsymbol{u_1} & \cdots & \boldsymbol{u_n} \end{bmatrix} U T U = ⎣ ⎢ ⎢ ⎡ u 1 T ⋮ u n T ⎦ ⎥ ⎥ ⎤ [ u 1 ⋯ u n ] 가 되는데 이 때, U T U U^TU U T U
( U T U ) i i = u i T u i = u i ⋅ u i = 1 ( U T U ) i j = u i T u j = u j ⋅ u i = 0 (U^TU)_{ii} = \boldsymbol{u_i}^T\boldsymbol{u_i} = \boldsymbol{u_i}\cdot \boldsymbol{u_i} = 1 \\ (U^TU)_{ij} = \boldsymbol{u_i}^T\boldsymbol{u_j} = \boldsymbol{u_j}\cdot \boldsymbol{u_i} = 0 ( U T U ) i i = u i T u i = u i ⋅ u i = 1 ( U T U ) i j = u i T u j = u j ⋅ u i = 0 가 됩니다. 이는 U U U
가 됩니다.
반대로, U T U = I U^T U=I U T U = I
( U T U ) i i = u i T u i = u i ⋅ u i = 1 ( U T U ) i j = u i T u j = u j ⋅ u i = 0 (U^TU)_{ii} = \boldsymbol{u_i}^T\boldsymbol{u_i} = \boldsymbol{u_i}\cdot \boldsymbol{u_i} = 1 \\ (U^TU)_{ij} = \boldsymbol{u_i}^T\boldsymbol{u_j} = \boldsymbol{u_j}\cdot \boldsymbol{u_i} = 0 ( U T U ) i i = u i T u i = u i ⋅ u i = 1 ( U T U ) i j = u i T u j = u j ⋅ u i = 0 가 성립하기 때문에, U U U
Theorem
Let U U U m × n m\times n m × n x , y \boldsymbol{x}, \boldsymbol{y} x , y R n \mathbb R^n R n
∥ U x ∥ = ∥ x ∥ \|U\boldsymbol{x}\|=\|\boldsymbol{x}\| ∥ U x ∥ = ∥ x ∥ ( U x ) ⋅ ( U y ) = x ⋅ y (U\boldsymbol{x})\cdot(U\boldsymbol{y})=\boldsymbol{x}\cdot\boldsymbol{y} ( U x ) ⋅ ( U y ) = x ⋅ y ( U x ) ⋅ ( U y ) = 0 (U\boldsymbol{x})\cdot(U\boldsymbol{y})=0 ( U x ) ⋅ ( U y ) = 0 x ⋅ y = 0 \boldsymbol{x}\cdot\boldsymbol{y}=0 x ⋅ y = 0
Proof of 1
U U U
를 만족합니다. 따라서
∥ U x ∥ 2 = ( U x ) T ( U x ) = x T U T U x = x T x = ∥ x ∥ 2 \|U\boldsymbol{x}\|^2 = (U\boldsymbol x)^T (U\boldsymbol x) = \boldsymbol x^T U^TU\boldsymbol x = \boldsymbol{x}^T\boldsymbol{x} = \|\boldsymbol{x}\|^2 ∥ U x ∥ 2 = ( U x ) T ( U x ) = x T U T U x = x T x = ∥ x ∥ 2 을 만족합니다.
Proof of 2
마찬가지로
( U x ) ⋅ ( U y ) = y T U T U x = y T x = x ⋅ y (U\boldsymbol{x})\cdot(U\boldsymbol{y}) = \boldsymbol{y}^TU^TU\boldsymbol x = \boldsymbol y^T \boldsymbol x = \boldsymbol x \cdot \boldsymbol y ( U x ) ⋅ ( U y ) = y T U T U x = y T x = x ⋅ y 를 만족합니다.
Proof of 3
2번에서
( U x ) ⋅ ( U y ) = x ⋅ y (U\boldsymbol{x})\cdot(U\boldsymbol{y})=\boldsymbol{x}\cdot\boldsymbol{y} ( U x ) ⋅ ( U y ) = x ⋅ y 이므로,
( U x ) ⋅ ( U y ) = 0 (U\boldsymbol{x})\cdot(U\boldsymbol{y})=0 ( U x ) ⋅ ( U y ) = 0 인 것과 동치는
x ⋅ y = 0 \boldsymbol{x}\cdot\boldsymbol{y}=0 x ⋅ y = 0 과 같습니다.
Theorem
An orthogonal matrix have orthonormal rows
Orthogonal matrix U U U
U T U = U U T = I U^TU=UU^T=I U T U = U U T = I 를 만족합니다. 여기서 V = U T V=U^T V = U T
V V T = V T V = I VV^T=V^TV = I V V T = V T V = I 를 만족합니다. 즉 V V V V V V U U U U U U
