행렬식 보조정리(Matrix Determinant Lemma)

$$어떤 행렬에 대한 계산을 필요로 하는 소스코드를 작성중이라 해보자. 이제 코딩을 하던 중에 어떤 반복문을 작성해야 하는데, 일단 행렬 $A_n$이 주어져 있고 이 행렬 $A_n$의 행렬식(determinant)역행렬을 계산했다고 하자. 이제 이 반복문에서 행렬이 계수(rank)가 1인 행렬 ${\mathbf{u}}_n{\mathbf{v}}_n^{\mathsf{T}}$에 의해 $A_{n+1}=A_n+{\mathbf{u}}_n{\mathbf{v}}_n^{\mathsf{T}}$로 갱신되었다고 한다면 (즉, 행렬 $A_n$이 rank one update가 되었다면), 이 새로운 행렬 $A_{n+1}$의 행렬식과 역행렬을 어떻게 하면 비교적 빠르게 구할 수 있을까?

물론 $A_{n+1}$의 행렬식과 역행렬을 직접 구할 수도 있다. 하지만 행렬식이나 역행렬을 구하는 계산복잡도(computational complexity)가 일반적으로 $O(n^3)$ 정도이기 때문에, 각각의 반복문에서 새로운 행렬 $A_{n+1}$의 행렬식과 역행렬을 매번 구해야만 한다면, 그만큼 코딩의 처리 속도가 늦어지게 될 것이다. 하지만, 현재 행렬 $A_n$의 행렬식과 역행렬을 미리 알고 있다는 가정 하에, 새롭게 갱신된 행렬 $A_{n+1}$의 행렬식과 역행렬을 $A_n$의 행렬식과 역행렬을 이용하여 표현할 수 있는 방법이 있다면, 계산복잡도를 상당히 줄일 수 있을 것이다.

이번 글에서는 먼저 주어진 행렬 $A$에 대하여, $A$가 계수가 $1$인 행렬 $\mathbf{u}{\mathbf{v}}^{\mathsf{T}}$에 의해 갱신되었을 때의 행렬식을 비교적 빠르게 구하는 방법을 알려주는 행렬식 보조정리(matrix determinant lemma)에 대해서 알아볼 것이다. 이 새로운 행렬의 역행렬을 구하는 셔먼-모리슨 공식(Sherman–Morrison formula)에 대해서는 다음 글에서 천천히 다뤄보도록 하자.

행렬식 보조정리(Matrix Determinant Lemma)

먼저 다음의 두 사실을 증명 없이 받아 들이기로 하자.

1. 두 행렬의 곱의 행렬식은 두 행렬의 행렬식의 곱과 같다: 임의의 행렬 $A,B\in {\mathbb{R}}^{n\times n}$에 대하여,
   $$det(AB)=det(A)det(B).$$
2. 임의의 행렬 $A\in {\mathbb{R}}^{m\times m}$, $B\in {\mathbb{R}}^{m\times n}$, $C\in {\mathbb{R}}^{n\times m}$, $D\in {\mathbb{R}}^{n\times n}$와 영행렬 $O\in {\mathbb{R}}^{m\times n}$에 대하여,
   $$det\left(\begin{array}{cc}A& O\\ C& D\end{array}\right)=det(A)det(D)=det\left(\begin{array}{cc}A& B\\ O^{\mathsf{T}}& D\end{array}\right).$$

정리. 행렬식 보조정리(Matrix Determinant Lemma)

$A\in {\mathbb{R}}^{n\times n}$가 가역행렬(invertible matrix)이고, $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^n$가 열벡터라 하자. 그러면 다음 등식이 성립한다.

$$det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})=det(A)(1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u}).$$

증명. $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$가 임의의 열벡터이고 $\mathbf{0}\in {\mathbb{R}}^n$이 영벡터라 하자. 그러면 직접 계산을 통해 아래의 등식이 성립함을 간단히 확인할 수 있다.

$$\left(\begin{array}{cc}I& \mathbf{0}\\ {\mathbf{y}}^{\mathsf{T}}& 1\end{array}\right)\left(\begin{array}{cc}I+\mathbf{x}{\mathbf{y}}^{\mathsf{T}}& \mathbf{x}\\ {\mathbf{0}}^{\mathsf{T}}& 1\end{array}\right)\left(\begin{array}{cc}I& \mathbf{0}\\ -{\mathbf{y}}^{\mathsf{T}}& 1\end{array}\right)=\left(\begin{array}{cc}I& \mathbf{x}\\ {\mathbf{0}}^{\mathsf{T}}& 1+{\mathbf{y}}^{\mathsf{T}}\mathbf{x}\end{array}\right).$$

이제 위 등식의 양변에 행렬식 연산을 적용하자. 그러면 좌변의 첫 행렬과 마지막 행렬은 (대각 원소들이 모두 $1$인 삼각 행렬이므로) 행렬식 $1$을 갖는다. 또한 좌변의 가운데 행렬의 행렬식은 $det(I+\mathbf{x}{\mathbf{y}}^{\mathsf{T}})$임을 알 수 있다. 또한 우변의 행렬식은 $1+{\mathbf{x}}^{\mathsf{T}}\mathbf{y}$와 같으므로, 이를 종합하면

$$det(I+\mathbf{x}{\mathbf{y}}^{\mathsf{T}})=1+{\mathbf{y}}^{\mathsf{T}}\mathbf{x}$$

