Schur / Real Schur Decomposition

Schur Decomposition

(Complex) Schur Decomposition 은 정사각행렬 A \in \mathbb{C}^{n\times n} 를 unitary 행렬 U \in \mathbb{C}^{n\times n} 와 상삼각행렬 T \in \mathbb{C}^{n\times n} 로 분해하는 방법이다. 즉, A = UTU^H 로 분해된다. 이것은 Hermitian 행렬의 고유값 분해 A = U\Lambda U^H 의 일반화된 형태다. 즉, A 가 실수 대칭행렬이거나 복소수 Hermitian 행렬이라면 T 는 대각행렬 \Lambda 가 된다.

행렬 A \in \mathbb{C}^{n\times n} 는 대각화 가능 여부와는 별도로 하나의 고유값 \lambda_{1(A)} 와 그 고유벡터 \mathbf{x}_{1(A)} 를 가진다. 그러면 \mathbf{x}_{1(A)} 를 이용해서 임의의 unitary 행렬 Q_1 을 아래와 같이 구성할 수 있다.

    \[Q_1 =  \begin{bmatrix} \\ \mathbf{x}_{1(A)} & \mathbf{w_2} & \mathbf{w_3} & \dots & \mathbf{w_n} \\ \\ \end{bmatrix}\]

Q_1 을 이용한 A 의 닮음 변환 Q_1^H A Q_1A 의 첫번째 열을 소거한다.

    \[\begin{aligned} Q_1^H A Q_1 &=  \begin{bmatrix} & \mathbf{x}_{1(A)}^H & \\  & \mathbf{w_2}^H & \\  & \mathbf{w_3}^H & \\  & \vdots & \\  & \mathbf{w_n}^H & \\ \end{bmatrix} \begin{bmatrix} \\ A\mathbf{x}_{1(A)} & A\mathbf{w_2} & A\mathbf{w_3} & \dots & A\mathbf{w}_n \\ \\ \end{bmatrix} \\  &= \begin{bmatrix} \lambda_A & \dots \\ 0 & \boxed{A_2}     \end{bmatrix} = T_1 \end{aligned}\]

A_2n-1 크기의 정사각행렬이다. A_2 역시 한개의 고유벡터 \lambda_{1(A_2)} 와 그 고유벡터 \mathbf{x}_{1(A_2)} 를 구해서 Q_2 를 만들 수 있을 것이다. 그럼 T_1 은 unitary 행렬인 \begin{bmatrix} I_{1\times 1} & 0 \\ 0 & Q_2     \end{bmatrix} 을 이용해서 두번째 열을 소거할 수 있다.

    \[\begin{bmatrix} I_{1\times 1} & 0 \\ 0 & Q_2     \end{bmatrix}^H \begin{bmatrix} \lambda_{1(A)} & \dots \\ 0 & \boxed{A_2}     \end{bmatrix} \begin{bmatrix} I_{1\times 1} & 0 \\ 0 & Q_2     \end{bmatrix} =  \begin{bmatrix} \lambda_{1(A)} & \dots \\ 0 & \begin{bmatrix}    \lambda_{1(A_2)} & \dots \\   0 & \boxed{A_3}   \end{bmatrix} \end{bmatrix} = T_2\]

한번 더 반복해보자.

    \[\begin{bmatrix} I_{2\times 2} & 0 \\ 0 & Q_3     \end{bmatrix}^H \begin{bmatrix} \lambda_{1(A)} & \dots \\ 0 & \begin{bmatrix}    \lambda_{1(A_2)} & \dots \\   0 & \boxed{A_3}   \end{bmatrix} \end{bmatrix} \begin{bmatrix} I_{2\times 2} & 0 \\ 0 & Q_3     \end{bmatrix} =  \begin{bmatrix} \lambda_{1(A)} & \dots \\ 0 & \begin{bmatrix}    \lambda_{1(A_2)} & \dots \\   0 & \begin{bmatrix}      \lambda_{1(A_3)} & \dots \\     0 & \boxed{A_4}     \end{bmatrix}   \end{bmatrix} \end{bmatrix} = T_3\]

이렇게 n-1 번 반복하면,

    \[\begin{aligned} U_0^H A U_0 &= T_1 \\ U_1^H T_1 U_1 &= T_2 \\ U_2^H T_2 U_2 &= T_3 \\ &\vdots \\ U_{n-2}^H T_{n-2} U_{n-2} &= T_{n-1} \end{aligned} \quad \begin{aligned} U_k = \begin{bmatrix} I_{k\times k} & 0 \\ 0 & Q_{k+1} \end{bmatrix} \end{aligned}\]

