Lesson 19 of 20

대각화 — 반복을 한 번에 계산하기

A 를 백 번 곱하지 않고 A¹⁰⁰ 구하기

어떤 과정을 반복하는 문제는 어디에나 있습니다. 날씨가 내일 어떻게 될지, 시장 점유율이 1년 뒤 어떻게 될지, 인구가 어떻게 변할지. 전부 x, Ax, A²x, A³x, … 를 묻는 문제예요.

A 를 100번 곱하려면 행렬 곱을 100번 해야 할까요? 안 그래도 됩니다.

고유벡터의 눈으로 보면 이유가 명확합니다. 만약 x = c₁v₁ + c₂v₂ 라면

Aⁿx = c₁λ₁ⁿv₁ + c₂λ₂ⁿv₂

행렬 곱이 숫자의 거듭제곱으로 바뀌었습니다. 고유축으로 좌표를 갈아타기만 하면 되는 거예요.

High school반복을 한 번에 계산하기

부제의 문제 — A¹⁰⁰ 을 어떻게 구할까요?

100번 곱하지 않고 — 고유벡터 좌표에서 하면 쉽다

왜 쉬워지나

고유벡터 방향에서는 곱하기만 하면 됩니다.

—	—
Av = λv	—
A²v = λ²v	—
A¹⁰⁰v = λ¹⁰⁰v	✔

행렬 곱이 숫자의 거듭제곱이 된다

그래서 절차

단계	—
1	고유벡터 좌표로 바꾼다
2	각 성분에 λ¹⁰⁰ 곱한다
3	원래 좌표로 되돌린다

A¹⁰⁰ = P D¹⁰⁰ P⁻¹ — 그게 대각화다

14강의 그 이야기입니다

보는 각도를 바꾸면 문제가 단순해진다

비유 — 환전

단계	—
불편한 통화 → 편한 통화	P⁻¹
계산한다	D — 쉽다
다시 원래 통화로	P

"바꿔서 계산하고 되돌린다" — 수학이 자주 쓰는 전략이다

고유축으로 쪼개면 반복 계산이 거듭제곱 하나로 끝납니다.

Python Runs in your browser

def Ax(A, x): return [sum(a*xi for a, xi in zip(행, x)) for 행 in A]

A = [[2, 1],
     [1, 2]]
# 고유벡터 (1,1) 은 λ=3, (1,-1) 은 λ=1

x = [3, 1]
# x 를 고유벡터로 쪼갭니다: x = c1(1,1) + c2(1,-1)
c1 = (x[0] + x[1]) / 2
c2 = (x[0] - x[1]) / 2
print(f"x = {c1}·(1,1) + {c2}·(1,-1)")
print()

# 직접 10번 곱하기
v = x[:]
for _ in range(10):
    v = Ax(A, v)
print("A 를 10번 곱해서:", v)

# 고윳값 거듭제곱으로 한 번에
직통 = [c1 * 3**10 * 1 + c2 * 1**10 * 1,
        c1 * 3**10 * 1 + c2 * 1**10 * (-1)]
print("고윳값으로 한 번에:", 직통, "← 같습니다")

🎮 오래 두면 어디로 가나

시장 점유율이 매달 옮겨 다니는 모형입니다. "한 달 →" 을 눌러 가며 어디로 수렴하는지 보세요. 출발점을 바꿔도 같은 곳에 도착합니다. 왜냐하면 λ=1 인 방향만 남고 나머지는 λⁿ → 0 으로 사그라들기 때문이에요.

High school대각화란

note 의 정의를 기하적으로 읽어 봅시다.

A = P D P⁻¹ — 좌표 변환 · 늘이기 · 되돌리기

부분	하는 일
P⁻¹	고유벡터 좌표로 바꾼다
D	각 축을 λ 배 늘인다
P	원래 좌표로 되돌린다

복잡한 변환도 축을 잘 잡으면 단순한 늘이기다

P 는 무엇인가

P 의 열이 고유벡터들이다

6강의 "열 = 기저가 가는 곳" 그대로예요. 표준기저를 고유벡터로 보내는 변환입니다.

언제 대각화되나

조건	—
고유벡터가 n 개 독립	P 가 가역이어야 하니까 ✔
고윳값이 전부 다르면	항상 대각화된다
대칭행렬이면	항상 — 게다가 직교로 ⭐

대칭행렬은 특별히 좋다 — 스펙트럴 정리

왜 대칭이 좋은가

—	—
고윳값이 전부 실수	복소수가 안 나온다 ✔
고유벡터가 서로 직교	16강의 편리함 ✔
P⁻¹ = Pᵀ	역행렬을 안 구해도 된다 ✔

공분산행렬이 대칭이라 PCA 가 잘 된다 — 20강

피보나치를 한 번에 구하기

대각화의 가장 예쁜 예입니다. 피보나치 수열의 점화식을 행렬로 적어 봅시다.

[F_n+1]  [1 1] [F_n  ]

[F_n  ] = [1 0] [F_n−1]

이 행렬의 고윳값을 구하면 λ² − λ − 1 = 0 에서 황금비 φ = (1+√5)/2 와 (1−√5)/2 가 나옵니다.

그래서 F_n 을 반복 없이 한 방에 구하는 공식이 나와요 — 비네의 공식이라고 부릅니다. 반복문 없이 수열의 n번째 항이 나오는 거죠.

고윳값이 황금비. 반복문 없이 F(n)을 구할 수 있습니다.

Python Runs in your browser