를 얻는다.

이제 임의의 가역행렬 $A\in {\mathbb{R}}^{n\times n}$와 열벡터 $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^n$에 대하여,

$$\begin{array}{rl}det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})& =det(A(I+A^{-1}\mathbf{u}{\mathbf{v}}^{\mathsf{T}}))\\ & =det(A)det(I+A^{-1}\mathbf{u}{\mathbf{v}}^{\mathsf{T}})\\ & =det(A)(1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u}).\end{array}$$

따라서 위 정리가 성립한다.

위 정리로부터 다음의 따름 정리를 얻는다.

따름정리.

$A\in {\mathbb{R}}^{n\times n}$가 임의의 행렬이고 (꼭 가역행렬이 아니어도 된다), $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^n$가 열벡터라 하자. 그러면 다음 등식이 성립한다.

$$det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})=det(A)+{\mathbf{v}}^{\mathsf{T}}\mathrm{adj}(A)\mathbf{u}.$$

이 때, $\mathrm{adj}(A)$는 $A$의 딸림행렬(adjoint matrix)를 나타낸다.

증명. 먼저 $A$가 가역행렬이라고 가정하자. 그러면 $det(A)A^{-1}=\mathrm{adf}(A)$이므로,

$$\begin{array}{rl}det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})& =det(A)(1+{\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u})\\ & =det(A)+det(A){\mathbf{v}}^{\mathsf{T}}{A}^{-1}\mathbf{u}\\ & =det(A)+{\mathbf{v}}^{\mathsf{T}}(det(A)A^{-1})\mathbf{u}\\ & =det(A)+{\mathbf{v}}^{\mathsf{T}}\mathrm{adj}(A)\mathbf{u}.\end{array}$$

따라서 임의의 가역행렬 $A$에 대하여 위 따름정리가 성립한다.

만약 $A$가 가역행렬이 아니라면, $A$를 가역행렬들의 수열 $(A_n)$의 극한으로 생각할 수 있다. 이제 딸림행렬을 하나의 함수로 이해해 보자. 즉, 함수 $\mathrm{adj}:{\mathbb{R}}^{n\times n}\to {\mathbb{R}}^{n\times n}$에 대하여, 행렬 $A$의 함숫값 $\mathrm{adj}(A)$는 각 원소가 $A$의 여인수(cofactor)들로 이루어진 행렬히다. 이 때, 각각의 여인수들은 $A$의 $(n-1)\times (n-1)$ 소행렬(submatrix)의 행렬식에 $1$ 또는 $-1$이 곱해진 형태이기 때문에, 모두 다항함수라 생각할 수 있다. 따라서 $\mathrm{adj}(A)$의 각 원소들은 $A$의 원소들에 대한 다항함수의 형태로 수어지기 때문에, $\mathrm{adj}$는 연속함수임을 알 수 있다. 따라서 $A_n\to A$일 때, $\mathrm{adj}(A_n)\to \mathrm{adj}(A)$가 성립하고,

$$\begin{array}{rl}det(A+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})& =\underset{n\to \mathrm{\infty }}{lim}det(A_n+\mathbf{u}{\mathbf{v}}^{\mathsf{T}})\\ & =\underset{n\to \mathrm{\infty }}{lim}det(A_n)+{\mathbf{v}}^{\mathsf{T}}\mathrm{adj}(A_n)\mathbf{u}=det(A)+{\mathbf{v}}^{\mathsf{T}}\mathrm{adj}(A)\mathbf{u}\end{array}$$

가 성립한다.

예제. $\alpha \ne 1$, $\alpha \ne 1-n$을 만족하는 임의의 실수 $\alpha$에 대하여,

$$A=\left(\begin{array}{ccccc}\alpha & 1& 1& \cdots & 1\\ 1& \alpha & 1& \cdots & 1\\ 1& 1& \alpha & \cdots & 1\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& 1& 1& \cdots & \alpha \end{array}\right)$$

가 가역행렬임을 증명하여라.

풀이. $I\in {\mathbb{R}}^{n\times n}$이 단위행렬, $\mathbf{e}\in {\mathbb{R}}^n$가 모든 성분이 $1$인 열벡터라 하자. 그러면 $A=(\alpha -1)I+\mathbf{e}{\mathbf{e}}^{\mathsf{T}}$와 같이 나타낼 수 있다. 이제 ${\mathbf{e}}^{\mathsf{T}}\mathbf{e}=n$이라는 사실을 이용하면

$$\begin{array}{rl}det(A)& =det((\alpha -1)I+\mathbf{e}{\mathbf{e}}^{\mathsf{T}})\\ & =det((\alpha -1)I)(1+{\mathbf{e}}^{\mathsf{T}}((\alpha -1)I{)}^{-1}\mathbf{e})\\ & =(\alpha -1{)}^{n}det(I)(1+\frac{1}{\alpha -1}{\mathbf{e}}^{\mathsf{T}}\mathbf{e})\\ & =(\alpha -1{)}^n(1+\frac{n}{\alpha -1})\\ & =(\alpha -1{)}^{n-1}(\alpha +n-1)\end{array}$$

여기서 $\alpha \ne 1$, $\alpha \ne 1-n$이므로, $det(A)\ne 0$이고 따라서 $A$는 가역행렬이다.