여기서는 간략하게 행렬의 characteristic polynomial을 계산하는 방법에 대해서 다룬다.


먼저 당연한 이야기부터. characteristic polynomial을 계산하면 행렬의 determinant 역시 계산할 수 있다.

$n \times n$ 행렬의 determinant를 계산하는데 걸리는 시간이 $\mathcal{O}(n^\omega)$라고 하자. 

현재 기술력으로는 $\omega \approx 2.373$ 정도임이 알려져 있다. (행렬 곱/행렬 역과 마찬가지)

그러니 기본적으로 기대할 수 있는 최적의 시간복잡도는 $\mathcal{O}(n^\omega)$이며, 실제로도 $\mathcal{O}(n^{\omega} \log n)$의 알고리즘이 존재한다.

관심이 있는 사람들은 krylov subspace와 Keller-Gehrig Algorithm을 찾아보면 된다. 난 모르겠다 ㅋㅋ


하지만 PS를 하는 입장에서나 실제로 계산을 하는 입장에서는, 일반적으로 행렬 연산들은 $\mathcal{O}(n^3)$으로 구현한다.

그러니 여기서는 목표를 $\mathcal{O}(n^3)$ 시간 안에 characteristic polynomial을 계산하는 것으로 하자.

또한, $\mathbb{F}_p$, $\mathbb{R}$, $\mathbb{C}$ 등 임의의 field에 대한 계산을 할 수 있도록 알고리즘을 생각해보도록 하자.

여기서 기본적으로 field의 크기는 크다고 가정을 하는데, field의 크기가 작은 경우에서도 아래의 내용이 적용된다. 약간의 머리를 더 쓰면 된다.


가장 쉬운 아이디어는 뭘까? 어쨌든 characteristic polynomial은 $n$차 다항식이니, $n$개의 점에서 다항식의 값을 각각 계산한 다음 Lagrange Interpolation을 덮어주면 된다. 다항식의 값을 한 번 계산하는 것은 쉽게 생각하면 determinant를 한 번 계산하는 것과 같으니, 총 $\mathcal{O}(n^4)$의 시간이 걸린다. 물론, interpolation은 간단하게 $\mathcal{O}(n^2)$에도 할 수 있으며 굳이 빡세게 하고 싶다면 $\mathcal{O}(n \log^2 n)$에도 된다. $n$을 하나 줄이는 것이 목표다.


어떻게 최적화를 할까? interpolation의 아이디어는 포기하기에는 너무 깔끔하다. 한 번 determinant를 계산하는데 $\mathcal{O}(n^2)$이 들도록 할 수는 없을까? 이를 위해서는 기존의 행렬과 similar 한 "예쁜 행렬"을 만들어주는 방법이 많이 사용된다. 가장 대표적인 예시는 역시 대각화. 행렬이 대각화가 된다면 그 자체로 characteristic polynomial의 계산은 끝이다. 하지만 대각화는 항상 가능한 것이 아니라는 것이 잘 알려져 있다. 또 다른 예시는 슈르 삼각화. 이 역시 가능하다면 그 자체로 끝난다. 이는 field가 algebraically closed field라면 (예를 들어, $\mathbb{C}$라면) 항상 가능하겠다. 하지만 우리가 다룰 대상은 훨씬 일반적이다. 이는 다르게 말하면 upper triangular보다 더 넓은 마음가짐으로 similar transformation 각도를 재야 한다는 뜻이다.


그래서 생각할 수 있는 형태는 Hessenberg Matrix다. 이는 결국 upper triangular인데 주대각선 바로 하나 아래의 대각선에도 nonzero element가 존재할 수 있는 형태의 행렬이다. 즉, $h_{i, j} = 0$ for all $i > j+1$를 만족하는 행렬이다. 이제 우리가 확인해야 하는 것은 두 가지다. 

첫 번째로, similar transformation을 통해서 Hessenberg 형태를 만들 수 있는 것이 보장되는가? 

두 번째로, Hessenberg 형태를 만들면 determinant의 계산이 $\mathcal{O}(n^2)$ 안에 되는가?


첫 번째부터 확인해보자. 우리는 Gaussian Elimination의 과정을 그대로 밟되, 목표를 Hessenberg 형태로 할 것이다.

첫 번째 column을 보자. 만약 $(2,1), (3,1), \cdots , (n,1)$에 있는 모든 원소가 $0$이라면, 다음 column으로 넘어간다.

이제 nonzero 원소가 있다고 하자. 그러면 Gaussian Elimination의 경우와 같이 $(2,1)$에 nonzero 원소를 하나 넣어줄 필요가 있다. $(k,1)$에 nonzero element가 있다고 하자. 그러면 우리가 해야하는 것은 $2$번째, $k$번째 을 swap하는 것이다. 이는 두 원소를 swap 하는 permutation matrix를 행렬 에 곱하는 것과 같다. 우리는 항상 similar transformation을 해야 하므로, 같은 permutation matrix의 역을 행렬 에 곱해야 한다. 이는 생각해보면 $2$번째, $k$번째 을 swap하는 것과 같다. 이렇게 해도 $(2,1)$에는 결국 nonzero element가 온다. 이 과정을 손으로 써보면, Hessenberg 형태의 묘미를 느낄 수 있다. 


자, 이제 $(2,1)$의 nonzero element를 가지고 $(3,1), (4,1), \cdots ,(n,1)$의 원소를 전부 $0$으로 만들어야 한다.

이는 각 $k \ge 3$에 대하여 $k$번째 에 $2$번째 의 배수를 더하는 것과 같다.

