2024년 6월 11일 화요일

닮음 변환(Similarity Transformation)

[경고] 아래 글을 읽지 않고 "닮음 변환"을 보면 바보로 느껴질 수 있습니다.


연립 방정식을 행렬(matrix) 형태로 표현한 $\bf Ax$ = $\bf b$의 기저(basis)를 바꾸어서 더 편하게 계산하는 ${\bf A}'{\bf x}'$ = ${\bf b}'$의 방식을 생각한다.

                          (1)

여기서 $\bf P$는 역행렬(inverse matrix)이 존재하는 적당한 정방 행렬(square matrix)이다. 이때 등장하는 새로운 행렬 변환 ${\bf A}'$ = ${\bf P}^{-1}{\bf AP}$을 닮음 변환(similarity transformation)이 혹은 $\bf A$의 켤레화(conjugation)라 한다. 또한 행렬 $\bf A$와 ${\bf A}'$은 행렬식(determinant), 대각합(trace)고유치(eigenvalue), 특성 다항식(characteristic polynomial), 동반 행렬(companion matrix) 등을 포함한 행렬의 중요 특성이 동일하거나 유사해서 닮은 행렬(similar matrix)이라 부른다. 닮은 행렬의 대표적 예는 행렬 곱 $\bf AB$와 $\bf BA$이다.

                          (2)

여기서 $\bf P$ = $\bf A$이다. 그래서 두 행렬 곱은 닮아있지만, 일반적으로 교환 법칙이 성립하지 않아 동일하지 않다.
다른 관점으로 닮음 변환은 고유 분해(eigendecomposition)의 일반화이다. 고유 분해는 행렬의 대각화에 쓰이지만, 닮음 변환은 대각화(diagonalization)란 조건 없이 기저를 바꾸는 임의 행렬 $\bf P$의 곱으로만 정의하기 때문이다. 즉, 닮음 변환에서 $\bf A$가 대각 행렬(diagonal matrix)인 경우가 바로 고유 분해이다.

2024년 6월 8일 토요일

동반 행렬(Companion Matrix)

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


단일 다항식(monic polynomial: 최고차 항의 계수가 1인 다항식) $p(x)$의 계수를 마지막 열에 넣어서 만든 행렬 ${\bf K}(p)$는 $p(x)$와 함께 가는 행렬이란 의미로 동반 행렬(companion matrix)이라 부른다.

                          (1)

여기서 $c_i$는 $p(x)$의 계수이다. 다만 다항식과 행렬은 너무 다른 개념이라서, 어떤 측면에서 이 두 대상이 동반자 관계일까? 답은 고유치(eigenvalue)를 만드는 행렬식(determinant)에 있다.

[동반 행렬의 특성 다항식(characteristic polynomial)]

                          (2)

[증명]
동반 행렬의 행렬식 정의로 특성 다항식을 계산한다.

             (3)

여기서 $|{\bf A}|_{ij}$는 $i$행과 $j$열을 초과하는 원소를 모아서 정의한 행렬식이다.
______________________________

임의의 행렬 $\bf A$에 대해, $|x {\bf I} - {\bf K}(p) |$로 특성 다항식 $p(x)$를 만든다. 그러면 식 (1)을 이용해 $\bf A$의 동반 행렬로 ${\bf K}(p)$를 항상 생성할 수 있다. 동반 행렬과 $\bf A$는 동일한 특성 다항식 $p(x)$로 연결되어서 두 행렬의 고유치는 같다. 여기서 특성 다항식의 정의에 따라 $p(x)$의 근이 고유치이다.
또한 동반 행렬의 중요한 성질 중 하나는 닮음 변환(similarity transformation)의 불변성이다. 즉, 행렬 $A$와 닮은 행렬(similar matrix) $\bf B$ = ${\bf P}^{-1} {\bf A P}$는 $A$와 동일한 동반 행렬 및 특성 다항식을 가진다.

[닮은 행렬의 동반 행렬과 특성 다항식]

                          (4)

여기서 $\bf B$ = ${\bf P}^{-1} {\bf A P}$이다.

[증명]
닮은 행렬의 특성 다항식이 같아서, 이 다항식으로 만든 동반 행렬 ${\bf K}(p)$도 같아진다.
______________________________

행렬 $\bf A$의 동반 행렬을 구하기 어려운 경우, 식 (4)를 써서 상대적으로 계산이 쉬운 $\bf B$로 동반 행렬을 구하기도 한다. 


   1. 기본(basics)   

[기본 관계식]

                          (1.1)

여기서 첫째식의 첨자(index)는 $i$ = $1, 2, \cdots, n-1$; ${\bf e}_i$는 $i$번 표준 기저(standard basis)인 열 벡터[예를 들어, ${\bf e}_1$ = $[1~0~0~\cdots~0]^T$], $n$은 정방 행렬의 크기이다.

[증명]
동반 행렬과 표준 기저의 단순한 행렬 곱이므로, 좌변을 계산해서 우변과 비교한다.
______________________________

식 (1.1)의 첫째식은 식 (1)에 정의한 동반 행렬의 대각선 원소의 아래에 위치한 1의 의미를 표현한다. 이 값으로 인해 동반 행렬에 표준 기저를 곱하면, 그 다음 표준 기저가 차례로 얻어진다.


[다음 읽을거리]

2024년 5월 17일 금요일

퇴플리츠 행렬(Toeplitz Matrix)

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


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

독특한 원소 패턴을 가진 퇴플리츠 행렬(Toeplitz matrix)은 행이 증가함에 따라 [그림 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)이다.
퇴플리츠 행렬은 상삼각과 하삼각 행렬(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)

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

                  (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.

[다음 읽을거리]