[경고] 아래 글을 읽지 않고 "퇴플리츠 행렬"을 보면 바보로 느껴질 수 있습니다.
[그림 1] 색깔 조각으로 표현한 퇴플리츠 행렬(출처: wikipedia.org)
독특한 원소 패턴을 가진 퇴플리츠 행렬(Toeplitz matrix) $\bf T$는 행이 증가함에 따라 [그림 1]처럼 대각선 원소의 왼쪽과 오른쪽 부분이 순차적으로 돌아가는 모양을 가진다. 이를 $2n-1$개의 퇴플리츠 상수(Toeplitz constant) $a_i$로 정의한다.
(1a)
(1b)여기서 $i$ = $1,2\cdots, n$ 및 $j$ = $1,2\cdots, n$; $T_{ij}$는 퇴플리츠 행렬 $\bf T$의 $i$행 $j$열 원소, $\bf T$의 차원(dimension)은 $n \times n$이다. 퇴플리츠 행렬은 반대각선(anti-diagonal)에 대해 대칭이라서 직각 대칭 행렬(persymmetric matrix)의 범주에 속한다. 또한 식 (1)처럼 대각선을 따라가는 원소는 항상 상수이므로, 퇴플리츠 행렬의 다른 이름은 대각 상수 행렬(diagonal-constant matrix)이다. 대각선 기준으로 값이 상수인 퇴플리츠 행렬에 대비되게, 반대각선 방향으로 놓인 원소가 상수인 행렬은 한켈 행렬(Hankel matrix) $\bf H$로 이름 붙인다.
(1c)
(1d)여기서 한켈 행렬의 구성 원소를 체계적으로 보려면 첫 행 벡터[$a_0, a_1, \cdots, a_{n-1}$]에서 시작해 마지막 열 벡터[$a_n, a_{n+1}, \cdots, a_{2n-2}$]까지 따라간다. 한켈 행렬은 자동적으로 대칭 행렬이 된다. 또한 교환 행렬(exchange matrix) $\bf J$를 통해 $\bf H$ = $\bf TJ$처럼 퇴플리츠 행렬과 한켈 행렬은 서로 연결된다.
퇴플리츠 행렬은 상삼각과 하삼각 행렬(upper and lower triangular matrices)로 구성된다.
(2)여기서 $\bf I$는 항등 행렬(identity matrix), $\bf L$과 $\bf U$는 각각 ${\bf T}/a_0$의 상삼각과 하삼각 행렬 부분이다. 삼각 행렬 $\bf L$과 $\bf U$는 다시 퇴플리츠 행렬에 속한다. 대칭 퇴플리츠 행렬(symmetric Toeplitz matrix) $\bf S$는 행렬 곱과 합의 형태로 분해할 수 있다.
(3a)
(3b)
(3c)여기서 $\bf S$는 대칭 행렬(symmetric matrix), $a_{-i}$ = $a_i$, $(\cdot)^T$는 전치 행렬(transpose)이다. 식 (3c)에 나타난 행렬 곱 ${\bf L}{\bf L}^T$은 전형적인 대칭 행렬이다. 대칭 퇴플리츠 행렬은 대칭과 직각 대칭이 함께 나타나는 쌍대칭 행렬(bisymmetric matrix)이다.
대칭 행렬의 역행렬은 다시 대칭 행렬이므로, 식 (3c)처럼 $\bf S$의 역행렬 ${\bf S}^{-1}$을 표현한다[1]. 역행렬의 정확한 증명은 식 (16)에 제시한다.
(4)여기서 $\bf X$와 $\bf Y$는 $\bf L$과 같은 하삼각 행렬, $x_0$은 0이 아닌 적절한 상수이다. 역행렬의 원소 $B_{ij}$는 원래 행렬의 여인자(cofactor) $C_{ij}$에 연결되어서 $B_{ij}$는 다음 성질을 갖는다.
- 일반적으로 $C_{ii}$ $\ne$ $C_{jj}$ ($i \ne j$): 같을 수 있지만 보통 다름
- 쌍대칭 행렬의 역행렬은 쌍대칭성을 가지므로, 여인자 $C_{ij}$가 다른 값은 전체 원소에서 ◥◤ 위치에만 있음
- 역행렬 ${\bf S}^{-1}$의 독립된 원소 개수[$B_{ij}$의 개수]는 $(n+1)^2 \mathbin{/} 4$[$n$: 홀수] 혹은 $n(n+2) \mathbin{/} 4$[$n$: 짝수]이므로, $\bf X$와 $\bf Y$는 $\bf L$ 구조의 하삼각 행렬로 선택할 수 있음[∵ 독립된 원소 $B_{ij}$는 전체 행렬 기준으로 ◥◤에 분포함]
대칭 퇴플리츠 행렬과 다르게, 행 번호가 커질 때 원소를 오른쪽으로 이동시키면서 순환 편이 혹은 전환(circular shift)을 적용한 행렬은 순환 행렬(circulant matrix) 혹은 더 정확히 순환 퇴플리츠 행렬(circulant Toeplitz matrix)이라 한다.
(5)여기서 퇴플리츠 상수 $a_{-i}$ = $a_{n-i}$이다.
요상하게 정의한 퇴플리츠 행렬이 푸리에 변환(Fourier transform)과 만나는 지점은 길쌈(convolution)이다. 퇴플리츠 행렬과 열 벡터의 곱으로 이산 길쌈(discrete convolution) $(f * g)_m$을 정의한다.
(6)이산 길쌈 $(f * g)_m$과 입력 신호인 $f_m$을 알면, 퇴플리츠 행렬의 역행렬을 식 (7d)처럼 구해서 또 다른 입력인 $g_m$을 결정할 수 있다.
퇴플리츠 역행렬(Toeplitz inverse matrix) ${\bf T}^{-1}$은 퇴플리츠 행렬 $\bf T$로 만든 일부 연립 일차 방정식의 해만 알아도 일의적으로 정해진다.
[퇴플리츠 역행렬] [2]
퇴플리츠 행렬 $\bf T$로 만든 열 벡터 $\bf x$, $\bf y$의 원소로 퇴플리츠 역행렬 ${\bf T}^{-1}$을 생성할 수 있다.
(7a)
(7b)
(7c)
(7d)여기서 $\bf x$ = $[x_0~x_1~\cdots~x_{n-1}]^T$, $\bf y$ = $[y_0~y_1~\cdots~y_{n-1}]^T$, ${\bf e}_i$ = $[0~\cdots~0~1~0~\cdots~0]^T$는 $i$번 정규 직교 열 벡터(orthonormal column vector) 혹은 표준 기저(standard basis), ${\bf e}_i$에서 $i$번째 원소만 $1$이고 나머지는 모두 $0$, ${\bf e}_1$ = $[1~0~0~\cdots~0]^T$, $\bf d$ = $[0,~a_{n-1}-a_{-1},~a_{n-2}-a_{-2}$, $\cdots$, $a_2 - a_{-n+2},~ a_1 - a_{-n+1}]^T$, $\bf I$는 항등 행렬이다.
[증명]
동반 행렬(companion matrix) $\bf K$와 퇴플리츠 행렬 $\bf T$로 만든 교환 법칙의 차이 ${\bf KT} - {\bf TK}$는 1행과 $n$열에만 값이 있고 나머지 원소는 모두 $0$으로 나타나므로, 다음 항등식이 성립한다.
(8a)
(8b)
(9)식 (9)의 둘째식에 $\bf x$를 곱해서 단위 기저 벡터(unit basis vector) ${\bf e}_i$의 표현식을 구한다.
(10)여기서 $j$ = $0,1,\cdots,n-1$; 동반 행렬의 성질에 따라 ${\bf K}{\bf e}_i$ = ${\bf e}_{i+1}$이 성립한다. 식 (10)에 등장하는 $\bf M$의 거듭제곱과 $\bf y$로 새로운 열 벡터 ${\bf n}_i$ = ${\bf M}^{i-1} {\bf y}$를 정의한다. 열 벡터 ${\bf n}_i$로 구성한 행렬 $\bf N$은 $\bf T$의 역행렬이다.
(11)여기서 ${\bf Tn}_i$ = ${\bf TM}^{i-1}{\bf y}$ = ${\bf K}^{i-1} {\bf e}_1$ = ${\bf e}_i$이다. 따라서 ${\bf T}^{-1}$은 존재하며 ${\bf n}_i$로 공식화된다. 마지막 단계로 역행렬의 열 벡터 ${\bf n}_i$를 재귀적으로 계산한다.
(12a)여기서 $i$ = $2, 3, \cdots, n$; ${\bf n}_1$ = $\bf x$, ${\bf Tn}_i$ = ${\bf e}_i$, ${\bf e}_{i-1}$ = ${\bf J}{\bf e}_{n-i+2}$, $\bf JJ$ = $\bf I$, ${\bf y}^T$ = ${\bf d}^T ({\bf T}^{-1})^T$, $\bf T$는 직각 대칭 행렬(persymmetric matrix)이라서 $\bf T$ = ${\bf JT}^T {\bf J}$, ${\bf T}^{-1}$도 직각 대칭 행렬이다. 식 (12a)에서 얻은 마지막식의 행렬 곱을 직접 곱해서 더욱 간략화한다.
(12b)식 (12b)는 ${\bf n}_i$에 대해 재귀적이지만 동반 행렬의 단순 곱이라서, 식 (7d) 형태로 쉽게 계산된다.
______________________________
식 (5)에 정의한 순환 행렬 $\bf C$는 $a_{n-i}$ = $a_{-i}$를 만족하므로, $\bf d$ = $\bf 0$, $\bf y$ = $\bf 0$이 나온다. 이를 식 (7d)에 대입해서 역행렬 ${\bf C}^{-1}$를 유도한다.
(13)역행렬을 구성하는 원소는 $\bf x$의 순환 옮김이기 때문에, ${\bf C}^{-1}$는 역시 순환 행렬이다.
대칭 퇴플리츠 행렬 $\bf S$의 역행렬 표현식은 생각보다 유도가 까다롭다. 증명을 위해 식 (7a)에 나오는 열 벡터 $\bf y$를 $\bf x$로 나타낸다. 먼저 $\bf d$를 분해한 식의 해를 $\bf y$ = ${\bf y}_r - {\bf y}_i$로 둔다.
(14a)여기서 $\bf d$ = ${\bf d}_r - {\bf d}_i$이다. 해 ${\bf y}_i$ = ${\bf e}_1$을 ${\bf d}_i$ = ${\bf Sy}_i$에 넣어서 답을 검증한다. 다음 절차로 $\bf S$의 아래 행 벡터부터 고려해서 ${\bf d}_r$ 결과에 근접한 관계식을 도출한다.
(14b)여기서 $A_0$ = $a_1 x_{n-1} + a_2 x_{n-1} + \cdots + a_{n-1}x_1$이다. 열 벡터 ${\bf d}_r$을 정확히 만들기 위해 $\bf S$의 첫번째 행 벡터와 $\bf x$간의 곱을 더한다.
(14c)여기서 $B_0$ = $a_0 x_0 + A_0$이다. 해 $\bf y$ = ${\bf y}_r - {\bf y}_i$를 식 (7b)와 (7c)에 넣고 정리한다.
(15)식 (15)를 식 (7d)에 대입해서 최종적으로 ${\bf S}^{-1}$ 공식을 획득한다[1].
(16)여기서 원소간의 곱셈은 교환 법칙이 성립하므로[예를 들어, $x_0 x_1$ = $x_1 x_0$] 행렬 ${\bf L}^T$, $\bf U$의 곱도 ${\bf L}^T{\bf U}$ = ${\bf U}{\bf L}^T$처럼 교환 법칙이 생긴다. 순환 행렬처럼 대칭 퇴플리츠 행렬의 역행렬도 $\bf x$의 원소만으로 결정할 수 있다.
[참고문헌]
[1] L. Rodman and T. Shalom, "On inversion of symmetric Toeplitz matrices," SIAM J. Matrix Anal. Appl., vol. 13, no. 2, pp. 530–549, Apr. 1992.
[2] X.-G. Lv, T.-Z. Huang, "A note on inversion of Toeplitz matrices," Appl. Math. Lett., vol. 20, no. 12, pp. 1189–1193, Dec. 2007.
[다음 읽을거리]
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(1)
(3b)
(4)
(7)
(10)
(11)
(12)
(16)
(17)
(19a)
