동반 행렬

1. 개요

동반 행렬 Companion matrix
정의	특성다항식이 주어진 모닉 다항식 $p$ 와 같은 $n\times n$ 행렬
모양	한 행(또는 열)에 계수, 나머지는 부대각 1 — 헤센베르크 형태
고유값	$p$ 의 근
고유벡터	근의 거듭제곱 $(\lambda^{n-1},\dots,\lambda,1)$ — 반데르몽드 열
쓰임	다항식 근 계산(roots), 선형 점화식·자기회귀의 상태공간 표현
변형	콜리그 행렬(체비쇼프), 코머드 행렬(직교다항식), 블록 동반(행렬 다항식)

다항식 근 찾기를 고유값 문제로 바꿔 치기 하는 행렬. 수치선형대수가 너무 잘 발달해서, 근 찾기 전용 알고리즘이 이 우회로에 자리를 내줬다.¹

동반 행렬(companion matrix)은 모닉 다항식 $p(x) = x^n + c_{n-1}x^{n-1} + \cdots + c_1x + c_0$ 에 대해, 특성다항식이 정확히 $p$ 가 되도록 계수를 배치한 행렬이다. 흔히 쓰는 꼴 하나는

$$C(p) = \begin{pmatrix} -c_{n-1} & -c_{n-2} & \cdots & -c_1 & -c_0\\ 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & & \ddots & & \vdots\\ 0 & 0 & \cdots & 1 & 0 \end{pmatrix}$$

이다. 첫 행에 계수를 놓느냐 마지막 열에 놓느냐, 전치를 하느냐에 따라 네 가지 꼴이 문헌에 섞여 쓰이는데, 모두 서로 닮음(또는 전치) 관계라 고유값은 같다. 이 문서는 위 꼴을 쓴다.

$\det(xI - C(p)) = p(x)$ 이므로 $C(p)$ 의 고유값이 곧 $p$ 의 근이다. MATLAB 의 roots 와 NumPy 의 np.roots 가 정확히 이것을 한다 — 동반 행렬을 만들고 QR 알고리즘으로 고유값을 구한다. 윌킨슨 다항식·뮬러 방법·프로니 방법 문서가 이 경로를 언급만 하고 넘어갔는데, 이 문서는 그 경로가 왜 정당하고 어디서 무너지는지를 다룬다.

2. 기본 성질

• 특성다항식. 마지막 열에 대한 여인수 전개로 귀납하면 $\det(xI - C) = p(x)$ 가 나온다. 케일리-해밀턴 정리에 의해 $p(C) = 0$ 이다.
• 최소다항식 = 특성다항식. 부대각이 모두 1 이라 $e_n, Ce_n, \dots, C^{n-1}e_n$ 이 선형독립이다(순환 벡터가 있다). 그래서 $C$ 의 최소다항식은 $p$ 자신이고, 중근이 있어도 각 고유값마다 조르당 블록이 정확히 하나뿐이다. 즉 $p$ 가 중근을 가지면 $C$ 는 반드시 대각화 불가능하다. 거꾸로, 최소다항식과 특성다항식이 같은 행렬(비유도 행렬, nonderogatory)은 모두 어떤 동반 행렬과 닮음이다.
• 고유벡터. $p(\lambda) = 0$ 이면 $v = (\lambda^{n-1}, \lambda^{n-2}, \dots, \lambda, 1)^\top$ 가 $Cv = \lambda v$ 를 만족한다. 둘째 행부터는 「한 칸 올리기」이고, 첫 행은 $-\sum c_k\lambda^k = \lambda^n$ 이 곧 $p(\lambda) = 0$ 이다. 예컨대 $p = (x-1)(x-2)(x-3)$ 이면 $C$ 의 첫 행은 $(6, -11, 6)$ 이고 고유값 3 의 고유벡터는 $(9, 3, 1)$ 이다. 고유벡터들을 늘어놓으면 반데르몽드 행렬이고, 그래서 서로 다른 근이면 $C = V\Lambda V^{-1}$ 이다.
• 헤센베르크. $C$ 는 이미 상 헤센베르크 형태다. QR 알고리즘의 첫 단계(헤센베르크 축약)를 공짜로 건너뛴다.

3. 선형 점화식과 상태공간 — 근 계산 말고의 쓰임

동반 행렬은 근 찾기보다 먼저 선형 점화식의 상태 전이 행렬로 나왔다. $y_{t} = -c_{n-1}y_{t-1} - \cdots - c_0y_{t-n}$ 은 상태 $s_t = (y_{t}, \dots, y_{t-n+1})^\top$ 로 $s_{t+1} = C\,s_t$ 가 된다.