# 피보나치를 세 가지 방법으로
def 반복(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a + b
    return a

def 행렬거듭제곱(n):
    # [[1,1],[1,0]]^n 을 분할 거듭제곱으로 — O(log n)
    def 곱(A, B):
        return [[A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
                [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]]]
    R = [[1, 0], [0, 1]]
    M = [[1, 1], [1, 0]]
    while n:
        if n & 1: R = 곱(R, M)
        M = 곱(M, M); n >>= 1
    return R[0][1]

def 비네(n):
    r5 = 5 ** 0.5
    파이 = (1 + r5) / 2
    프시 = (1 - r5) / 2
    return round((파이**n - 프시**n) / r5)

for n in (10, 20, 30, 50):
    print(f"F({n:>2}) = 반복 {반복(n):>12}  행렬 {행렬거듭제곱(n):>12}  비네 {비네(n):>12}")
print()
print("황금비 φ =", (1 + 5**0.5)/2, "← [[1,1],[1,0]] 의 고윳값입니다")

High school대각화가 안 되는 행렬도 있습니다

note 의 이 경고를 왜 와 함께 봅시다.

고유벡터가 모자라면 대각화가 안 된다

언제 모자라나

상황	—
고윳값이 중복인데	고유벡터는 하나뿐 ⚠

전단 행렬이 대표적이다 — 한 방향만 지킨다

기하적으로

전단(shear)은 기울이는 변환입니다.

방향	—
가로 방향	안 변한다 — 고유벡터 ✔
다른 모든 방향	기울어진다 ⚠

축이 하나뿐이니 2차원을 설명 못 한다

그럼 어떻게 하나

방법	—
조르당 표준형	대각에 가깝게 — 이론적
SVD	어떤 행렬이든 된다 ⭐ (20강)

20강의 SVD 가 조건 없이 통하는 이유가 여기 있다

SVD 가 왜 항상 되나

—	—
대각화	같은 기저를 양쪽에 쓴다 — 까다롭다
SVD	다른 기저를 써도 된다 ✔

제약을 하나 풀었더니 모든 행렬에 통한다

게다가 정사각형이 아니어도 됩니다. 19강의 한계를 20강이 넘어서는 거죠.

어디에 쓰이나

PageRank — 웹 링크 행렬의 λ=1 고유벡터가 페이지 순위입니다. 구글은 이것을 거듭제곱법으로 구했어요 (18강 마지막 코드)
마르코프 연쇄 — 날씨·대기행렬·게임 밸런스의 장기 예측
주성분분석(PCA) — 공분산행렬의 고유벡터가 데이터가 가장 많이 퍼진 방향
진동 해석 — 다리와 건물의 고유진동수. 공명을 피하려면 반드시 계산해야 합니다
미분방정식 — x' = Ax 의 해가 e^{λt}v 꼴로 나옵니다

공통점이 보이시나요? 전부 같은 일을 반복하거나 가장 두드러진 방향을 찾는 문제입니다. 고윳값 분해는 그 두 질문에 대한 답이에요.

정상상태 = 고윳값 1의 고유벡터. PageRank 가 이 원리로 돕니다.

Python Runs in your browser

# 마르코프 연쇄 — 오래 두면 어디로 가나
def Ax(A, x): return [sum(a*xi for a, xi in zip(행, x)) for 행 in A]

# 열의 합이 1: A사 손님의 90%가 남고 10%가 떠남 / B사 손님의 20%가 A로
P = [[0.9, 0.2],
     [0.1, 0.8]]

for 출발 in ([1.0, 0.0], [0.0, 1.0], [0.5, 0.5]):
    x = 출발[:]
    for _ in range(60):
        x = Ax(P, x)
    print(f"출발 {출발} → 60달 뒤 {[round(v, 6) for v in x]}")
print()
print("출발점이 무엇이든 같은 곳으로 갑니다")
print("그 자리는 Px = x 를 만족하는 곳 — 즉 λ=1 의 고유벡터입니다")
print("풀어 보면 (2/3, 1/3) =", [round(2/3, 6), round(1/3, 6)])

High school대각화가 답하는 실제 문제들

19강을 마치며 쓰임을 봅시다.

문제	고윳값이 답하는 것
반복하면 어떻게 되나	\|λ\| > 1 이면 발산 ⚠
안정적인가	\|λ\| < 1 이면 수렴 ✔
결국 어디로 가나	가장 큰 λ 의 방향 ⭐

가장 큰 고윳값이 장기 행동을 지배한다

왜 그런가

λ₁ > λ₂ 이면 λ₁ⁿ 이 λ₂ⁿ 보다 압도적으로 커집니다.

n	2ⁿ	1.5ⁿ	비율
10	1024	58	18배
50	10¹⁵	10⁸	10⁷ 배

반복할수록 한 방향만 남는다 — 거듭제곱법의 원리다

실제 예 — 인구 모형

—	—
연령별 인구 변화를 행렬로	—
가장 큰 고윳값	= 장기 성장률 ⭐
그 고유벡터	= 안정적 연령 구조

초기 상태와 무관하게 같은 구조로 수렴한다

페이지랭크도 같은 원리

링크를 따라 반복해서 돌아다니면 가장 큰 고유벡터로 수렴합니다.

그게 곧 웹의 중요도 분포다 — 18강의 그 이야기

비유 — 소문의 확산

—	—
누가 먼저 말했든	—
결국 퍼지는 패턴은	같아진다 ✔

구조가 초기 조건보다 강하다 — 고유벡터가 그 구조다

🤔 Check yourself

A = PΛP⁻¹ 일 때 A⁵ 는?

Answer A⁵ = PΛP⁻¹·PΛP⁻¹·… 에서 가운데 P⁻¹P = I 가 계속 사라져 PΛ⁵P⁻¹ 만 남습니다. Λ⁵ 는 대각선만 5제곱하면 끝이에요.

🤔 Check yourself

n×n 행렬이 대각화되기 위한 조건은?

🤔 Check yourself

마르코프 연쇄가 같은 상태로 수렴하는 까닭은?