홍라이프 계산기행렬 거듭제곱 계산기 쉽게 이해하기 — 개념과 원리
정사각행렬을 자연수 n번 거듭제곱한 Aⁿ = A·A·…·A(n개)를 구하는 계산기이며, A⁰ = I로 정의합니다. 행렬의 거듭제곱은 같은 선형 변환을 반복할 때의 결과를 나타냅니다. 마르코프 연쇄의 n단계 전이, 해마다 반복되는 인구 모형, 그래프의 인접행렬로 센 길이 n인 경로의 수, 피보나치 수열 같은 점화식이 모두 Aⁿ로 표현됩니다.
계산 방법
A를 n − 1번 곱하지 않고 반복 제곱법(이진 거듭제곱)을 씁니다. n을 2진수로 나타낸 뒤, 결과 P = I와 밑 B = A에서 시작합니다. n의 가장 낮은 자리가 1이면 P에 B를 곱하고, B를 제곱한 다음 n을 한 자리 오른쪽으로 옮깁니다. n이 0이 되면 P가 Aⁿ입니다. 제곱은 약 log₂ n번이면 되므로 A¹⁰⁰⁰도 999번이 아니라 20번 정도의 곱셈으로 끝납니다. 행렬은 정사각이어야 하고 n은 0 이상의 정수여야 합니다.
원리
지수법칙 Aᵃ·Aᵇ = Aᵃ⁺ᵇ가 핵심입니다. 모든 자연수는 2의 거듭제곱의 합(2진수의 각 자리)으로 쓸 수 있고, A, A², A⁴, A⁸, …은 앞의 것을 제곱해 얻습니다. 그중 n의 1인 자리에 해당하는 것만 곱하면 Aⁿ가 됩니다. 기본값 행렬에는 재미있는 성질도 있습니다. [1 1; 1 0]ⁿ = [Fₙ₊₁ Fₙ; Fₙ Fₙ₋₁]이며 Fₖ는 피보나치 수(F₁ = F₂ = 1)입니다. 이 행렬을 곱하면 각 행의 두 성분을 더하게 되는데, 이것이 바로 Fₖ₊₁ = Fₖ + Fₖ₋₁이라는 점화식이기 때문입니다.
예제 풀이
- 기본 입력: A = [1 1; 1 0], n = 10이며 10 = 1010₂ = 8 + 2입니다.
- 제곱을 반복합니다: A² = [2 1; 1 1], A⁴ = [5 3; 3 2], A⁸ = [34 21; 21 13]
- 1인 자리만 곱합니다: A¹⁰ = A²·A⁸
- 2×34 + 1×21 = 89, 2×21 + 1×13 = 55, 1×34 + 1×21 = 55, 1×21 + 1×13 = 34
- 결과: A¹⁰ = [89 55; 55 34] = [F₁₁ F₁₀; F₁₀ F₉]
결과 해석
Aⁿ의 장기적인 모습은 A의 고윳값이 결정합니다. 모든 고윳값의 절댓값이 1보다 작으면 성분이 0으로 줄어들고, 1보다 큰 고윳값이 있으면 대략 λⁿ처럼 커집니다. 예제의 가장 큰 고윳값은 황금비 φ ≈ 1.618이라서 89/55 ≈ 1.618처럼 한 단계마다 약 1.618배씩 커집니다. 전이행렬은 가장 큰 고윳값이 1이어서 Aⁿ의 행이 정상분포에 가까워지는 경우가 많습니다.
흔한 실수
- 행렬 곱 대신 각 성분을 제곱하는 경우
- (AB)ⁿ = AⁿBⁿ라고 쓰는 경우. A와 B가 교환 가능할 때만 성립합니다.
- 음수나 분수 지수를 넣는 경우. 이 계산기는 0 이상의 정수만 다룹니다.
자주 묻는 질문
A⁰는 무엇인가요?
정의에 따라 같은 크기의 단위행렬입니다.
A⁻ⁿ은 어떻게 구하나요?
행렬식이 0이 아니면 먼저 역행렬을 구한 뒤 그 역행렬을 n제곱합니다.
n이 아주 클 때 더 좋은 방법이 있나요?
A = PDP⁻¹로 대각화되면 Aⁿ = PDⁿP⁻¹이고, Dⁿ은 고윳값만 n제곱하면 됩니다.
출처: Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 4.6.3절 · Gilbert Strang, Introduction to Linear Algebra, Wellesley-Cambridge Press