최소다항식

수치해석 마지막 수정: 2026-08-09 04:39:23

1. 개요[편집]

최소다항식 Minimal polynomial
정의	$m_A(A)=O$ 인 모닉 다항식 중 차수가 최소인 것
유일성	유일 (소멸 이데알의 모닉 생성원)
특성다항식과	$m_A \mid p_A$ — 케일리-해밀턴 정리
조르당 형	각 고유값의 최대 블록 크기가 지수
대각화	가능 $\iff$ $m_A$ 가 중근을 갖지 않음
수치 계산	불연속 — 부동소수점으로 계산하지 않는다

특성다항식은 행렬의 크기를 말해 주고, 최소다항식은 행렬의 성격을 말해 준다.

최소다항식(minimal polynomial) $m_A$ 는 정사각행렬 $A$ 에 대해 $m_A(A) = O$ 를 만족하는 모닉 다항식 중 차수가 가장 낮은 것이다. 존재는 케일리-해밀턴 정리가 보장한다 — 특성다항식 $p_A$ 자체가 $A$ 를 죽이므로 후보 집합이 비어 있지 않다. 유일성은 한 줄이다. 같은 최소 차수의 모닉 다항식이 둘 있으면 차를 취했을 때 차수가 낮으면서 여전히 $A$ 를 죽이는 다항식이 나오므로 모순이다.

더 깔끔한 진술은 이렇다. $\{q \in \mathbb{C}[\lambda] : q(A) = O\}$ 는 다항식환의 이데알이고, $\mathbb{C}[\lambda]$ 가 주 이데알 정역이므로 이 이데알은 생성원 하나로 표현된다. 그 모닉 생성원이 $m_A$ 다. 여기서 곧바로 따라오는 것이 나눗셈 성질 — $q(A) = O$ 이면 $m_A \mid q$ 이고, 특히 $m_A \mid p_A$ 다.

2. 특성다항식과 무엇이 다른가[편집]

두 다항식은 근의 집합은 같고 중복도만 다르다. $\lambda$ 가 $m_A$ 의 근인 것과 $A$ 의 고유값인 것은 동치다. 한쪽 방향은 $Av = \lambda v$ 에서 $0 = m_A(A)v = m_A(\lambda)v$ 로 바로 나오고, 반대 방향은 $m_A \mid p_A$ 에서 나온다. 따라서

p_A(\lambda) = \prod_i (\lambda - \lambda_i)^{a_i}, \qquad m_A(\lambda) = \prod_i (\lambda - \lambda_i)^{m_i}, \qquad 1 \le m_i \le a_i

이다. 몇 가지 예가 감을 잡아 준다.

행렬	특성다항식	최소다항식
단위행렬 $I_n$	$(\lambda-1)^n$	$\lambda - 1$
$\mathrm{diag}(2,2,3)$	$(\lambda-2)^2(\lambda-3)$	$(\lambda-2)(\lambda-3)$
멱영 조르당 블록 $J_n(0)$	$\lambda^n$	$\lambda^n$
사영행렬 ( $A^2=A$ )	랭크에 의존	$\lambda^2-\lambda$ 의 약수

$\deg m_A = n$ 인 행렬을 비퇴화(nonderogatory) 또는 순환행렬이라 부른다. 이는 모든 고유값의 기하적 중복도가 1인 것과 동치이고, 다시 $A$ 가 동반행렬과 닮음인 것과 동치다. 반대쪽 극단이 단위행렬 — 차수 1이다.

같은 정보를 다항식환 위의 가군으로 옮기면 $\lambda I - A$ 의 스미스 표준형이 되고, 그때 $m_A$ 는 마지막 불변인자, $p_A$ 는 모든 불변인자의 곱이라는 대응이 생긴다. 복소수체에 의존하지 않는 유리 표준형이 여기서 나온다.¹

3. 조르당 형에서 읽어내기[편집]

지수 $m_i$ 의 정체는 조르당 표준형이 정확히 알려준다. 크기 $k$ 인 블록 $J_k(\lambda) = \lambda I + N$ 에서 $N$ 은 멱영이고 $N^{k-1} \ne 0$ , $N^k = 0$ 이므로 이 블록의 최소다항식은 정확히 $(\lambda-\lambda_i)^k$ 다. 블록대각 행렬의 최소다항식은 블록별 최소다항식들의 최소공배수이므로,

m_i = \bigl(\text{고유값 } \lambda_i \text{ 에 붙은 조르당 블록 중 } \textbf{가장 큰 것}\text{의 크기}\bigr)