계속 열들이 소거되어 T_{n-1} 은 결국 상삼각행렬이 된다.

이제 A 를 표현하기 위해서 식을 이항하면,

    \[\begin{aligned} A &= U_0 T_1 U_0^H \\ T_1 &= U_1 T_2 U_1^H \\ T_2 &= U_2 T_3 U_2^H \\ &\vdots \\ T_{n-2} &= U_{n-2} T_{n-1} U_{n-2}^H \end{aligned}\]

식 전체를 A 로 나타내면

    \[\begin{aligned} A &= U_0 U_1 U_2 \dots U_{n-2} T_{n-1} U_{n-2}^H \dots U_2^H U_1^H U_0^H \\ &= (U_0 U_1 U_2 \dots U_{n-2}) T_{n-1} (U_0 U_1 U_2 \dots U_{n-2})^H \\ &= UTU^H \end{aligned}\]

unitary 행렬끼리의 곱은 역시 unitary 행렬이므로 A = UTU^H 형태로 분해가 된다는 것을 알 수 있다.

Real Schur Decomposition

Real Schur Decomposition 은 실수 행렬만으로 이뤄진 Schur Decomposition 이라고 보면 된다. 다만 T 의 모양이 상삼각행렬이 아닐 수 있다.

    \[A = QTQ^T,\quad T = \begin{bmatrix} T_{11} & T_{12} & \dots & T_{1m} \\ & T_{22} & \dots & T_{2m} \\ & & \ddots & \vdots \\ & & & T_{mm} \\ \end{bmatrix}\]

T_{ii} 의 크기는 1\times 1 일 수도, 2\times 2 일 수도 있다. 1\times 1 블럭은 실수 고유값이고, 2\times 2 블럭은 켤례쌍 (conjugate pair) 복소수 고유값을 가진다.

Conjugate Pair Lambda

A \in \mathbb{R}^{n\times n} 의 고유값 중 하나가 실수라면 대응되는 고유벡터 역시 실수 벡터다. 반대로 고유값이 복소수라면 대응되는 고유벡터 역시 복소수 벡터가 된다. 또 복소수 고유값을 가진다면 반드시 켤례복소수 고유값도 가진다.

정말 켤례 복소수 고유값을 가지는지 증명해보자. 고유값이 \lambda = \alpha + i\beta, \beta \neq 0 라면 대응되는 고유벡터는 \mathbf{x} = \mathbf{u} + i\mathbf{v} 형태다.

    \[\begin{aligned} A\mathbf{x} &= A (\mathbf{u} + i\mathbf{v}) = A\mathbf{u} + iA\mathbf{v} \\ \lambda \mathbf{x} &= (\alpha + i\beta) (\mathbf{u} + i\mathbf{v}) = (\underbrace{\alpha\mathbf{u} - \beta\mathbf{v}}_{A\mathbf{u}}) + i(\underbrace{\beta\mathbf{u} + \alpha\mathbf{v}}_{A\mathbf{v}}) \end{aligned}\]

즉,

(1)   \[\begin{aligned}  A\mathbf{u} &= \alpha\mathbf{u} - \beta\mathbf{v} \\ A\mathbf{v} &= \beta\mathbf{u} + \alpha\mathbf{v} \end{aligned}\]

이번엔 A\bar{\mathbf{x}} 를 구해보자.

    \[\begin{aligned} A\bar{\mathbf{x}} &= A (\mathbf{u} - i\mathbf{v}) = A\mathbf{u} - iA\mathbf{v} \\ &= (\alpha\mathbf{u} - \beta\mathbf{v}) - i(\beta\mathbf{u} + \alpha\mathbf{v}) \\ &= (\alpha - i\beta)\mathbf{u} - i(\alpha - i\beta)\mathbf{v} \\ &= (\alpha - i\beta)(\mathbf{u} - i\mathbf{v}) = \bar{\lambda}\bar{\mathbf{x}} \end{aligned}\]

A\bar{\mathbf{x}} = \bar{\lambda}\bar{\mathbf{x}} 이므로 \bar{\lambda} = \alpha - i\beta, \beta\neq 0 역시 고유값, \bar{\mathbf{x}} 는 대응되는 고유벡터다.

Conjugate Pair Matrix

이번에는 A 의 켤례쌍 고유값 \lambda = \alpha + i\beta, \bar{\lambda} = \alpha - i\beta 와 같은 고유값을 갖는 닮음행렬 S \in \mathbb{R}^{2\times 2} 을 정의해보자.

식 (1) 을 다시 쓰면,

