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

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

$\newcommand{adj}{\operatorname{adj}}$어떤 행렬에 대한 계산을 필요로 하는 소스코드를 작성중이라 해보자. 이제 코딩을 하던 중에 어떤 반복문을 작성해야 하는데, 일단 행렬 $A_n$이 주어져 있고 이 행렬 $A_n$의 행렬식(determinant)역행렬을 계산했다고 하자. 이제 이 반복문에서 행렬이 계수(rank)가 1인 행렬 $\mathbf{u}_n \mathbf{v}_n^\T$에 의해 $A_{n+1} = A_n + \mathbf{u}_n \mathbf{v}_n^\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}^\T$에 의해 갱신되었을 때의 행렬식을 비교적 빠르게 구하는 방법을 알려주는 행렬식 보조정리(matrix determinant lemma)에 대해서 알아볼 것이다. 이 새로운 행렬의 역행렬을 구하는 셔먼-모리슨 공식(Sherman–Morrison formula)에 대해서는 다음 글에서 천천히 다뤄보도록 하자.

 

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

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

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

 

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

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

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

 

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

\[ \begin{pmatrix} I & \mathbf{0} \\ \mathbf{y}^\T & 1 \end{pmatrix} \begin{pmatrix} I + \mathbf{x} \mathbf{y}^\T & \mathbf{x} \\ \mathbf{0}^\T & 1 \end{pmatrix} \begin{pmatrix} I & \mathbf{0} \\ -\mathbf{y}^\T & 1 \end{pmatrix} = \begin{pmatrix} I & \mathbf{x} \\ \mathbf{0}^\T & 1 + \mathbf{y}^\T \mathbf{x} \end{pmatrix}. \]

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

\[ \det(I + \mathbf{x} \mathbf{y}^\T) = 1 + \mathbf{y}^\T \mathbf{x} \]

를 얻는다.

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

\begin{align*} \det(A + \mathbf{u}\mathbf{v}^\T) &= \det(A (I + A^{-1} \mathbf{u} \mathbf{v}^\T)) \\[6px] &= \det(A) \det(I + A^{-1} \mathbf{u} \mathbf{v}^\T) \\[6px] &= \det(A) (1 + \mathbf{v}^\T A^{-1} \mathbf{u}). \end{align*}

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

 

 

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

 

따름정리.

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

\[ \det(A + \mathbf{u}\mathbf{v}^\T) = \det(A) + \mathbf{v}^\T \adj(A) \mathbf{u}. \]

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

 

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

\begin{align*} \det(A + \mathbf{u}\mathbf{v}^\T) &= \det(A) (1 + \mathbf{v}^\T A^{-1} \mathbf{u}) \\[6px] &= \det(A) + \det(A) \mathbf{v}^\T A^{-1} \mathbf{u} \\[6px] &= \det(A) + \mathbf{v}^\T \big( \det(A) A^{-1} \big) \mathbf{u} \\[6px] &= \det(A) + \mathbf{v}^\T \adj(A) \mathbf{u}. \end{align*}

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

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

\begin{align*} \det(A + \mathbf{u}\mathbf{v}^\T) &= \lim_{n \to \infty} \det(A_n + \mathbf{u}\mathbf{v}^\T) \\[6px] &= \lim_{n \to \infty} \det(A_n) + \mathbf{v}^\T \adj(A_n) \mathbf{u} = \det(A) + \mathbf{v}^\T \adj(A) \mathbf{u} \end{align*}

가 성립한다..

 

 

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

\[ A = \begin{pmatrix} \alpha & 1 & 1 & \cdots & 1 \\ 1 & \alpha & 1& \cdots & 1 \\ 1 & 1 & \alpha & \cdots & 1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & 1 & \cdots & \alpha \end{pmatrix} \]

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

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

\begin{align*} \det(A) &= \det((\alpha-1)I + \mathbf{e} \mathbf{e}^\T) \\[6px] &= \det( (\alpha-1)I) \big(1 + \mathbf{e}^\T ((\alpha-1)I)^{-1} \mathbf{e} \big) \\[6px] &= (\alpha-1)^n \det(I) \left( 1 + \frac{1}{\alpha-1} \mathbf{e}^\T \mathbf{e} \right) \\[6px] &= (\alpha-1)^n \left( 1 + \frac{n}{\alpha - 1} \right) \\[6px] &= (\alpha-1)^{n-1} (\alpha + n - 1) \end{align*}

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