이다. 반면 $p_A$ 의 지수 $a_i$ 는 그 고유값 블록들의 크기 총합이다. 최대냐 합이냐 — 딱 이 차이다. $m_i$ 를 고유값 $\lambda_i$ 의 지표(index)라고도 부른다.

여기서 가장 쓸모 있는 따름정리가 나온다.

$A$ 가 대각화 가능 $\iff$ $m_A$ 가 서로 다른 일차식의 곱 (중근 없음).

모든 $m_i = 1$ 이라는 것이 모든 블록이 $1\times1$ 이라는 것과 같기 때문이다. 고유벡터를 세지 않고, 심지어 고유값을 구하지 않고도 대각화 가능성을 판정할 수 있는 조건이라는 점이 매력이다. $A^2 = A$ 면 $m_A \mid \lambda^2-\lambda$ 라 사영행렬은 무조건 대각화 가능하고 고유값이 0과 1뿐이며, 그래서 대각합이 곧 랭크다 — 두 줄이면 끝난다.²

상수계수 선형 상미분방정식의 해 기저에 $e^{\lambda t}, te^{\lambda t}, \dots, t^{m_i-1}e^{\lambda t}$ 가 등장하는 것도 같은 지수다. $t$ 의 최고 차수를 정하는 것은 대수적 중복도가 아니라 최소다항식의 지수라는 사실은 임계 감쇠 진동계를 손으로 풀 때 실제로 쓰인다.

4. 크릴로프 차원의 상한[편집]

수치해석 쪽에서 이 개념이 밥값을 하는 곳은 여기다. 벡터 하나에 대해서도 같은 정의를 할 수 있다 — $m_{A,b}(A)b = 0$ 인 최소 차수 모닉 다항식을 $b$ 의 최소다항식, 그 차수 $d$ 를 $A$ 에 대한 $b$ 의 등급(grade)이라 한다. 당연히 $m_{A,b} \mid m_A$ 다. 그러면

\dim \mathcal{K}_m(A,b) = \min(m,\ d), \qquad \mathcal{K}_d(A,b) \text{ 는 } A\text{-불변}

이다. 크릴로프 부분공간은 $d$ 차원에서 자라기를 멈추고 그 순간 불변 부분공간이 된다. 아놀디 알고리즘에서 $h_{j+1,j} = 0$ 이 되는 “행운의 붕괴”가 정확히 이 시점이다.

따라서 크리로프 부분공간법의 유한 종료성이 따라온다. 정확 산술에서 GMRES와 CG는 늦어도 $\deg m_{A,b} \le \deg m_A \le n$ 회 안에 정확해에 도달한다. 이론적으로는 반복법이 아니라 직접법인 셈이다.

그런데 실전에서 진짜 지렛대는 차수가 아니라 서로 다른 고유값의 개수다. 대각화 가능한 $A = V\Lambda V^{-1}$ 에 대해 GMRES 잔차는

\frac{\|r_k\|_2}{\|r_0\|_2} \le \kappa(V)\min_{\substack{\deg p \le k \\ p(0)=1}} \max_i |p(\lambda_i)|

로 눌린다. 서로 다른 고유값이 $k$ 개뿐이면 그 점들을 근으로 갖는 $k$ 차 다항식을 고를 수 있으므로 우변이 정확히 0 — $k$ 스텝 만에 끝난다. 전처리기가 하는 일이 바로 이것이다. 전처리는 조건수만 낮추는 것이 아니라 스펙트럼을 몇 개의 뭉치로 모아 낮은 차수 다항식이 그 위에서 작아지게 만든다. 진짜 최소다항식의 차수는 여전히 $n$ 이지만, “실효 차수”가 뭉치 개수로 내려가는 것이다.³

5. 왜 부동소수점에서는 계산하지 않는가[편집]

$\deg m_A$ 는 행렬 성분에 대해 불연속이다. 이것 하나로 이야기가 끝난다.

$I_n$ 의 최소다항식은 차수 1이다. 그런데 $I_n + \varepsilon N$ 을 아무 $N$ 으로나 흔들면 거의 확실히 고유값 $n$ 개가 전부 달라지고, 그 순간 최소다항식은 특성다항식과 같아져 차수가 $n$ 이 된다. $\varepsilon = 10^{-16}$ — 반올림 한 번 — 이어도 그렇다. 일반적으로 무작위로 뽑은 행렬은 거의 확실히 $m_A = p_A$ 이고, 최소다항식이 짧아지는 것은 구조가 정확히 박혀 있을 때뿐이다.

