Determinant, 무엇을 결정(determine)한다는 말일까? 그 답을 찾기 위해서 우리는 the system of linear equations로 돌아가야 한다. Square matrix $A$에 대해서 $A \textbf{x} = \textbf{b}$라는 system이 주어져 있다. 이때 적절한 elementary row operation을 통해 $A$를 identity matrix $I$와 row-equivalent하도록 변형할 수 있는 경우가 존재할 수 있다. 그말인즉슨 $A$가 invertible하여서 사용한 elementary matrix들의 곱이 $A$의 inverse가 된다는 말이고, 역으로 어떻게 elementary row operation을 하여도 $I$와 row-equivalent하게 만들 수 없다면 $A$는 invertible하지 않다는 뜻이다.
Theorem 1
Theorem 1. Let $A$ be a square matrix. If the reduced row echelon form of $A$ is the identity matrix, then $A$ is invertible.
이를 확장하면 다음의 TFAE가 주어진다.
Theorem 2
Theorem 2. Let $A$ be a square matrix. Then the followings are equivalent:
(1) $A$ has a left inverse,
(2) $A \textbf{x} = \textbf{0}$ has the only solution $\textbf{x} = \textbf{0}$,
(3) $A$ is row-equivalent to the identity matrix,
(4) $A$ is a product of elementary matrices,
(5) $A$ is invertible,
(6) $A$ has a right inverse.
이 정리는 Gauss-Jordan elimination을 사용해 어떤 정사각행렬의 inverse를 구하는 방법을 제공한다. 예컨대 $E_1, ..., E_k$가 모두 $A$에 곱해져서 identity matrix를 만드는 elementary matrix라면 $$E_k \cdots E_1 A = I$$가 성립한다. 따라서 $$E_k \cdots E_1 [A I] = [I E_k \cdots E_1]$$이고, $E_k \cdots E_1 = A^{-1}$이다.
$2 \times 2$ 행렬의 예시를 살펴보자. $$A = \begin{pmatrix}
a & b \\
c & d
\end{pmatrix}$$의 inverse를 위에서 소개한 방법을 적용해 구하면 다음과 같이 주어진다. $$A^{-1} = \frac{1}{ad - bc} \begin{pmatrix}
d & -b \\
-c & a
\end{pmatrix}$$ 이때 $ad - bc$라는 값이 $0$이 된다면 위 식은 정의되지 않고, 실제로 계산하는 과정에서 이를 확인할 수 있다. 따라서 $ad - bc$라는 값이 $A$의 inverse가 존재하는지 그 여부를 "결정"한다고 생각할 수 있으므로, $2 \times 2$ 행렬의 determinant를 다음과 같이 정의한다.
Determinant of $2 \times 2 $ Matrices
Definition 1. For a $2 \times 2$ matrix $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$, the determinant of $A$ is defined as $$\det A = ad - bc.$$
이때 determinant는 다음의 성질들이 성립한다.
Remark.
(1) $\det \begin{pmatrix} a & b \\ c & d \end{pmatrix} = -\det \begin{pmatrix} c & d \\ a & b \end{pmatrix}$
(2) $\det \begin{pmatrix} ka + la' & kb + lb' \\ c & d \end{pmatrix} = k \det \begin{pmatrix} a & b \\ c & d \end{pmatrix} + l \det \begin{pmatrix} a' & b' \\ c & d \end{pmatrix}$
(3) $\det \begin{pmatrix} a & b \\ ka + c & kb + d \end{pmatrix} = \det \begin{pmatrix} a & b \\ c & d \end{pmatrix}$
즉 elementary operation을 행렬에 적용한 뒤 determinant의 결과는 위와 같이 주어지고, 어떤 한 행에 대해서 linear하다는 말이다.
이렇게 $2 \times 2$ 행렬의 determinant를 정의하고, 실제로 어떻게 계산할 수 있는지 살펴보았다. 이제 size를 늘려서 $3 \times 3, 4 \times 4$, 나아가 임의의 $n \times n$ 행렬에 대해서 determinant를 정의하는 일이 남았다. 상식적으로 $2 \times 2$ 행렬의 determinant가 일반적으로 가지는 성질을 더 큰 size의 determinant도 가져야 한다고 생각할 수 있으므로, 이 성질들을 근거로 determinant를 일반화하여 정의해보자.
n-Linear Function
Definition 2. A function $\delta : M_{n \times n}(F) \longrightarrow F$ is called an $n$-linear function if $\forall r \in \{1, ..., n\}$, we have $\delta \begin{pmatrix} a_1 \\ \vdots \\ a_{r-1} \\ u+kv \\ a_{r+1} \\ \vdots \\ a_n \end{pmatrix} = \delta \begin{pmatrix} a_1 \\ \vdots \\ a_{r-1} \\ u \\ a_{r+1} \\ \vdots \\ a_n \end{pmatrix} + k\delta \begin{pmatrix} a_1 \\ \vdots \\ a_{r-1} \\ u \\ a_{r+1} \\ \vdots \\ a_n \end{pmatrix}$
whenever $k \in F$ and $u, v, a_i \in F^n$.
Alternating
Definiton 3. An $n$-linear function $\delta : M_{n \times n}(F) \longrightarrow F$ is called alternating if $\delta(M)$ changes sign if any two rows of $M$ are interchanged.
Determinant
Definition 4. A function $\det : M_{n \times n}(F) \longrightarrow F$ is called a determinant if it satiesfies the followings:
(1) $\det$ is an $n$-linear function,
(2) $\det$ is alternating,
(3) $\det(I_n) = 1$.
그리고 이러한 함수는 유일하게 존재한다는 사실을 확인할 수 있다.
Theorem 3
Theorem 3. Let $n \in \mathbb{N}$. Then there uniquely exists a function $\det : M_{n \times n}(F) \longrightarrow F$ defined above.
따라서 determinant는 well-defined된 함수다. 이제 구체적으로 어떻게 determinant를 계산할 수 있는지 알아보자.
위 determinant의 정의에 의해 임의의 elementary matrix의 determinant는 쉽게 계산할 수 있다.
Remark. Let $E$ be an elementary matrix.
(Type 1) $\det E = k$ if $E$ is obtained from multiplying some row of $I$ by $k$.
(Type 2) $\det E = -1$ if $E$ is obtained from interchanging the adjacent rows of $I$.
(Type 3) $\det E = 1$ if $E$ is obtained from adding $k$ times some row of $I$ to another row of $I$.
Theorem 4
Lemma. Let $A$ be a matrix and $E$ be any elementary matrix of the same size as $A$. $\det (EA) = \det E \cdot \det A$.
Theorem 4. Let $A$ and $B$ be any matrices. Then the followings hold:
(1) If $A$ is a triangular matrix, then $\det A$ is the product of diagonal entries of $A$,
(2) $A$ is invertible if and only if $\det A \neq 0$,
(3) $\det (AB) = \det A \det B$,
(4) $\det A^t = \det A$,
(5) If $A$ has two idential rows, then $\det A = 0$.
따라서 우리는 임의의 행렬이 주어져 있을 때, 사실상 Gaussian elimination으로 기존 행렬을 변환시키고 그만큼의 determinant를 곱해줌으로써 행렬의 determinant를 계산할 수 있다.
앞서 우리는 $2 \times 2$ 행렬의 determinant를 closed form으로 깔끔하게 구해냈다. 이런 비슷한 공식을 더 큰 size에서도 찾을 수 있을까?
Determinant의 성질만 가지고 $3 \times 3$ 행렬의 determinant를 구해보자. $$A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \\ \Longrightarrow \det A = \det \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \\ = \det \begin{pmatrix} a_{11} & 0 & 0 \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} + \det \begin{pmatrix} 0 & a_{12} & 0 \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} + \det \begin{pmatrix} 0 & 0 & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \\ = \det \begin{pmatrix} a_{11} & 0 & 0 \\ 0 & a_{22} & 0 \\ 0 & 0 & a_{33} \end{pmatrix} + \det \begin{pmatrix} a_{11} & 0 & 0 \\ 0 & 0 & a_{23} \\ 0 & a_{32} & 0 \end{pmatrix} \\ + \det \begin{pmatrix} 0 & a_{12} & 0 \\ a_{21} & 0 & 0 \\ 0 & 0 & a_{33} \end{pmatrix} + \det \begin{pmatrix} 0 & a_{12} & 0 \\ a_{21} & 0 & 0 \\ 0 & 0 & a_{33} \end{pmatrix} \\ + \det \begin{pmatrix} 0 & 0 & a_{13} \\ a_{21} & 0 & 0 \\ 0 & a_{32} & 0 \end{pmatrix} + \det \begin{pmatrix} 0 & 0 & a_{13} \\ 0 & a_{22} & 0 \\ a_{31} & 0 & 0 \end{pmatrix} \\ = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{11}a_{23}a_{32} - a_{12} a_{21}a_{33} - a_{13}a_{22}a_{31}.$$ Elementary operation과 위에서 구한 elemetary matrix의 determinat를 적용하면 이러한 결과를 얻는다. 이때 주목할 점은 마지막 결과의 각 항은 $A$의 성분 세 개의 곱으로 이루어져 있는데, 각 성분의 첫 번째 number들의 배열은 모두 $1, 2, 3$이다. 그리고 두 번째 number의 배열은 $1, 2, 3$의 적절한 permutation이다.
위 결과는 $3 \times 3$ 행렬의 경우이지만, 동일한 과정을 임의의 $n \times n$ 행렬에 대해서도 사용할 수 있고, 결과는 analogous하게 나올 것이다. 따라서 우리는 permutation의 관점으로 determinant를 계산할 수 있고, 다음의 정리로 제시되어 있다.
Leibniz Formula
Theorem 5. For $A \in M_{n \times n}(F)$, $$\det A = \sum_{\sigma \in S_n} \text{sign}(\sigma) a_{1 \sigma(1)} \cdots a_{n \sigma(n)}.$$
Cofactor Expansion
위 예시의 마지막 결과만 가지고 오자. $$\det A \\ = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{11}a_{23}a_{32} - a_{12} a_{21}a_{33} - a_{13}a_{22}a_{31} \\ = a_{11} (a_{22}a_{33} - a_{23} a_{32}) - a_{12} (a_{21}a_{33} - a_{23}a_{31}) + a_{13} (a_{21} a_{32} - a_{22}a_{31})$$ 괄호 안의 값들은 각각 $A$에서 괄호 앞 성분이 위치해 있는 행과 열을 제거함으로 얻어진 행렬의 determinant이다.
Definition 5. Let $A = [a_{ij}] \in M_{n \times n}(F)$. Then $$A_{ij} = (-1)^{i + j} \det M_{ij}$$ is called the cofactor of the entry $a_{ij}$, where $M_{ij}$ is the submatrix obtained by deleting the $i$-th row and the $j$-th column. We call $M_{ij}$ the minor of the entry $a_{ij}$.
위의 $3 \times 3$ 행렬의 예시에서 우리는 처음 determinant의 $n$-linear property를 첫 번째 행에 대해서 적용시켜 계산했다. 그런데 첫 번째 행 뿐만 아니라 다른 행에 대해서도 동일한 계산을 할 수 있는데, 첫 번째 행으로 interchanging 해주고 부호만 바꿔주면 되기 때문이다. 따라서 위 정의를 사용해 determinant를 다시 작성하면 다음과 같다.
Theorem 6. Let $A = [a_{ij}] \in M_{n \times n}(F)$ and let $A_{ij}$ be the cofactor of $a_{ij}$. Then $$\det A = \sum_{j=1}^n a_{ij} A_{ij}$$ for each $1 \leq i \leq n$. We call this the cofactor expansion of $\det A$ along the $i$-th row.
그리고 $\det A = \det A^t$이므로 어떤 column에 대해서 똑같이 cofactor expansion을 사용해도 값은 변함이 없다.
Cramer's Rule
Lemma. For $A = [a_{ij}] \in M_{n \times n}(F)$ and the cofactor $A_{ij}$ of $a_{ij}$, $$a_{i1}A_{j1} + a_{i2}A_{j2} + \cdots + a_{in}A_{jn} = \begin{cases} \det A & \text{if } i = j \\ 0 & \text{if } i \neq j. \end{cases}$$
Proof. Let $B$ be a matrix obtained from $A$ by replacing the $j$-th row by a new row $x = [x_1 \cdots x_n]$. Then, along the $j$-th row, the cofactors of $B$ are the same as those of $A$. Now, we can choose $x$ to be the $j$-th row of $A$. Then clearly, $B = A$ and $\det B = \det A$.
For any $i, i \neq j$, if we choose $x$ to be the $i$-th row of $A$, then $\det B = 0$ because the two rows are the same. $\blacksquare$
Definition 6. Let $A = [a_{ij}] \in M_{n \times n}(F)$ and let $A_{ij}$ be the cofactor of $a_{ij}$. Then $$\begin{pmatrix} A_{11} & \cdots & A_{1n} \\ \vdots & \ddots & \vdots \\ A_{n1} & \cdots & A_{nn} \end{pmatrix}$$ is called the matrix of cofactors of $A$. Its transpose is called the adjugate of $A$ and is denoted by adj $A$.
위 정의로부터 $A \cdot \text{adj} A = (\det A) I$임을 알 수 있고, 따라서 $$A^{-1} = \frac{1}{\det A} \text{adj} A$$로 주어짐을 알 수 있다.
Cramer's Rule. Let $A \textbf{x} = \textbf{b}$ be a system of linear equations. If $A$ is invertible, $A \textbf{x} = \textbf{b}$ has the unique solution given by $$x_j = \frac{\det C_j}{\det A}, \quad j = 1, ..., n,$$ where $C_j$ is the matrix obtained from $A$ by replacing the $j$-th column with the column vector $\textbf{b}$.
Proof. We have $\textbf{x} = A^{-1} \textbf{b}$. Then $$\textbf{x} = \frac{1}{\det A} \begin{pmatrix} A_{11} & \cdots & A_{n1} \\ \vdots & \ddots & \vdots \\ A_{1n} & \cdots & A_{nn} \end{pmatrix} \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} \\ = \frac{1}{\det A} \begin{pmatrix} A_{11}b_1 + \cdots A_{n1} b_n \\ \vdots \\ A_{1n}b_1 + \cdots + A_{nn}b_n \end{pmatrix}$$ Thus $$x_j = \frac{1}{\det A}(A_{1j}b_1 + \cdots + A_{nj} b_n) = \frac{C_j}{\det A} \blacksquare$$