조르당 분해
1. 개요
조르당 분해(Jordan decomposition)는 복소수 범위에서는 항상 모든 행렬을 다음의 조르당 블록(Jordan Block)이라 불리는 행렬들의 블록 대각 행렬(block diagonal matrix)들과 상사로 나타낼 수 있다는 내용이다.
$$J= \left(\begin{array}{cccccc}\lambda & 1 & & & & \mathbf{0} \\ & \lambda & 1 & & & \\ & & \lambda & \ddots & & \\ & & & \ddots & 1 & \\ & & & & \lambda & 1\\ \mathbf{0} & & & & & \lambda\end{array}\right)$$ 또는 $$ \ J= \left(\begin{array}{cccccc}\lambda & & & & & \mathbf{0} \\1 & \lambda & & & & \\ & 1 & \lambda & & & \\ & & \ddots & \ddots & & \\ & & & 1 & \lambda & \\ \mathbf{0} & & & & 1& \lambda\end{array}\right)$$
비어 있는 곳은 모두 0이다. 상삼각/하삼각행렬 두 형태는 서로 상사이므로 뭘 쓰는지는 상관없지만 하나로 통일하는 것이 보통이다. 이 문서에서는 첫 번째 형태, 즉 상삼각 형태를 사용하도록 한다.이러한 형태를 조르당 형식(Jordan form)이라 하며, 각각의 조르당 블록은 (순서를 무시하면) 유일하게 결정된다. 대각화 불가능한 행렬들도 나타낼 수 있을 뿐만 아니라, 복소수 범위 내에서 상사인 행렬들을 완벽하게 분류해 줄 수 있다는 의의가 있다. 조르당 블록의 크기는 1*1도 가능하기 때문에, 행렬의 대각화도 조르당 분해의 일종이다.
순수수학적으로 엄밀하게 보면 일반적인 스칼라 체 $$F$$ 위에서의 행렬을 생각할 때, 행렬의 최소다항식이 스칼라 체 $$F$$ 에서 일차식으로 완벽히 분해될 때만 조르당 분해가 존재한다. 대신에 $$F$$가 대수적으로 닫혀있지 않을 때는 Frobenius normal form 혹은 rational canonical form이라 불리는 형식을 생각할 수 있다. 물론 상황은 비슷해서, 대수적으로 닫힌 체 위에서는 조르당 블록의 구성으로 행렬의 상사를 완벽하게 분류할 수 있다.
아래에서 조르당 분해에 접근하는 다양한 관점을 서술한다.
2. 일반화된 고유값과 고유벡터로 이해
순수수학 계열이 아닌 많은 선형대수학 교재에는 조르당 분해가 '''일반화된 고유벡터'''(generalized eigenvector)의 개념으로 설명된다. 일반적인 고유벡터가 $$(T- \lambda I) v =0$$을 만족하는 $$v$$였다면, 일반화된 고유벡터는 어떤 정수 $$k$$에 대해 $$(T- \lambda I)^k v =0$$을 만족하는 벡터를 말한다. 보통 고유벡터는 $$T- \lambda I$$를 한번만 적용해도 0이 되지만, 일반화된 고유벡터는 여러 번 적용이 필요한 것이다. 이 때 적용이 필요한 최소의 $$k$$, 즉 $$(T- \lambda I)^k v =0$$인 최소의 $$k$$를 $$v$$의 '''차수'''라 한다.
일반화된 고유벡터 $$v$$의 차수가 k일 때, 리스트 $$\{v, (T- \lambda I)v, (T- \lambda I)^2 v, \cdots, (T- \lambda I)^{k-1}v \}$$을 '''조르당 사슬'''(Jordan chain)이라 부른다. 이 때 $$v_i = (T- \lambda I)^i v$$라 했을 때 항등식 $$ Tv_i = \lambda v_i + v_{i+1} $$ 을 생각하면, '''조르당 사슬에 대한 $$T$$의 행렬은 조르당 블록이 된다'''는 사실을 알 수 있다. 즉 조르당 분해는 '''조르당 사슬만으로 이루어진 전체 공간의 기저를 찾을 수 있을까?''' 하는 문제가 된다.
따라서 이러한 접근에서, 조르당 분해의 구성 증명은 귀납법을 사용하게 된다. 조르당 사슬의 가장 끝 원소는 항상 $$(T- \lambda I)v = 0$$을 만족시키는 일반 고유벡터이다. 따라서 특정 고유벡터를 하나 잡고, 이를 포함하는 최대의 조르당 사슬을 생각하고, 그 조르당 사슬이 생성하는 공간과 직합을 이루는 invariant subspace를 찾으면 되는 것이다. 보통 이는 $$(T- \lambda I)$$의 null space(혹은 kernel)와 column space(혹은 image) 이 둘을 적절히 기술적으로 활용하는 과정이 된다.
이 증명 자체는 보통 귀찮다고 여겨지는 부분이 많고, 실제로 본질적이라고 보기는 힘들다. 대신에 이 증명에서 중요한 것은 $$(T-\lambda I)^k$$의 계수(rank)들로 조르당 분해를 결정지을 수 있다는 결과가 된다. 정확히 말하면 $$(T-\lambda I)^k$$의 nullity(kernel의 차원)을 $$n_k$$라 하면, 크기 $$k$$인 조르당 블록의 개수는 $$n_{k+1} - n_{k}$$가 된다.
2.1. 조르당 분해 계산하기
이 성질을 활용하여 다음처럼 조르당 분해를 계산할 수 있다. 행렬 혹은 선형사상의 영공간을 $$N(A)$$, 영공간의 차원을 $$n(A)$$라 쓰자.
1. 우선 $$T$$의 특성다항식을 완전히 인수분해한다.
2. 각각의 고유값 $$\lambda$$에 대해 다음 과정을 반복하여, 조르당 사슬로 이루어진 $$N((T-\lambda I)^e)$$의 기저 $$\mathscr{B}$$를 잡는다. ($$e$$는 특성다항식에서 $$\lambda$$의 중복도)
2-1. $$S=T-\lambda I$$라 놓고, $$N(S),N(S^2), N(S^3), \cdots,$$를 계산한다. $$n(S^k)=e$$가 될 때 멈추고, 이 때의 $$k$$값을 $$l$$이라 하자.
2-2. $$\mathscr{B}=\phi$$, $$i=l$$로 시작해 i를 1씩 감소시키며 다음의 과정을 반복한다.
2-3. 최종적으로 얻은 $$\mathscr{B}$$가 조르당 사슬로 이루어진 $$N((T-\lambda I)^e)$$의 기저가 된다. $$\mathscr{C_i}$$의 각각의 원소로 시작하는 사슬은 크기 $$i$$의 조르당 블록의 기저로 대응이 된다.
3. 각각의 고유값에서 얻은 기저를 모두 모은다. 이 기저에 대해 $$T$$는 조르당 형식으로 나타난다.2-2. $$\mathscr{B}=\phi$$, $$i=l$$로 시작해 i를 1씩 감소시키며 다음의 과정을 반복한다.
2-2-1. $$ N(S^{i-1})$$의 기저 $$\mathscr{A}_{i-1}$$와 $$ (N(S^i) \setminus N(S^{i-1}) ) \cap \mathscr{B} = \mathscr{B}_{i}$$을 구한다.
2-2-2. $$\mathscr{A}_{i-1} \cup \mathscr{B}_{i} $$를 포함하는 $$ N(S^i) $$의 기저를 생각하고, 이 때 추가된 원소들의 집합을 $$\mathscr{C_i}$$라 하자. 제대로 했다면 $$\mathscr{C_i}$$의 원소의 개수는 $$n_{i+1} - n_{i}$$가 되어야 한다.
2-2-3. $$\mathscr{C_i}$$의 각각의 원소 $$v$$에 대해, $$v$$로 시작된 사슬 $$v,Sv,S^2 v, \cdots, S^{i-1} v$$를 모두 $$\mathscr{B}$$에 추가한다.
2-2-4. i를 1 감소시킨다.
2-2-2. $$\mathscr{A}_{i-1} \cup \mathscr{B}_{i} $$를 포함하는 $$ N(S^i) $$의 기저를 생각하고, 이 때 추가된 원소들의 집합을 $$\mathscr{C_i}$$라 하자. 제대로 했다면 $$\mathscr{C_i}$$의 원소의 개수는 $$n_{i+1} - n_{i}$$가 되어야 한다.
2-2-3. $$\mathscr{C_i}$$의 각각의 원소 $$v$$에 대해, $$v$$로 시작된 사슬 $$v,Sv,S^2 v, \cdots, S^{i-1} v$$를 모두 $$\mathscr{B}$$에 추가한다.
2-2-4. i를 1 감소시킨다.
2-3. 최종적으로 얻은 $$\mathscr{B}$$가 조르당 사슬로 이루어진 $$N((T-\lambda I)^e)$$의 기저가 된다. $$\mathscr{C_i}$$의 각각의 원소로 시작하는 사슬은 크기 $$i$$의 조르당 블록의 기저로 대응이 된다.
물론 조르당 형식만이 필요하다면 기저를 얻을 필요는 없고, $$n(T-\lambda I)^k$$들만 알아도 된다.
이해를 돕기 위한 바보같은(...) 예시를 하나 들면
$$T= \left(\begin{array}{cccc}1 & 1 & 0 & 0 \\0 & 1 & 0 & 0\\0 &0&1&0\\0&0&0&2 \end{array}\right) $$
1. $$p(\lambda) = (\lambda-1)^3 (\lambda-2)$$.
2-1. $$\lambda = 1$$에 대해서 $$S= \left(\begin{array}{cccc}0 & 1 & 0 & 0 \\0 & 0 & 0 & 0\\0 &0&0&0\\0&0&0&1 \end{array}\right) $$이고, $$n(S)=2, n(S^2)=3$$이다. $$e=3$$이었으므로 여기서 멈추고, $$l=2$$.
2-2. $$i=2$$부터 시작한다.
2-3. $$\mathscr{B}=\{e_1,e_2,e_3\}$$이 $$N((T-I)^3)$$의 원하는 기저이다.
2-2. $$i=2$$부터 시작한다.
2-2-1. $$i=2$$일 때: $$N(S)$$의 기저 $$ e_2, e_3$$에 아직 공집합인 $$\mathscr{B}_{i}$$를 더한다. 여기에 $$e_1$$을 추가해야 $$N(S^2)$$가 되므로, $$\mathscr{C_2}= \{e_1\}$$. $$e_1$$으로 생성되는 사슬 $$e_1, e_2$$를 $$\mathscr{B}$$에 추가한다.
2-2-1. $$i=1$$일 때: $$N(S^0)$$은 $$N(I)=\{0\}$$으로 간주한다. $$\mathscr{B}_{1}= \{e_1\}$$이 되므로, 여기에 $$e_3$$을 추가해야 $$N(S)$$가 되므로 $$\mathscr{C_1}= \{e_3\}$$. $$e_3$$으로 생성되는 사슬 $$e_3$$을 $$\mathscr{B}$$에 추가하고, 여기서 종료.
2-2-1. $$i=1$$일 때: $$N(S^0)$$은 $$N(I)=\{0\}$$으로 간주한다. $$\mathscr{B}_{1}= \{e_1\}$$이 되므로, 여기에 $$e_3$$을 추가해야 $$N(S)$$가 되므로 $$\mathscr{C_1}= \{e_3\}$$. $$e_3$$으로 생성되는 사슬 $$e_3$$을 $$\mathscr{B}$$에 추가하고, 여기서 종료.
2-3. $$\mathscr{B}=\{e_1,e_2,e_3\}$$이 $$N((T-I)^3)$$의 원하는 기저이다.
2-1. $$\lambda=2$$에 대해서 $$n(S)=1$$이고, $$e=1$$이었으므로 $$l=1$$.
2-2. $$i=1$$에 대해서만 적용하여도 된다. $$N(S)$$의 기저 $$e_4$$가 $$\mathscr{B}$$에 추가되고 끝난다.
2-3. $$\mathscr{B}=\{e_4\}$$이 $$N(T-2I)$$의 원하는 기저이다.
3. 2-3에서 얻어진 $$\mathscr{B}$$들을 모두 모은 $$\{e_1,e_2,e_3,e_4\}$$가 조르당 사슬로 이루어진 기저이며, 이 기저에 대해 $$T$$는 조르당 폼으로 나타난다. 2-2. $$i=1$$에 대해서만 적용하여도 된다. $$N(S)$$의 기저 $$e_4$$가 $$\mathscr{B}$$에 추가되고 끝난다.
2-3. $$\mathscr{B}=\{e_4\}$$이 $$N(T-2I)$$의 원하는 기저이다.
일반적인 경우를 손으로 계산해 보면 상당히 귀찮으므로, 대학교 과제/시험 정도를 제외하면 주로 컴퓨터의 도움을 많이 받게 될 것이다. 상용 프로그램이 없으면 울프람알파에서 'Jordan normal form calculator'를 검색해 이용하자.
위 방법을 따라가 조르당 분해의 존재성을 증명하는 것도 가능하긴 하지만, 다만 $$N((T-\lambda I)^e)$$의 기저들을 모두 모았을 때 전체 공간의 기저가 된다는 사실은 따로 증명해야 한다.
3. 추상대수학을 이용한 이해
PID 위의 유한생성 가군의 기본정리를 통해 이해할 수 있다.[1]
이 간결한 사고방식은 우선 $$F$$-벡터 공간 $$V$$를 $$F\left[x\right]$$-가군으로 이해하는 것에서 시작한다. 선형변환 $$T$$가 주어져 있을 때 작용 $$F\left[x\right]\rightarrow Hom(V,V)$$을 $$x\mapsto T$$로 부여하는 것이다. 그리고 $$V$$에 PID 위의 유한생성 가군의 기본정리를 적용하는 것이다.
$$T$$의 최소다항식이 존재하므로 $$V$$는 torsion module이므로, PID 위의 유한생성 가군의 기본정리의 elementary divisor decomposition을 생각하면
$$ V \cong \bigoplus F\left[x\right]/(p_i(x))^{r_i} $$
의 형태로 쓸 수 있다. 기약다항식 $$p_i(x)$$들은 모두 최소다항식의 약수이고, 따라서 만약 $$T$$의 최소다항식이 일차식들로 분해가 된다면 $$p_i(x)$$들도 일차식이어야 한다. $$p_i(x)=x-c_i$$라 놓자.
이제 여기서 포인트는 '''조르당 블록은 사실 $$x$$가 $$F[x]/(x-c)^r$$에 작용할 때의 행렬이라는 것이다.''' 더 정확히 말하면 기저 $$\{1, (x-c), \cdots, (x-c)^{r-1} \}$$를 잡았을 때 $$ x \cdot (x-c)^k = c(x-c)^k + (x-c)^{k+1} $$ 을 관찰하면, $$F[x]/(x-c)^r$$ 위에서 $$x$$의 곱셈을 위 기저에 대한 행렬로 나타내면 조르당 블록이 됨을 알 수 있다. 이들의 직합이 전체공간이므로 조르당 분해가 바로 따라나오고, 한편 $$(c_i, r_i)$$들의 순서쌍이 유일하게 결정되므로 조르당 분해도 유일함을 알 수 있는 것.
한편 PID 위의 유한생성 가군의 기본정리에서 대신 Invariant factor들을 생각한다면,
$$V \cong \bigoplus \left(F\left[x\right]/\left(a_{i}\right)\right), \quad a_{i}\mid a_{i+1}$$
로 나타낼 수 있다. 다항식 $$a(x) = x^{n}+\sum b_{i}x^{i}$$에 대해서, $$F[x]/(a(x))$$ 위에서 $$x$$의 작용은 기저 $$\{1, x, x^2, \cdots, x^{n-1} \}$$에 대해, 동반행렬(companion matrix)이라 불리는 다음의 행렬
$$C_{a(x)} =\left(\begin{array}{cccccc}0 & & & & & -b_{0}\\1 & 0 & & & & -b_{1}\\ & 1 & 0 & & & -b_{2}\\ & & & \ddots & & \vdots\\ & & & 1 & 0 & -b_{n-2}\\ & & & & 1 & -b_{n-1}\end{array}\right)$$
으로 나타난다. ($$x\cdot x^{n-1} \equiv -{\displaystyle \sum_{j<n}}b_{j}x^{j}(\text{mod } a(x))$$ 을 생각하면 알 수 있다.) 이들 동반행렬의 블록으로 전체 행렬을 나타낸 것을 Frobenius canonical form이라 부른다. 이는 $$T$$의 최소다항식 분해 여부에 전혀 상관이 없이 모든 상황에서 적용될 수 있다.
3.1. 제1분해정리, 제2분해정리
일부 서술 방법에서는 $$T$$의 최소다항식의 인자들을 생각하고, 이들로 먼저 분해하는 방법을 사용하기도 한다.
먼저 $$T$$의 최소 다항식, $$p$$와 그것의 소인수분해 $$p=\prod p_{i}^{r_{i}}$$를 생각하자. $$W_{i}:=\ker p_{i}^{r_{i}}\left(T\right)$$라 하면, 다음이 성립하고, 첫 번째 분해방식을 제1분해(primary decomposition)이라 부르는 것이다.
이 primary decomposition의 증명에서는 $$T$$의 특성 다항식의 인자들도 $$p_{i}$$가 되어야 한다는 것이 따라나오고, 따라서 특성 다항식에 대해서도 같은 작업을 할 수 있다.* $$V={\displaystyle \bigoplus_{i}}W_{i}$$
* $$\left.T\right|_{W_{i}}$$의 최소 다항식은 $$p_{i}^{r_{i}}$$이다.
최소다항식이 $$p_{i}^{r_{i}}$$인 공간(위의 $$W_{i}$$)들을 invariant subspace들로 완벽히 분해하는 것을 제2분해정리(cyclic decomposition)이라 부른다. 정확히 말하면 최소다항식과 특성다항식이 $$p_{i}^{r'_{ij}}$$로 동일한 invariant subspace들을 cyclic subspace (일종의 'irreducible' invariant subspace로 생각할 수 있다)라 부르고, 이들의 직합으로 전체공간을 유일하게 나타낼 수 있다는 것이 제2분해정리이다.
제1분해정리는 베주 항등식 성질만을 이용해 비교적 초등적으로 증명할 수 있지만, 제2분해정리는 PID 위의 가군정리를 이용하거나 이에 준하는 상당한 노동이 필요하다. 둘의 증명을 이러한 식으로 나누어 놓는 서술도 많은 편인데, 조르당 분해의 증명에서거나 아니면 원본인 PID 위의 가군정리나 '''사실상 제2분해정리가 핵심적인 부분이기 때문.'''
4. 활용
상사인 행렬을 완벽히 분류하는 것 외에도, 조르당 분해는 행렬의 계산을 쉽게 하고 싶을 때 사용된다. 대표적으로 행렬의 n제곱을 구하거나 행렬 지수를 계산할 때. 크기 $$k$$인 조르당 블록의 n제곱과 지수 계산은 다음과 같이 비교적 간단히 계산된다.
$$ J^n = \left(\begin{array}{cccccc} \lambda^n & \binom{n}{1} \lambda^{n-1} &\binom{n}{2} \lambda^{n-2} & \cdots & \cdots & \binom{n}{k-1} \lambda^{n-k+1} \\ & \lambda^n & \binom{n}{1}\lambda^{n-1} & \cdots &\cdots & \binom{n}{k-2} \lambda^{n-k+2} \\ & & \lambda^n & \cdots & \cdots & \binom{n}{k-3} \lambda^{n-k+3} \\ & & & \ddots & & \vdots \\ & & & & \lambda^n & \binom{n}{1} \lambda^{n-1} \\ & & & & & \lambda^n \end{array}\right) $$, $$ e^{tJ} = e^{t\lambda} \left(\begin{array}{cccccc} 1 & \frac{t}{1!} & \frac{t^2}{2!} & \cdots & \cdots & \frac{t^{k-1}}{(k-1)!} \\ & 1 & \frac{t}{1!} & \cdots &\cdots & \frac{t^{k-2}}{(k-2)!} \\ & & 1 & \cdots & \cdots & \frac{t^{k-3}}{(k-3)!} \\ & & & \ddots & & \vdots \\ & & & & 1 & \frac{t}{1!} \\ & & & & & 1 \end{array} \right) $$
따라서 어떤 행렬의 n제곱이나 행렬지수를 쉽게 계산하고 싶을 때, 조르당 형식으로 변환하여 $$A^n = S J^n S^{-1}$$, $$e^{tA}=S e^{tJ}S^{-1}$$로 계산하는 방법이 쓰인다. 선형미분방정식이나 점화식에 이들이 등장하는 만큼 다양하게 쓰일 수 있다.
다만 실제로는 조르당 분해 자체가 Numerically Unstable하기 때문에 대다수의 수치 선형대수 프로그래밍에서 다루지 않는 경우가 많다. 참고
애초에 Eigenvalue부터 정확한 값을 구해야 하는데, 그러려면 Characteristic Polynomial을 정수나 유리수 형태의 정확한 숫자로 푸는 알고리즘을 적용하는 방법밖에 없고, 알다시피 5차 방정식 이상의 해법은 없기 때문에 아주 특이한 경우를 제외하고는 조르당 분해에 필요한 정확도의 Eigenvalue를 구하는 방법 자체가 없다.
반대로 부동 소수점을 이용해 Eigenvalue를 근사하는 알고리즘의 경우, 큰 매트릭스에서도 적용이 가능하지만, 두 eigenvalue가 같은지 다른지 판별할 기준이 명확하지 않게 된다.