여기에 후진 오차 해석의 논리를 얹으면 결론이 확정된다. 후진 안정한 알고리즘은 ” $A$ 근처 어떤 행렬의 정확한 답”을 준다. 그런데 $A$ 근처 행렬은 거의 전부 최소다항식 차수가 $n$ 이다. 따라서 후진 안정한 알고리즘은 원리적으로 최소다항식을 복원할 수 없다. 조르당 표준형이 계산 불가인 것과 정확히 같은 이유이며, 실제로 둘은 같은 정보다.

연속적인 대체물이 의사스펙트럼이다. $\Lambda_\varepsilon(A) = \{z : \sigma_{\min}(zI-A)\le\varepsilon\}$ 을 놓고 “서로 다른 고유값이 몇 개냐”를 “해상도 $\varepsilon$ 에서 뭉치가 몇 개냐”로 바꾼다. 위의 다항식 상계도 대응물이 있어서, $\partial\Lambda_\varepsilon$ 의 길이를 $L_\varepsilon$ 이라 할 때

\|p(A)\|_2 \le \frac{L_\varepsilon}{2\pi\varepsilon}\max_{z\in\Lambda_\varepsilon}|p(z)|

가 성립한다. $\kappa(V)$ 라는 계산 불가능한 양이 등고선 길이라는 잴 수 있는 양으로 바뀐 셈이다.

한술 더 뜨면, 비정규 행렬에서는 고유값 정보 자체가 수렴을 예측하지 못한다. 그린바움-프타크-스트라코시(1996)는 임의로 지정한 비증가 잔차 곡선과 임의로 지정한 스펙트럼에 대해, 정확히 그 곡선을 그리는 행렬과 우변이 존재함을 보였다. 스펙트럼과 GMRES 수렴 사이에는 원리적으로 아무 관계도 없을 수 있다는 뜻이다. 최소다항식은 비정규 행렬의 수렴을 설명하는 언어로는 부족하다.

물론 최소다항식을 실제로 계산하는 세계도 있다. 정확 산술, 즉 유리수체나 유한체 위의 컴퓨터 대수다. $\lambda I - A$ 의 스미스 표준형을 구하거나, 크릴로프 수열의 첫 선형종속을 정확 연산으로 잡아내면 된다. 비드만(Wiedemann, 1986)의 희소 선형계 알고리즘은 유한체 위에서 수열 $\{u^{\top}A^kb\}$ 의 최소다항식을 베를레캄프-매시로 찾아 해를 구성하는데, 암호 분야의 대규모 희소 문제에서 여전히 현역이다.⁴

6. 관련 문서[편집]

조르당 형은 특성다항식이 일차식으로 완전히 쪼개지는 체(대표적으로 $\mathbb{C}$ )에서만 온전하지만, 불변인자와 유리 표준형은 임의의 체에서 성립한다. 그래서 유한체 위에서 선형대수를 하는 부호이론·암호 쪽 사람들은 조르당 대신 불변인자로 말한다. 같은 정보를 다른 언어로 쓰는 것뿐이지만, 언어를 잘못 고르면 정리 하나가 통째로 거짓이 된다. ↩
” $A^2=A$ 면 $\mathrm{tr}\,A = \mathrm{rank}\,A$ ” 는 선형대수 시험 단골인데, 최소다항식으로 접근하면 세 줄, 정공법으로 하면 한 페이지다. 시험장에서 이 차이는 생각보다 크다. ↩
반대 방향의 함정도 있다. “고유값이 $k$ 개뿐이니 $k$ 스텝이면 끝난다”를 부동소수점에서 기대하면 안 된다. 크릴로프 벡터의 직교성이 무너지면 이론상 끝났어야 할 스텝에서 잔차가 남고, 계속 돌리면 다시 내려간다. GMRES/CG가 ” $n$ 스텝 직접법”이 아니라 “잘 전처리하면 훨씬 일찍 멈추는 반복법”으로 취급되는 이유다. ↩
여기서 재미있는 역전이 일어난다. 부동소수점에서는 “최소다항식을 계산한다”가 금기어인데, 유한체에서는 나눗셈에 오차가 없으므로 그것이 오히려 가장 빠른 길이 된다. 수치해석의 상식과 컴퓨터 대수의 상식이 정반대인 지점이고, 두 분야 사람이 같은 회의실에서 싸우는 단골 주제이기도 하다. ↩