• 자기회귀 모형 AR($p$)의 정상성 조건 「특성근이 단위원 밖」은 동반 행렬로 보면 「$C$ 의 스펙트럼 반지름 < 1」이다. 같은 이야기를 행렬 쪽에서 한 것뿐이다.
• 고계 상미분방정식 $y^{(n)} + c_{n-1}y^{(n-1)} + \cdots + c_0 y = 0$ 을 1계 연립으로 바꾸면 계수 행렬이 동반 행렬이다. 제어공학의 제어 가능 표준형(controllable canonical form)이 이것이다.
• 다단계 시간적분법의 안정성은 특성다항식 근의 위치로 판정하는데(강성 방정식 참고), 오차 전파를 행렬로 쓰면 역시 동반 행렬의 거듭제곱이다. 근이 단위원 위에서 중근이면 조르당 블록 때문에 오차가 다항식으로 자란다 — 영안정성(zero-stability)의 「단위원 위 근은 단순근이어야 한다」는 조건이 정확히 이 조르당 블록 금지다.

4. 근 계산 — 왜 이 우회로가 표준인가

다항식 근만 노리는 알고리즘(뉴턴+수축, 뮬러 방법, 젠킨스-트라우브 알고리즘)이 있는데 왜 $O(n^3)$ 짜리 고유값 계산을 쓸까. 이유는 셋이다.

1. 전역 수렴. 시프트 QR 은 초기값 없이 모든 근을 한꺼번에 준다. 수축 순서·초기값·복소수 근 처리 같은 근 찾기의 잔손질이 없다.
2. 후방 안정성. QR 알고리즘은 행렬 노름 기준으로 후방 안정하다. 계산된 고유값은 $\|E\| = O(u)\|C\|$ 인 섭동 $C + E$ 의 정확한 고유값이다.
3. 소프트웨어. LAPACK 의 geev 는 수십 년 다듬어졌다. 다항식 근 전용 코드보다 신뢰도가 높다.

함정은 2번에 숨어 있다. 행렬 섭동 $E$ 가 다항식 계수 섭동으로 바뀌면 얼마나 되는가? 에델먼·무라카미(1995)가 이걸 1차 섭동으로 풀었다. $E$ 가 $C$ 의 구조(첫 행만 계수)를 지키지 않는 일반 섭동이라, 대응하는 계수 섭동 $\delta c_k$ 가 각 계수 크기 $|c_k|$ 에 비례한다는 보장이 없다. 상한은 $\|C\|$ 와 계수들의 조합으로 정해지고, 계수 크기가 들쭉날쭉하면 작은 계수가 큰 계수 몫의 오차를 뒤집어쓸 수 있다. 즉 동반 행렬 QR 은 행렬로서는 후방 안정이지만 다항식으로서는 계수별(componentwise) 후방 안정이 아니다.

여기서 균형화(balancing, 파를렛-라인슈 1969)가 결정적이다. 대각 닮음 변환 $D^{-1}CD$ 로 행과 열의 노름을 맞추면 고유값은 그대로이고 $\|C\|$ 가 크게 줄어, 에델먼·무라카미의 상한이 훨씬 좋아진다. LAPACK geev 는 기본으로 균형화를 한다. 실제로 근이 $10^{-6}, 10^{-5}, \dots, 10^{6}$ 인 13차 다항식의 동반 행렬은 프로베니우스 노름이 $1.6\times10^{21}$ 인데 균형화 뒤 $1.2\times10^{6}$ 이 되고, np.roots 는 13개 근을 모두 상대오차 $5.7\times10^{-15}$ 로 돌려준다. 반면 윌킨슨 다항식(근 $1,\dots,20$)은 균형화를 해도 최대 상대오차가 $5.0\times10^{-3}$ 이다. 이쪽은 알고리즘이 아니라 근 자체의 조건수가 나쁜 경우라 어떤 후방 안정 방법도 못 구한다.

에델먼·무라카미의 실무 결론은 반반이다. 토-트레페텐이 제안한 무작위 시험 다항식들에서는 계수별 후방 오차도 작다고 예측됐고 실제로 작았다. 그러나 계수별 후방 오차가 작지 않은 반례를 구성할 수 있었고, 실제 계산에서도 그렇게 나왔다. 그래서 「균형화된 동반 행렬 QR 은 대개 충분히 좋다, 단 보장은 아니다」가 정확한 요약이다.²

5. 비용과 빠른 알고리즘

일반 고유값 QR 은 $O(n^3)$ 연산, $O(n^2)$ 메모리다. 차수가 수천이면 부담스럽다. 그런데 동반 행렬은 유니터리 행렬 + 계수 1 행렬 꼴이라 QR 반복 내내 이 구조(준분리, quasiseparable)가 유지된다. 이걸 이용하면 반복당 $O(n)$, 전체 $O(n^2)$ 로 줄일 수 있다는 것은 오래 알려졌지만, 초기 구조화 알고리즘들은 구조를 표현하는 생성자에 오차가 쌓여 안정성을 잃었다.

오렌츠·마흐·반데브릴·왓킨스(2015, 흔히 AMVW)는 동반 행렬을 기븐스 회전들의 곱과 계수 1 수정으로 표현하고, 바깥 계수 표현을 직접 건드리지 않는 방식으로 이 문제를 풀었다. $O(n^2)$ 이면서 (행렬 노름 기준) 후방 안정하다는 것을 증명했고, 차수가 클수록 LAPACK 일반 고유값 루틴보다 크게 빠르다고 보고했다. 계수 쪽 후방 오차 분석과 동반 펜슬로의 확장은 같은 저자들의 후속 연구가 이어받았다.³

