최소 다항식(Minimal Polynomial)

선형대수에서 최소 다항식(Minimal Polynomial)은 주어진 행렬 $A$ 또는 선형 변환 $T$을 소거하는 최소 차수의 단위계수(Monic) 다항식이다. 특성 다항식(Characterstic Polynomial)과 밀접한 관계가 있지만, 서로 다르다.

특성 다항식 (Characteristic Polynomial)

어떤 정사각 행렬 $A$의 특성 다항식은 다음과 같이 정의된다.

$$p_A(\lambda )=\det (A-\lambda I)$$

1. 항상 $n$차 다항식이다.
2. 행렬 $A$의 고유값(Eigenvalues)들이 근이 된다.
3. 모든 정사각 행렬에 대해 정의된다.

최소 다항식 (Minimal Polynomial)

정사각 행렬 $A$의 최소 다항식 $m_A(x)$는 다음을 만족하는 가장 낮은 차수의 단위계수 다항식이다.

$$m_A(A)=0$$

즉, $m_A(x)$는 $A$를 대입했을 때 영행렬이 되는 가장 차수가 낮은 다항식이다.

최소 다항식의 성질

1. $A$의 특성 다항식 $p_A(x)$의 약수

$$m_A(x)\mid p_A(x)$$

2. 단위계수 (Monic Polynomial)
   최소 다항식은 최고차항의 계수가 항상 $1$인 단위 다항식입니다.

3. 차수
   최소 다항식의 차수는 특성 다항식의 차수보다 작거나 같다.

$$\mathrm{deg}{m}_A(x)\le \mathrm{deg}{p}_A(x)$$

특히, 행렬이 대각화 가능할 경우 두 다항식의 차수가 같을 수 있다. 아래는 문제와 해답 아이디어를 한국어로 번역·정리한 내용입니다.

조르당 표준형의 최소다항식

유한 차원 벡터 공간 위의 선형 연산자 $T$의 특성 다항식이 일차식으로 완전히 분해된다고 하자. 서로 다른 고유값을 ${\lambda }_1,\dots ,{\lambda }_k$라 하고, 각 ${\lambda }_i$에 대응하는 조르당 표준형(Jordan canonical form)에서 가장 큰 블록의 크기를 $p_i$라 하자. 이때 $T$의 최소다항식은

$$p(t)=(t-{\lambda }_1{)}^{p_1}(t-{\lambda }_2{)}^{p_2}\cdots (t-{\lambda }_k{)}^{p_k}$$

조르당 기저(고윳값별 일반고유벡터 사슬) $\beta$를 취하면, 각 일반고유벡터 $v$ (길이가 $p_i$인 사슬의 끝벡터)에 대해

$$(T-{\lambda }_{i}I{)}^{p_i}(v)=0$$

이다. 따라서 $p(T)$를 $\beta$ 위에 작용시키면 모든 벡터가 $0$으로 보내져

$$p(T)(\beta )=\{0\}$$

가 되어 $p(T)$는 영(零) 변환이다.

최소다항식 $q(t)$는 $q(T)=0$인 모든 다항식 중 차수가 최소인 것이다. $p(T)=0$이므로 $q(t)$는 $p(t)$를 나누어야 한다. 따라서

$$q(t)=\prod _{i=1}^k(t-{\lambda }_i{)}^{r_i}(1\le r_i\le p_i)$$

형태이다.

만약 어떤 $i$에 대해 $r_i<p_i$라면, 조르당 기저에 길이가 $p_i$인 일반고유벡터 사슬의 끝벡터 $u$가 있다. 이 $u$에 대해

$$(T-{\lambda }_{i}I{)}^{r_i}(u)=w\ne 0$$

가 된다.

다른 고유값 블록에서는 $(T-{\lambda }_{j}I)$가 가역이므로, $(t-{\lambda }_j{)}^{r_j}$ 꼴 인자들은 $w$를 0으로 만들지 못한다. 따라서

$$q(T)(u)=\prod _j(T-{\lambda }_{j}I{)}^{r_j}(u)=(T-{\lambda }_{i}I{)}^{r_i}(u)\ne 0$$

가 되어 최소다항식이 $q(T)=0$이라는 사실에 모순된다. 그러므로 $r_i$는 꼭 $p_i$와 같아야 한다.

직합의 최소다항식

선형 변환 $T$가 주어지고, $T$에 대해 불변인 부분공간 $W_1$, $W_2$가 있다고 하자. 이때 $V=W_1\oplus W_2$라고 가정하자. $T$의 제한 $T_{W_1}$과 $T_{W_2}$의 최소 다항식이 각각 $p_1(t)$와 $p_2(t)$라고 하면,

$$p_1(t)=\prod _{\lambda }(t-\lambda {)}^{a_{\lambda }},p_2(t)=\prod _{\lambda }(t-\lambda {)}^{b_{\lambda }}$$

$V=W_1\oplus W_2$의 최소다항식은 $p_1(t)$와 $p_2(t)$의 최소공배수(Least Common Multiple)로 주어진다. 즉, $T$의 최소 다항식은 다음과 같다.

$$m_T(t)=\mathrm{lcm}(p_1(t),p_2(t))=\prod _{\lambda }(t-\lambda {)}^{\max (a_{\lambda },b_{\lambda })}$$