(2)   \[A \begin{bmatrix} \mathbf{u} & \mathbf{v} \end{bmatrix} =  \begin{bmatrix} \mathbf{u} & \mathbf{v} \end{bmatrix} \begin{bmatrix} \alpha & \beta \\ -\beta & \alpha \end{bmatrix} \]

여기서 \mathbf{u}\mathbf{v} 는 선형독립이다. 만약 \mathbf{u}\mathbf{v} 가 선형종속이라면 그의 선형결합인 고유벡터 \mathbf{x}\bar{\mathbf{x}} 도 선형종속이 되고, 그러면 고유값 \lambda\bar{\lambda} 는 같아질 수 있으므로 \beta = 0 이 된다. 따라서 \mathbf{u}\mathbf{v} 는 선형독립이다.

\begin{bmatrix} \mathbf{u} & \mathbf{v} \end{bmatrix}QR 분해하면,

(3)   \[\begin{bmatrix}  \mathbf{u} & \mathbf{v}  \end{bmatrix} = \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} R \]

이제 식 (3) 을 식 (2) 에 대입하면,

    \[\begin{aligned} A \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2      \end{bmatrix} R &=  \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} R \begin{bmatrix} \alpha & \beta \\ -\beta & \alpha \end{bmatrix} \\ A \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2      \end{bmatrix} &=  \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} R \begin{bmatrix} \alpha & \beta \\ -\beta & \alpha \end{bmatrix} R^{-1} \\ &= \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} S \end{aligned}\]

S\begin{bmatrix} \alpha & \beta \\ -\beta & \alpha \end{bmatrix} 과 닮음 행렬이다.

    \[\begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix}^T  A \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} = S\]

Decomposition

Ak 개의 켤례쌍 고유값을 가진다면, 1번째 켤례쌍 고유값과 대응되는 켤례쌍 고유벡터로부터 아래의 직교 행렬을 만들 수 있다.

    \[Q_1 = \begin{bmatrix} \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} & \mathbf{w}_3 & \dots & \mathbf{w}_n     \end{bmatrix}\]

Q_1 을 이용한 A 의 닮음 변환 Q_1^T A Q 는 다음과 같이 좌상단 2\times 2 블럭 아래를 0 으로 만든다.

    \[\begin{aligned} Q_1^T A Q &= \begin{bmatrix}   \begin{bmatrix}   \mathbf{q}_1 & \mathbf{q}_2   \end{bmatrix}^T \\ \mathbf{w}_3^T \\ \vdots \\ \mathbf{w}_n^T      \end{bmatrix} \begin{bmatrix} A \begin{bmatrix} \mathbf{q}_1 & \mathbf{q}_2 \end{bmatrix} & A\mathbf{w}_3 & \dots & A\mathbf{w}_n  \end{bmatrix} \\ =& \begin{bmatrix} S_1 & \dots \\ 0 & \boxed{A_2} \end{bmatrix} = T_1 \end{aligned}\]

S_1A 의 1번째 켤례쌍 고유값을 갖는 \mathbb{R}^{2\times 2} 행렬이고, A_2(n-2)\times(n-2) 크기의 정사각행렬이다. A_2k-1 개의 켤례쌍 고유값을 가진다. 따라서 Q_2 를 만들 수 있을 것이다. 그럼 T_1 은 직교행렬 \begin{bmatrix} I_{2\times 2} & 0 \\ 0 & Q_2 \end{bmatrix} 를 이용해서 T_2 를 만들 수 있다.

    \[\begin{bmatrix}  I_{2\times 2} & 0 \\  0 & Q_2  \end{bmatrix}^T \begin{bmatrix} S_1 & \dots \\ 0 & \boxed{A_2} \end{bmatrix} \begin{bmatrix}  I_{2\times 2} & 0 \\  0 & Q_2  \end{bmatrix} =  \begin{bmatrix} S_1 & \dots \\ 0 &    \begin{bmatrix}   S_2 & \dots \\   0 & \boxed{A_3}   \end{bmatrix} \end{bmatrix} = T_2\]

만약 실수 고유값을 가진다면 Schur 분해에서 했던대로 좌상단 성분 아래를 0 으로 만든다. 결과적으로 A 는 다음과 같이 분해된다.

    \[A = QTQ^T,\quad T = \begin{bmatrix} T_{11} & T_{12} & \dots & T_{1m} \\ & T_{22} & \dots & T_{2m} \\ & & \ddots & \vdots \\ & & & T_{mm} \\ \end{bmatrix}\]

T_{ii} 는 실수 고유값이거나, 켤례 복소수 고유값을 갖는 2\times 2 행렬이다.

Leave a Reply

Your email address will not be published. Required fields are marked *