퇴플리츠 행렬(Toeplitz Matrix)

[경고] 아래 글을 읽지 않고 "퇴플리츠 행렬"을 보면 바보로 느껴질 수 있습니다.

1. 행렬

2. 동반 행렬

[그림 1] 색깔 조각으로 표현한 퇴플리츠 행렬(출처: wikipedia.org)

독특한 원소 패턴을 가진 퇴플리츠 행렬(Toeplitz matrix) $\mathbf{T}$는 행이 증가함에 따라 [그림 1]처럼 대각선 원소의 왼쪽과 오른쪽 부분이 순차적으로 돌아가는 모양을 가진다. 이를 $2n-1$개의 퇴플리츠 상수(Toeplitz constant) $a_i$로 정의한다.

                          (1a)

                          (1b)

여기서 $i$ = $1,2\cdots ,n$ 및 $j$ = $1,2\cdots ,n$; $T_{ij}$는 퇴플리츠 행렬 $\mathbf{T}$의 $i$행 $j$열 원소, $\mathbf{T}$의 차원(dimension)은 $n\times n$이다. 퇴플리츠 행렬은 반대각선(anti-diagonal)에 대해 대칭이라서 직각 대칭 행렬(persymmetric matrix)의 범주에 속한다. 또한 식 (1)처럼 대각선을 따라가는 원소는 항상 상수이므로, 퇴플리츠 행렬의 다른 이름은 대각 상수 행렬(diagonal-constant matrix)이다. 대각선 기준으로 값이 상수인 퇴플리츠 행렬에 대비되게, 반대각선 방향으로 놓인 원소가 상수인 행렬은 한켈 행렬(Hankel matrix) $\mathbf{H}$로 이름 붙인다.

                          (1c)

                          (1d)

여기서 한켈 행렬의 구성 원소를 체계적으로 보려면 첫 행 벡터[$a_0,a_1,\cdots ,a_{n-1}$]에서 시작해 마지막 열 벡터[$a_n,a_{n+1},\cdots ,a_{2n-2}$]까지 따라간다. 한켈 행렬은 자동적으로 대칭 행렬이 된다. 또한 교환 행렬(exchange matrix) $\mathbf{J}$를 통해 $\mathbf{H}$ = $\mathbf{T}\mathbf{J}$처럼 퇴플리츠 행렬과 한켈 행렬은 서로 연결된다.

퇴플리츠 행렬은 상삼각과 하삼각 행렬(upper and lower triangular matrices)로 구성된다.

                  (2)

여기서 $\mathbf{I}$는 항등 행렬(identity matrix), $\mathbf{L}$과 $\mathbf{U}$는 각각 $\mathbf{T}/a_0$의 상삼각과 하삼각 행렬 부분이다. 삼각 행렬 $\mathbf{L}$과 $\mathbf{U}$는 다시 퇴플리츠 행렬에 속한다. 대칭 퇴플리츠 행렬(symmetric Toeplitz matrix) $\mathbf{S}$는 행렬 곱과 합의 형태로 분해할 수 있다.

                          (3a)

                          (3b)

                          (3c)

여기서 $\mathbf{S}$는 대칭 행렬(symmetric matrix), $a_{-i}$ = $a_i$, $(\cdot {)}^T$는 전치 행렬(transpose)이다. 식 (3c)에 나타난 행렬 곱 $\mathbf{L}{\mathbf{L}}^T$은 전형적인 대칭 행렬이다. 대칭 퇴플리츠 행렬은 대칭과 직각 대칭이 함께 나타나는 쌍대칭 행렬(bisymmetric matrix)이다.

대칭 행렬의 역행렬은 다시 대칭 행렬이므로, 식 (3c)처럼 $\mathbf{S}$의 역행렬 ${\mathbf{S}}^{-1}$을 표현한다[1]. 역행렬의 정확한 증명은 식 (16)에 제시한다.

                          (4)

여기서 $\mathbf{X}$와 $\mathbf{Y}$는 $\mathbf{L}$과 같은 하삼각 행렬, $x_0$은 0이 아닌 적절한 상수이다. 역행렬의 원소 $B_{ij}$는 원래 행렬의 여인자(cofactor) $C_{ij}$에 연결되어서 $B_{ij}$는 다음 성질을 갖는다.