즉, 각 고유값 $\lambda$에 대해 양쪽에서 나타난 블록 크기의 최대값을 취한다. $m_T(t)$는 두 제한 $p_1(T)=0$, $p_2(T)=0$을 동시에 만족하는 가장 낮은 차수의 다항식이기 때문에 곱 대신 최소공배수가 되어야한다.

소멸자 (Annihilator)

$T$가 유한 차원 벡터 공간 $V$ 위의 선형 변환이고, $x$가 $V$의 비영벡터라고 하자. 다항식 $p(t)$가 $T$-소멸자(Annihilator)라고 하면, $p(t)$는 단위계수(Monic) 다항식으로서 $p(T)(x)=0$이 되는 가장 낮은 차수의 다항식이다.

벡터 $x$에 대한 $T$-소멸자과 연산자 $T$ 자체의 최소다항식(minimal polynomial)은 비슷해 보이지만, 관점과 적용 범위가 다르다. $T$-소멸자 $p_x(t)$는 벡터 $x$에 대해서만 작용하는 반면, 최소다항식 $m_T(t)$는 연산자 $T$가 작용하는 모든 벡터에 대해 작용한다.

따라서 각 $x$의 소멸다항식 $p_x(t)$는 반드시 $m_T(t)$를 나눈다.

$$p_x(t)|m_T(t).$$

즉, 최소다항식은 모든 벡터의 소멸다항식들의 최소공배수다.

$$m_T(t)=\mathrm{lcm}\{p_x(t):x\in V\},$$

특히 하나의 벡터로 $V$ 전체를 생성(=cyclic)할 수 있으면 그 $x$의 소멸다항식이 곧 최소다항식이 된다.

소멸자를 이용한 최소다항식 구하기

먼저 벡터 $v$를 하나 선택합니다. 보통 무작위 벡터나 표준기저를 시도하며, 실제로는 랜덤 벡터가 사이클릭일 확률이 높습니다.

벡터공간의 차원이 $n$이라면 케일리-해밀턴 정리에 의해 $\{v,Tv,T^{2}v,\cdots ,T^{n}v\}$는 반드시 선형종속입니다.

이때, 가장 작은 $k$에 대해

$$a_{0}v+a_{1}Tv+\cdots +a_k{T}^{k}v=0(a_k\ne 0)$$

을 만족하는 계수들을 찾으면, 이를 통해 소멸다항식

$$p_v(t)=t^k+\frac{a_{k-1}}{a_k}{t}^{k-1}+\cdots +\frac{a_0}{a_k}$$

을 구할 수 있습니다.

만약 $\mathrm{deg}{p}_v=\dim V$이면, $v$는 사이클릭 벡터이므로

$$m_T(t)=p_v(t)$$

가 됩니다.

반면에 $\mathrm{deg}{p}_v<\dim V$인 경우, $v$가 생성하는 부분공간 $V_1=⟨v,,Tv,\dots ,T^{k-1}v⟩$에서 다루지 못한 부분에 대해 새로운 벡터 $w$를 선택하여 동일한 과정을 반복합니다. 최종적으로 구한 소멸다항식들의 최소공배수가 변환 $T$의 최소다항식이 됩니다.

Krylov 부분공간

주어진 선형연산자 $T:V\to V$와 시작벡터 $v\in V$에 대하여,

\mathcal K_m(T,v)=\langle\,v,\;T v,\;T^2v,\;\dots,\;T^{m-1}v\,\rangle $$ 꼴로 늘려가는 부분공간을 Krylov 부분공간이라 부르고, 그 생성집합 $\{v,Tv,\dots,T^{m-1}v\}$ Krylov 기저의 후보라고 합니다. 보통 $m=\dim V$까지 진행하며, 어딘가에서 선형종속이 발생(즉 $\{v,\dots,T^m v\}$ 중 하나가 앞의 조합)하면 더 이상 차수가 올라가지 않으므로 소멸다항식이 발견됩니다. 구현도 비교적 간단하면서 $\mathcal{O}(n^3)$ 내외로 빠르게 동작합니다. ### Krylov-Gauss 예시

A = \begin{pmatrix} 3 & 0 & 1 \ 2 & 2 & 2 \ -1 & 0 & 1 \end{pmatrix}

1. $v_1 = (1, 0, 0)^T$

\begin{aligned} v_1 &= \begin{pmatrix}1\0\0\end{pmatrix} \ \ A v_1 &= \begin{pmatrix}3\2\-1\end{pmatrix} \ \ A^2 v_1 &= A (A v_1) = A \begin{pmatrix}3\2\-1\end{pmatrix} = \begin{pmatrix}8\8\-4\end{pmatrix} \end{aligned}

$$이므로$$

A^2 v_1 - 4 A v_1 + 4 v_1 = 0

$$따라서$$

{p_1(t) = (t - 2)^2 = t^2 - 4t + 4}

2. $v_2 = (0, 1, 0)^T$

\begin{aligned} v_2 &= \begin{pmatrix}0\1\0\end{pmatrix} \ \ A v_2 &= \begin{pmatrix}0\2\0\end{pmatrix} \end{aligned}

$$이므로$$

A v_2 - 2 v_2 = 0 \quad \Rightarrow \quad (A - 2I)v_2 = 0

$$따라서$$

p_2(t) = t - 2

$$3.최소다항식두소멸다항식의최소공배수는$$

m_A(t) = (t - 2)

이므로 행렬 $A$의 최소다항식은 $(t - 2)^2$ 입니다.