이는 $LU$ 분해를 생각해보면, 일종의 lower triangular matrix를 에 곱하는 것과 같다. 

역시 우리는 similar transformation을 적용해야 하므로, 이 행렬의 역을 에 곱해야 한다.

이는 식을 써보면 $2$번째 에 $k$번째 의 배수를 더하는 것과 같다. 정확히 어떤 계수를 넣어야 하는지는 직접 계산해보자.

이를 반복하면, $(3,1), \cdots , (n,1)$을 다 날릴 수 있다. 이제 이를 각 column에 대하여 순서대로 반복하자.


두 번째를 확인하자. Hessenberg 행렬에서 $\lambda I$ 형태의 행렬을 빼도 여전히 Hessenberg 행렬이다.

그러니, Hessenberg 행렬의 determinant를 $\mathcal{O}(n^2)$에 구할 수 있으면 된다.

그런데 이건 단순하게 Gaussian Elimination을 하면 된다. 실제로 행렬을 그려보고 생각하면 자명하다.


그러니 이 과정을 모두 합치면 $\mathcal{O}(n^3)$에 characteristic polynomial을 계산할 수 있다.

'수학 > 선형대수학' 카테고리의 다른 글

Fast Computation of Characteristic Polynomial  (0) 2020.05.28
"A rough guide to linear algebra" 후기  (2) 2019.12.20

책 소개 링크 // 책 링크


이번에 이 책을 읽게 된 계기는 크게 3가지다.


  • 수학 공부를 좀 하고 싶었다. 1학년 동안 수강한 수학 과목 중에서 내용이 새로웠던 과목이 선형대수학 2 하나여서 아쉬운 점이 많았다. 2학기에는 ICPC/Project Euler를 하면서 프로그래밍을 하는 시간이 더 많았고, 종강 직전에는 교양 과제를 마무리하느라 고생하다보니 수학 공부가 하고 싶어졌다. 이런 책이 있다는 사실은 오래 전부터 알고 있었고, 책 제본까지 이미 해두었던 상황이었다. 마침 선형대수학 2도 수강했으니, 이제 이 책을 읽을 수 있지 않을까 싶기도 했다.
  • 선형대수학에 대한 새로운 시각/직관을 얻고 싶었다. 책 소개 링크에 들어가서 저자의 글을 보면 대강 무슨 뜻인지 느낌을 알 수 있다. “correct abstract viewpoint of linear algebra”가 어떤 관점인지를 알고 싶었다. 선형대수학 2의 교재인 "선형대수와 군"에서도 철학이나 직관을 강조했고, 교재를 읽으면서 이 점이 굉장히 매력적이라고 생각했다. 이번에 읽은 책도 "correct viewpoint"를 잡기 위한 책이라고 소개가 되어 있으니 더 읽고 싶어졌다. 저자는 순수수학으로 진로를 잡을 게 아니면 굳이 필요가 없다고 적긴 했는데, 아무튼 내가 재밌으면 된 거 아닐까 싶어서 그냥 읽었다.
  • 현대대수학 입문 준비. 다음 1학기에 가능하면 현대대수학 수업을 들을 예정이다. 책의 내용 중 일부가 현대대수학 수업 내용과 겹친다. 다음 학기 수업을 위한 좋은 준비가 될 것 같아서 이 책을 읽게 되었다. 이인석 교수님의 "대수학" 책도 사긴 샀는데, 시간 문제상 방학 도중 읽을 것 같지는 않다. 그래도 현대대수학 언어는 많이 배워간 것 같아서 좋다.
배운 것도 많아서 좋다. "선형대수와 군"을 중간중간에 참고하면서 읽으면 여러모로 새롭게 얻을 수 있는 게 많은 것 같다.

현재 책에서 제대로 해결하지 못한 Exercise는 (2장 9절에 있는 경시대회 문제를 제외하면)

1. Four-Lemma와 Five-Lemma. 2.6.N.
2. skew-symmetric matrix에서 Pfaffian과 Determinant 사이의 관계를 증명하는 문제: 3.3.I. (b)
3. PID에서 free module의 submodule이 free임을 Zorn's Lemma로 보이는 문제: 4.3.E.
4. SVD의 Low-Rank Approximation에서의 활용을 증명하는 문제: 5.5.K. 

4번은 일반적인 vector space 및 inner product에서는 아직 못 풀고 \(\mathbb{R}^n\) 공간의 dot product에서만 풀었다. 
SVD만 나오면 행렬 생각이 자꾸 나서 문제인듯 하다. 그래도 1, 2, 3번은 제대로 시간 잡으면 해결할 수 있을 것 같다.
2번은 "선형대수와 군" 책에도 있는데, 얘는 풀이를 검색해도 설명을 못 찾겠다. Exterior Algebra 방식의 설명을 찾고 싶다.
  
아무튼 저 네 문제는 난이도도 있고 중요한 문제이기도 하니 나중에 풀면 블로그에 올릴 생각이다. 
UPD: 영원히 안 풀듯 ㅋㅋㅋㅋㅋㅋㅋㅋ

좋은 책을 읽을 수 있어서 저자에게 감사하다. 오타 찾아놓은거 기록했으니 나중에 책 다시 한 번 훑을 때 정리해서 보내야겠다.



'수학 > 선형대수학' 카테고리의 다른 글

Fast Computation of Characteristic Polynomial  (0) 2020.05.28
"A rough guide to linear algebra" 후기  (2) 2019.12.20
  1. mmath 2020.10.04 15:47

    안녕하세요 블로그 잘 보고있습니다.
    책 링크를 들어가도 책을 다운받을 수 없어서 그런데 혹시 책을 email로 보내주실 수 있으세요?