Determinant and Trace
Determinant
Determinants(행렬식)은 선형대수학에서 매우 중요한 개념입니다. 행렬식은 분석을 위한 수학적 도구이면서 선형연립방정식의 솔루션입니다. 행렬식은 오직 정사각 행렬 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 에서만 정의됩니다. 이 교재에서는 행렬식을 $\text{det}(\boldsymbol{A})$ 또는 $|\boldsymbol{A}|$ 로 표현합니다.
\[\text{det}(\boldsymbol{A}) = \begin{vmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&&\ddots&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn} \end{vmatrix} \tag{4.1}\]정사각 행렬 $\boldsymbol{A}$ 의 행렬식(determinant) 은 $\boldsymbol{A}$ 를 실수(real number)로 mapping하는 함수로 볼 수 있습니다. General한 $n\times n$ 행렬에 대한 행렬식의 정의를 살펴보기 전에 몇 가지 특별한 행렬에 대한 행렬식의 정의를 살펴보도록 하겠습니다.
Example 4.1 (Testing for Matrix Invertibility)
\[\boldsymbol{A}^{-1} = \frac{1}{a_{11}a_{22} - a_{12}a_{21}}\begin{bmatrix}a_{22}&-a_{12}\\-a_{21}&a_{11}\end{bmatrix} \tag{4.2}\]
정사각 행렬 $\boldsymbol{A}$ 가 역행렬이 존재한다고 가정하겠습니다. 2.2.2장을 통해 우리는 언제 역행렬이 존재하는지 이미 알고 있습니다. 만약 $\boldsymbol{A}$ 가 $1\times1$ 행렬이라면, 즉, 단순 scalar number라면 $\boldsymbol{A} = a \Longrightarrow \boldsymbol{A}^{-1} = \frac{1}{a}$ 입니다. 따라서, $a \neq 0$ 이라면, $a\frac{1}{a} = 1$ 을 만족합니다.
이번에는 $2\times2$ 행렬의 경우를 살펴보도록 하겠습니다. Definition 2.3의 역행렬 정의에 의해, 우리는 $\boldsymbol{AA}^{-1} = \boldsymbol{I}$ 라는 것을 알고 있습니다. 그러므로 식 (2.4)에 의해서 $\boldsymbol{A}$ 의 역행렬은 다음과 같습니다.그러므로, 오직
\[a_{11}a_{22} - a_{12}a_{21} \neq 0 \tag{4.3}\]인 경우에만 $\boldsymbol{A}$ 의 역행렬이 존재합니다.
\[\text{det}(\boldsymbol{A}) = \begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix} = a_{11}a_{22} - a_{12}a_{21} \tag{4.4}\]
여기서 (4.3)이 $\boldsymbol{A} \in \mathbb{R}^{2 \times 2}$ 의 determinant(행렬식) 입니다.
Example 4.1에서는 행렬식과 역행렬의 존재 유무의 관계를 보여주고 있습니다. 아래의 theorem은 위 내용을 $n\times n$ 행렬에 일반화하고 있습니다.
Theorem 4.1. 모든 정사각 행렬(square matrix) $\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 에 대해, 오직 $\text{det}(\boldsymbol{A}) \neq 0$ 일 때 $\boldsymbol{A}$ 의 역행렬이 존재합니다(invertible).
크기가 작은 행렬에 대해서는 명시적으로 행렬식을 표현하는데, $n = 1$ 인 경우에는 다음과 같습니다.
\[\text{det}(\boldsymbol{A}) = \text{det}(a_{11}) = a_{11} \tag{4.5}\]$n = 2$ 인 경우는 다음과 같습니다 (식 (4.4)와 동일).
\[\text{det}(\boldsymbol{A}) = \begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix} = a_{11}a_{22} - a_{12}a_{21} \tag{4.6}\]$n = 3$ 인 경우는 Sarrus’ rule이라고 알려져 있으며, 다음과 같습니다.
\[\begin{align*}\begin{vmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{vmatrix} = &a_{11}a_{22}a_{33} + a_{21}a_{32}a_{13} + a_{31}a_{12}a_{23} \\&- a_{31}a_{22}a_{13} - a_{11}a_{32}a_{23} - a_{21}a_{12}a_{33} \end{align*} \tag{4.7}\]위 식을 쉽게 기억하려면 행렬의 삼중곱(triple products)를 기억하면 됩니다.
정사각 행렬 $\boldsymbol{T}$ 에 대해, $i > j$ 를 만족하는 모든 요소 $T_{ij} = 0$ 일 때, 행렬 $\boldsymbol{T}$ 를 upper-triangular matrix 라고 합니다. 즉, 대각 요소 아래 부분은 모두 0인 행렬을 의미합니다. 이와 비슷하게 lower-triangular matrix 는 대각 요소 위에 있는 모든 요소들이 0인 행렬로 정의합니다. 삼각 행렬(triangular matrix) $\boldsymbol{T} \in \mathbb{R}^{n\times n}$ 의 경우, 행렬식은 대각 요소들의 곱이며 다음과 같습니다.
\[\det(\boldsymbol{T}) = \prod_{i=1}^nT_{ii} \tag{4.8}\]Example 4.2 (Determinants as Measures of Volume)
행렬식은 n개의 벡터 집합으로부터 $\mathbb{R}^n$ 에 있는 object로 mapping으로 간주할 때 조금 더 이해하기 쉬울 수 있습니다. 그리고 행렬식 $\det(\boldsymbol{A})$ 는 행렬 $\boldsymbol{A}$ 의 열들로 형성된 n-차원 평행육면체(parallelepiped)의 signed volume(부호가 있는 부피) 입니다.
$n=2$ 일 때, 행렬의 열들은 아래 그림과 같이 평행사변형(parallelogram)을 형성합니다.두 벡터 사이의 각도가 작아질수록 평행사변형의 넓이도 줄어든다는 것을 알 수 있습니다. 두 벡터 $\boldsymbol{b}, \boldsymbol{g}$ 는 행렬 $\boldsymbol{A} = \begin{bmatrix}\boldsymbol{b},\boldsymbol{g}\end{bmatrix}$ 의 columns를 형성합니다. 그리고 행렬 $\boldsymbol{A}$ 의 행렬식의 절대값은 평행사변형의 넓이가 됩니다. 만약 두 벡터가 선형 종속(linearly dependent)이라면, $\boldsymbol{b} = \lambda\boldsymbol{g}, \lambda \in \mathbb{R}$ 이고 평행사변형을 형성하지 않으며 넓이는 0입니다. 이와 반대로, 선형 종속(linearly independent)이라면 두 벡터는 canonical basis 벡터 $\boldsymbol{e}_1, \boldsymbol{e}_2$ 의 배수이며 각각은 $\boldsymbol{b} = \begin{bmatrix}b\\0\end{bmatrix}, \boldsymbol{g} = \begin{bmatrix}0\\g\end{bmatrix}$ 로 쓸 수 있으며, 행렬식은 $\begin{vmatrix}b&0\\0&g\end{vmatrix} = bg - 0 = bg$ 입니다.
행렬식의 부호(sign)은 표준 basis $(\boldsymbol{e}_1,\boldsymbol{e}_2)$ 에 대해 spanning vector $\boldsymbol{b},\boldsymbol{g}$ 의 방향을 가리킵니다. 벡터의 순서를 $\boldsymbol{g},\boldsymbol{b}$ 로 바꾸면 $\boldsymbol{A}$ 의 열이 바뀌게 되고 부호는 반대가 됩니다. 위의 평행사변형 그림에서 음영 처리된 영역의 방향이 반대가 됩니다.
이는 넓이 = 높이 x 너비의 공식과 유사한 것을 확인할 수 있습니다. 이러한 직관을 고차원으로 확장할 수 있는데, $\mathbb{R}^3$ 에서 3개의 벡터 $\boldsymbol{r},\boldsymbol{b},\boldsymbol{g}$ 를 고려해보도록 하겠습니다. 이 벡터들은 평행육면체의 edges를 span합니다. 즉, 아래 그림과 같이 평행사변형 면을 가진 육면체가 됩니다.
그리고 $3\times3$ 행렬 $\lbrack\boldsymbol{r},\boldsymbol{b},\boldsymbol{g}\rbrack$ 의 행렬식의 절대값은 이 평행육면체의 부피입니다. 따라서, 행렬식은 행렬을 구성하는 열 벡터로 형성된 signed volume을 측정하는 함수로 동작합니다.
3개의 선형 독립인 벡터 $\boldsymbol{r},\boldsymbol{g},\boldsymbol{b}$ 가 다음과 같이 주어졌다고 가정해봅시다.
\[\boldsymbol{r} = \begin{bmatrix}2\\0\\-8\end{bmatrix}, \boldsymbol{g} = \begin{bmatrix}6\\1\\0\end{bmatrix}, \boldsymbol{b} = \begin{bmatrix}1\\4\\-1\end{bmatrix} \tag{4.9}\]세 벡터는 다음과 같이 행렬의 열로 구성될 수 있고,
\[\boldsymbol{A} = \lbrack\boldsymbol{r},\boldsymbol{g},\boldsymbol{b}\rbrack = \begin{bmatrix}2&6&1\\0&1&4\\-8&0&-1\end{bmatrix} \tag{4.10}\]부피는 다음과 같이 계산할 수 있습니다.
\[V = |\det(\boldsymbol{A})| = 186 \tag{4.11}\]즉, determinant는 해당 행렬을 linear transformation으로 볼 때, 변환되는 area(or volume)가 어떻게 scaling 되는지를 알려주는 factor이며, determinant의 부호(sign)은 방향을 의미합니다. 이와 관련한 강의(link)에서 determinant를 시각적으로 잘 보여주고 있으니, 참조바랍니다 !
지금까지는 $n=1,2,3$ 인 경우의 행렬식만을 살펴봤는데, $n\times n$ 행렬의 행렬식을 계산하려면 일반화된 알고리즘이 필요합니다. 아래의 theorem 4.2는 $n\times n$ 행렬의 행렬식 계산을 $(n-1)\times(n-1)$ 행렬의 행렬식 계산으로 축소(치환, reduction) 합니다. Theorem 4.2를 Laplace expansion이라고 하며, 이를 $2\times2$ 행렬의 행렬식을 구할 때까지 반복 수행하여 $n\times n$ 행렬의 행렬식을 계산합니다.
Theorem 4.2 (Laplace Expansion). 행렬 $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 이 있을 때, 모든 $j = 1,\dotsc,n$ 에 대하여
\[\det(\boldsymbol{A}) = \sum_{k=1}^n(-1)^{k+j}a_{kj}\det(\boldsymbol{A}_{k,j}) \tag{4.12}\]
- Exapnsion along column $j$
\[\det(\boldsymbol{A}) = \sum_{k=1}^n(-1)^{k+j}a_{jk}\det(\boldsymbol{A}_{j,k}) \tag{4.13}\]
- Expansion along row $j$
여기서 $\boldsymbol{A}_{k,j} \in \mathbb{R}^{(n-1)\times(n-1)}$ 는 k행과 j열을 제거하여 얻은 $\boldsymbol{A}$ 의 submatrix 입니다.
예제를 통해 살펴보도록 합시다.
Example 4.3 (Laplace Expansion)
\[\boldsymbol{A} = \begin{bmatrix}1&2&3\\3&1&2\\0&0&1\end{bmatrix} \tag{4.14}\]
다음 행렬의 행렬식을 계산해봅시다.첫 번째 행을 따라 laplace expansion을 적용하면, 식 (4.13)에 의해 다음과 같이 식을 전개할 수 있습니다.
\[\begin{align*} \begin{vmatrix}1&2&3\\3&1&2\\0&0&1\end{vmatrix} = &(-1)^{1+1}\cdot1\begin{vmatrix}1&2\\0&1\end{vmatrix} \\ &+(-1)^{1+2}\cdot2\begin{vmatrix}3&2\\0&1\end{vmatrix} + (-1)^{1+3}\cdot3\begin{vmatrix}3&1\\0&0\end{vmatrix} \end{align*} \tag{4.15}\]식 (4.6)에 의해 모든 $2\times2$ 행렬의 행렬식을 계산하면 다음과 같이 $\boldsymbol{A}$ 의 행렬식을 얻을 수 있습니다.
\[\det(\boldsymbol{A}) = 1(1-0)-2(3-0)+3(0-0) = -5 \tag{4.16}\]검증을 위해 식 (4.7)의 Sarrus’ rule을 사용하여 행렬식을 구해보면 다음과 같이 (4.16)과 동일하다는 것을 알 수 있습니다.
\[\det(\boldsymbol{A}) = 1\cdot1\cdot1+3\cdot0\cdot3+0\cdot2\cdot2-0\cdot1\cdot3-1\cdot0\cdot2-3\cdot2\cdot1 = 1-6=-5 \tag{4.17}\]
$\boldsymbol{A} \in \mathbb{R}^{n\times n}$ 에 대한 행렬식은 다음과 같은 속성들을 가지고 있습니다.
- 행렬곱의 행렬식은 각 행렬의 대응되는 행렬식의 곱과 같습니다, $\det(\boldsymbol{AB}) = \det(\boldsymbol{A})\det(\boldsymbol{B})$ .
- 행렬을 변환하여도 행렬식은 변하지 않습니다, $\det(\boldsymbol{A}) = \det(\boldsymbol{A}^\top)$ .
- 행렬 $\boldsymbol{A}$ 가 invertible 하다면(regular), $\det(\boldsymbol{A}^{-1}) = \frac{1}{\det(\boldsymbol{A})}$ 을 만족합니다.
- Similar matrices (Definition 2.22) 에서 행렬식은 같습니다. 그러므로, linear mapping $\Phi : V \rightarrow V$ 에 대한 모든 변환 행렬 $\boldsymbol{A}_\Phi$ 는 동일한 행렬식을 갖습니다. 따라서, linear mapping의 basis change에도 행렬식은 변하지 않습니다.
- 행렬의 한 행/열의 multiple을 다른 행/열에 더해도 $\det(\boldsymbol{A})$ 는 변하지 않습니다 (가우스 소거법을 통해 행렬을 echelon form으로 변환하더라도 determinant는 변하지 않음).
- 행렬을 $\lambda \in \mathbb{R}$ 로 scaling하면, 그 행렬의 determinant는 $\lambda^n$ 을 곱한 것과 같습니다, $\det(\lambda\boldsymbol{A}) = \lambda^n\det(\boldsymbol{A})$ .
- 두 행/열을 swap하면 $\det(\boldsymbol{A})$ 의 부호가 바뀝니다.
위 속성 중 마지막 3개의 속성 때문에, 가우스 소거법(gaussian elimination)을 사용해 $\boldsymbol{A}$ 를 row-echelon form으로 변환하여 $\det(\boldsymbol{A})$ 를 계산할 수 있습니다. $\boldsymbol{A}$ 가 triangular form이 될 때까지 가우스 소거법을 적용하면, (4.8)에 의해 대각 요소들의 곱으로 간단히 행렬식을 계산할 수 있습니다.
Theorem 4.3. 정사각 행렬(square matrix) $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 의 $\text{rk}(\boldsymbol{A}) = n$ 이면, $\det(\boldsymbol{A}) \neq 0$ 입니다. 즉, 오직 full rank 일 때만, $\boldsymbol{A}$ 는 invertible 합니다.
손으로 직접 계산하던 시절에는 invertibility 여부를 분석하는데 행렬식 계산이 필수적이었습니다. 하지만 머신러닝에서 현대적인 접근 방법은 직접적인 수치적 방법을 사용합니다. 예를 들어, 2장에서 역행렬은 가우스 소거법으로 구할 수 있습니다. 따라서, 가우스 소거법을 통해 행렬식을 구할 수 있습니다.
행렬식(Determinant)는 이어지는 내용들에서 중요한 역할을 하는데, 특히 4.2장에서 characteristic polynomial(특성 다항식)의 eigenvalue(고윳값)과 eigenvectors(고유벡터)에 대해 배울 때 중요합니다.
Trace
Definition 4.4. 정사각 행렬 $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 의 trace(대각합)는 다음과 같이 정의됩니다.
\[\text{tr}(\boldsymbol{A}) := \sum_{i=1}^na_{ii} \tag{4.18}\]즉, trace는 행렬 $\boldsymbol{A}$ 의 대각 성분의 합입니다.
Trace는 다음의 속성들을 만족합니다.
- $\text{tr}(\boldsymbol{A}+\boldsymbol{B}) = \text{tr}(\boldsymbol{A}) + \text{tr}(\boldsymbol{B}) \text{ for } \boldsymbol{A},\boldsymbol{B} \in \mathbb{R}^{n\times n}$
- $\text{tr}(\alpha\boldsymbol{A}) = \alpha\text{tr}(\boldsymbol{A}), \alpha \in \mathbb{R} \text{ for }\boldsymbol{A}\in\mathbb{R}^{n\times n}$
- $\text{tr}(\boldsymbol{I}_n) = n$
- $\text{tr}(\boldsymbol{AB}) = \text{tr}(\boldsymbol{BA}) \text{ for } \boldsymbol{A}\in\mathbb{R}^{n\times k}, \boldsymbol{B}\in\mathbb{R}^{k\times n}$
행렬곱의 trace의 속성은 더 일반적입니다. 구체적으로, cyclic permutations 아래서 trace는 변하지 않습니다. 즉, 다음의 식을 만족합니다.
\[\text{tr}(\boldsymbol{AKL}) = \text{tr}(\boldsymbol{KLA}) \tag{4.19}\]이 속성은 임의의 갯수의 행렬곱에 일반화될 수 있습니다. (4.19)의 특별 케이스로 두 벡터 $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}^n$ 에 대한 다음의 식입니다.
\[\text{tr}(\boldsymbol{xy}^\top) = \text{tr}(\boldsymbol{y}^\top\boldsymbol{x}) = \boldsymbol{y}^\top\boldsymbol{x} \in \mathbb{R} \tag{4.20}\]$V$ 가 vector sapce이고, linear mapping $\Phi : V \rightarrow V$ 가 주어졌을 때, 이 mapping의 trace는 $\Phi$ 의 matrix representation의 trace를 사용하여 정의할 수 있습니다. $V$ 의 basis가 주어졌을 때, $\Phi$ 를 transformation matrix을 사용하여 표현할 수 있습니다. 그러면, $\Phi$ 의 trace는 $\boldsymbol{A}$ 의 trace라는 것을 알 수 있습니다. $V$ 의 다른 basis가 있고, 대응되는 transformation matrix $\boldsymbol{B}$ 는 $\boldsymbol{S}^{-1}\boldsymbol{AS}$ 형태의 basis change(2.7.2장)을 통해 얻을 수 있습니다. 그리고 대응되는 $\Phi$ 의 trace는 다음과 같습니다.
\[\text{tr}(\boldsymbol{B}) = \text{tr}(\boldsymbol{S}^{-1}\boldsymbol{AS}) \overset{(4.19)}= \text{tr}(\boldsymbol{ASS}^{-1}) = \text{tr}(\boldsymbol{A}) \tag{4.21}\]따라서, linear mapping의 matrix representation은 basis에 의해 변하지만(즉, basis에 종속적이지만), linear mapping $\Phi$ 의 trace는 basis에 독립적입니다.
이번에는 determinant와 trace를 square matrix를 특성화하는 함수로 다루었습니다. 이를 하나로 묶으면 다항식의 term으로 행렬 $\boldsymbol{A}$ 를 설명하는 중요한 방정식을 정의할 수 있습니다.
Definition 4.5 (Characteristic Polynomial). $\lambda \in \mathbb{R}$ 과 square matrix $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ 에 대해, 다음의 식을
\[\begin{align*} p_{\boldsymbol{A}}(\lambda) &:= \det(\boldsymbol{A}-\lambda\boldsymbol{I}) \tag{4.22a} \\ &= c_0 + c_1\lambda + c_2\lambda^2 + \cdots + c_{n-1}\lambda^{n-1} + (-1)^n\lambda^n \tag{4.22b} \end{align*}\]$\boldsymbol{A}$ 의 characteristic polynomial(특성 다항식)이라고 합니다.
\[\begin{align*} c_0 &= \det(\boldsymbol{A}) \tag{4.23} \\ c_{n-1} &= (-1)^{n-1}\text{tr}(\boldsymbol{A}) \tag{4.24} \end{align*}\]
특성 다항식 (4.22a)를 통해 eigenvalue와 eigenvectors를 구할 수 있는데 이는 다음 장에서 살펴보도록 하겠습니다.