6. 다른 기저 — 콜리그 행렬

단항식 계수는 근이 $[-1,1]$ 에 몰려 있을 때 특히 나쁜 표현이다. 그 구간의 다항식은 체비쇼프 다항식 계수 $\sum a_kT_k(x)$ 로 들고 다니는 게 자연스럽다(함수 근사 소프트웨어 Chebfun 이 그렇다). 굿(1961)의 콜리그 행렬(colleague matrix)은 체비쇼프 세 항 점화식 $xT_k = \tfrac12(T_{k+1} + T_{k-1})$ 을 이용해, 대각 근처는 $\tfrac12$ 가 늘어선 삼중대각이고 계수는 마지막 행에만 들어가는 행렬로 체비쇼프 급수의 근을 고유값으로 준다. 일반 직교다항식에 대한 같은 구성은 코머드 행렬(comrade matrix)이라 부른다.

근이 $[-0.95, 0.95]$ 에 등간격으로 놓인 다항식으로 재 보면 차이가 보인다(최대 절대오차).

차수	단항식 계수 + 동반 행렬	체비쇼프 계수 + 콜리그 행렬
20	$6.6\times10^{-12}$	$7.8\times10^{-13}$
30	$3.6\times10^{-8}$	$5.3\times10^{-9}$
40	$6.4\times10^{-4}$	$1.6\times10^{-5}$

(두 경우 모두 근에서 계수를 배정밀도로 만드는 단계의 반올림을 포함한다.) 차수가 올라갈수록 간격이 벌어진다. 등간격 근은 둘 다에게 어려운 시험이고, 함수를 체비쇼프 점에서 보간해 얻은 급수라면 콜리그 쪽의 이득은 훨씬 크다. 체비쇼프 계수는 매끄러운 함수에서 빠르게 감쇠해 계수 크기의 폭이 단항식만큼 크지 않기 때문이다. 같은 이유로 반데르몽드 행렬 대신 직교 기저 반데르몽드를 쓰는 것과 같은 계열의 처방이다.

7. 블록 동반 — 행렬 다항식의 선형화

계수가 행렬인 다항식 $P(\lambda) = A_m\lambda^m + \cdots + A_1\lambda + A_0$ 의 고유값 문제 $P(\lambda)x = 0$ 도 같은 방식으로 크기 $mn$ 의 일반화 고유값 문제로 바꾼다. 이를 선형화(linearization)라 한다. 구조 동역학의 2차 고유값 문제 $(\lambda^2M + \lambda D + K)x = 0$ 이 대표적인데, 감쇠 $D$ 가 있으면 모드 해석의 표준 고유값 문제로 곧장 안 내려가서 블록 동반 형태 $\begin{pmatrix} 0 & I\\ -K & -D\end{pmatrix}$ 와 $\mathrm{diag}(I, M)$ 의 펜슬로 푼다. 선형화는 무수히 많고 어느 것을 고르느냐에 따라 조건수가 달라진다는 것이 2000년대 이후 활발한 연구 주제다(블록 대칭 선형화, 스케일링).

8. 관련 문서

• 윌킨슨 다항식 · 호너 방법 · 뮬러 방법 · 젠킨스-트라우브 알고리즘 · 프로니 방법
• QR 알고리즘 · 고유값 문제 · 고유값 조건수 · 의사스펙트럼 · 후진 오차 해석
• 반데르몽드 행렬 · 케일리-해밀턴 정리 · 최소다항식 · 조르당 표준형 · 체비쇼프 다항식
• 자기회귀 모형 · 강성 방정식 · 모드 해석 · 행렬 균형화 · 2차 고유값 문제

9. Footnotes

1. 「고유값 계산은 다항식 근 계산으로 환원된다」고 배운 학생이 실무에서 「근 계산은 고유값 계산으로 환원된다」를 처음 보면 잠깐 세계관이 뒤집힌다. 교과서의 환원 방향과 프로그램의 환원 방향이 정반대인 대표적 사례. ↩

2. 균형화는 대각 행렬로 닮음 변환만 하므로 고유값은 수학적으로 하나도 안 바뀐다. 바뀌는 건 반올림 오차가 어느 원소에 얹히느냐뿐인데, 그것만으로 노름이 $10^{21}$ 에서 $10^{6}$ 으로 떨어진다. 공짜 점심이 실제로 존재하는 드문 장소. 단, 고유벡터가 필요하면 $D$ 를 되돌려 곱하는 걸 잊지 말 것. ↩

3. 「$O(n^2)$ 구조화 QR」 논문은 1990년대부터 꾸준히 나왔지만 상당수가 안정성 증명 없이 실험으로만 버텼다. 생성자 표현에 오차가 쌓이면 행렬이 더는 동반 행렬 구조를 갖지 않는데 알고리즘은 그 구조를 가정하고 계속 돈다 — 조용히 틀리는 최악의 유형이다. ↩