• 일반적으로 $C_{ii}$ $\ne$ $C_{jj}$ ($i\ne j$): 같을 수 있지만 보통 다름
• 쌍대칭 행렬의 역행렬은 쌍대칭성을 가지므로, 여인자 $C_{ij}$가 다른 값은 전체 원소에서 ◥◤ 위치에만 있음
• 역행렬 ${\mathbf{S}}^{-1}$의 독립된 원소 개수[$B_{ij}$의 개수]는 $(n+1{)}^2/4$[$n$: 홀수] 혹은 $n(n+2)/4$[$n$: 짝수]이므로, $\mathbf{X}$와 $\mathbf{Y}$는 $\mathbf{L}$ 구조의 하삼각 행렬로 선택할 수 있음[∵ 독립된 원소 $B_{ij}$는 전체 행렬 기준으로 ◥◤에 분포함]

대칭 퇴플리츠 행렬과 다르게, 행 번호가 커질 때 원소를 오른쪽으로 이동시키면서 순환 편이 혹은 전환(circular shift)을 적용한 행렬은 순환 행렬(circulant matrix) 혹은 더 정확히 순환 퇴플리츠 행렬(circulant Toeplitz matrix)이라 한다.

                          (5)

여기서 퇴플리츠 상수 $a_{-i}$ = $a_{n-i}$이다.

요상하게 정의한 퇴플리츠 행렬이 푸리에 변환(Fourier transform)과 만나는 지점은 길쌈(convolution)이다. 퇴플리츠 행렬과 열 벡터의 곱으로 이산 길쌈(discrete convolution) $(f\ast g{)}_m$을 정의한다.

                          (6)

이산 길쌈 $(f\ast g{)}_m$과 입력 신호인 $f_m$을 알면, 퇴플리츠 행렬의 역행렬을 식 (7d)처럼 구해서 또 다른 입력인 $g_m$을 결정할 수 있다.

퇴플리츠 역행렬(Toeplitz inverse matrix) ${\mathbf{T}}^{-1}$은 퇴플리츠 행렬 $\mathbf{T}$로 만든 일부 연립 방정식의 해만 알아도 일의적으로 정해진다.

[퇴플리츠 역행렬] [2]

퇴플리츠 행렬 $\mathbf{T}$로 만든 열 벡터 $\mathbf{x}$, $\mathbf{y}$의 원소로 퇴플리츠 역행렬 ${\mathbf{T}}^{-1}$을 생성할 수 있다.

                          (7a)

                          (7b)

                          (7c)

                          (7d)

여기서 $\mathbf{x}$ = $[x_0{x}_1\cdots x_{n-1}{]}^T$, $\mathbf{y}$ = $[y_0{y}_1\cdots y_{n-1}{]}^T$, ${\mathbf{e}}_i$ = $[0\cdots 010\cdots 0{]}^T$는 $i$번 정규 직교 열 벡터(orthonormal column vector) 혹은 표준 기저(standard basis), ${\mathbf{e}}_i$에서 $i$번째 원소만 $1$이고 나머지는 모두 $0$, ${\mathbf{e}}_1$ = $[100\cdots 0{]}^T$, $\mathbf{d}$ = $[0,a_{n-1}-a_{-1},a_{n-2}-a_{-2}$, $\cdots$, $a_2-a_{-n+2},a_1-a_{-n+1}{]}^T$, $\mathbf{I}$는 항등 행렬이다.

[증명]

동반 행렬(companion matrix) $\mathbf{K}$와 퇴플리츠 행렬 $\mathbf{T}$로 만든 교환 법칙의 차이 $\mathbf{K}\mathbf{T}-\mathbf{T}\mathbf{K}$는 1행과 $n$열에만 값이 있고 나머지 원소는 모두 $0$으로 나타나므로, 다음 항등식이 성립한다.

                  (8a)

                  (8b)

여기서 $\mathbf{J}$는 반전치(anti-transpose) 관계를 만드는 교환 행렬(exchange matrix)이다. 식 (8b)에 식 (7b)를 대입해서 $\mathbf{T}$를 인수로 빼낸다.

                  (9)

식 (9)의 둘째식에 $\mathbf{x}$를 곱해서 단위 기저 벡터(unit basis vector) ${\mathbf{e}}_i$의 표현식을 구한다.

                  (10)

여기서 $j$ = $0,1,\cdots ,n-1$; 동반 행렬의 성질에 따라 $\mathbf{K}{\mathbf{e}}_i$ = ${\mathbf{e}}_{i+1}$이 성립한다. 식 (10)에 등장하는 $\mathbf{M}$의 거듭제곱과 $\mathbf{y}$로 새로운 열 벡터 ${\mathbf{n}}_i$ = ${\mathbf{M}}^{i-1}\mathbf{y}$를 정의한다. 열 벡터 ${\mathbf{n}}_i$로 구성한 행렬 $\mathbf{N}$은 $\mathbf{T}$의 역행렬이다.

                  (11)

