Fast Computation of Characteristic Polynomial

여기서는 간략하게 행렬의 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을 계산할 수 있다.