여기서 ${\mathbf{T}\mathbf{n}}_i$ = ${\mathbf{T}\mathbf{M}}^{i-1}\mathbf{y}$ = ${\mathbf{K}}^{i-1}{\mathbf{e}}_1$ = ${\mathbf{e}}_i$이다. 따라서 ${\mathbf{T}}^{-1}$은 존재하며 ${\mathbf{n}}_i$로 공식화된다. 마지막 단계로 역행렬의 열 벡터 ${\mathbf{n}}_i$를 재귀적으로 계산한다.

                 (12a)

여기서 $i$ = $2,3,\cdots ,n$; ${\mathbf{n}}_1$ = $\mathbf{x}$, ${\mathbf{T}\mathbf{n}}_i$ = ${\mathbf{e}}_i$, ${\mathbf{e}}_{i-1}$ = $\mathbf{J}{\mathbf{e}}_{n-i+2}$, $\mathbf{J}\mathbf{J}$ = $\mathbf{I}$, ${\mathbf{y}}^T$ = ${\mathbf{d}}^T({\mathbf{T}}^{-1}{)}^T$, $\mathbf{T}$는 직각 대칭 행렬(persymmetric matrix)이라서 $\mathbf{T}$ = ${\mathbf{J}\mathbf{T}}^T\mathbf{J}$, ${\mathbf{T}}^{-1}$도 직각 대칭 행렬이다. 식 (12a)에서 얻은 마지막식의 행렬 곱을 직접 곱해서 더욱 간략화한다.

                  (12b)

식 (12b)는 ${\mathbf{n}}_i$에 대해 재귀적이지만 동반 행렬의 단순 곱이라서, 식 (7d) 형태로 쉽게 계산된다.

______________________________

식 (5)에 정의한 순환 행렬 $\mathbf{C}$는 $a_{n-i}$ = $a_{-i}$를 만족하므로, $\mathbf{d}$ = $\mathbf{0}$, $\mathbf{y}$ = $\mathbf{0}$이 나온다. 이를 식 (7d)에 대입해서 역행렬 ${\mathbf{C}}^{-1}$를 유도한다.

                          (13)

역행렬을 구성하는 원소는 $\mathbf{x}$의 순환 옮김이기 때문에, ${\mathbf{C}}^{-1}$는 역시 순환 행렬이다.

대칭 퇴플리츠 행렬 $\mathbf{S}$의 역행렬 표현식은 생각보다 유도가 까다롭다. 증명을 위해 식 (7a)에 나오는 열 벡터 $\mathbf{y}$를 $\mathbf{x}$로 나타낸다. 먼저 $\mathbf{d}$를 분해한 식의 해를 $\mathbf{y}$ = ${\mathbf{y}}_r-{\mathbf{y}}_i$로 둔다.

                  (14a)

여기서 $\mathbf{d}$ = ${\mathbf{d}}_r-{\mathbf{d}}_i$이다. 해 ${\mathbf{y}}_i$ = ${\mathbf{e}}_1$을 ${\mathbf{d}}_i$ = ${\mathbf{S}\mathbf{y}}_i$에 넣어서 답을 검증한다. 다음 절차로 $\mathbf{S}$의 아래 행 벡터부터 고려해서 ${\mathbf{d}}_r$ 결과에 근접한 관계식을 도출한다.

                  (14b)

여기서 $A_0$ = $a_1{x}_{n-1}+a_2{x}_{n-1}+\cdots +a_{n-1}{x}_1$이다. 열 벡터 ${\mathbf{d}}_r$을 정확히 만들기 위해 $\mathbf{S}$의 첫번째 행 벡터와 $\mathbf{x}$간의 곱을 더한다.

                  (14c)

여기서 $B_0$ = $a_0{x}_0+A_0$이다. 해 $\mathbf{y}$ = ${\mathbf{y}}_r-{\mathbf{y}}_i$를 식 (7b)와 (7c)에 넣고 정리한다.

                  (15)

식 (15)를 식 (7d)에 대입해서 최종적으로 ${\mathbf{S}}^{-1}$ 공식을 획득한다[1].

                          (16)

여기서 원소간의 곱셈은 교환 법칙이 성립하므로[예를 들어, $x_0{x}_1$ = $x_1{x}_0$] 행렬 ${\mathbf{L}}^T$, $\mathbf{U}$의 곱도 ${\mathbf{L}}^T\mathbf{U}$ = $\mathbf{U}{\mathbf{L}}^T$처럼 교환 법칙이 생긴다. 순환 행렬처럼 대칭 퇴플리츠 행렬의 역행렬도 $\mathbf{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. 이산 푸리에 변환