선형대수(HYU)_16 판별식의 공식

4.3 Formulas For the Determinant

첫 번째 formular는 이미 전에 언급이 되었다. Row operation으로 $D$의 pivot을 구했을 때:

$A$가 invertible하면 $PA=LDU$, $detP=\pm 1$이다.
$$detA=\pm detLdetDdetU=\pm \text{ (product of the pivots)}$$

• $\pm$ 부호는 row exchange의 횟수에 따라 결정된다. (even or odd)
• Triangular factor는 $detL=detU=1$이고
• $detD=d_1\cdots d_n$

Example

$$\left[\begin{array}{ccccc}2& -1& & & \\ -1& 2& -1& & \\ & -1& 2& \cdot & \\ & & \cdot & \cdots & -1\\ & & & -1& 2\end{array}\right]=LDU=L\left[\begin{array}{ccccc}2& & & & \\ & 3/2& & & \\ & & 4/3& & \\ & & & \cdot & \\ & & & & (n+1)/n\end{array}\right]U$$

• 예시와 같은 matrix를 sparse matrix라고 한다.
• $detA=2\cdot (3/2)\cdot (4/3)\cdots (n+1/n)=n+1$

Determinant의 property 1-3으로 부터 일반적으로 잘 알려진 $n=2$, $n=3$인 square matrix의 determinant formula를 도출해보자.

• 우선, matrix의 row를 각 coordinate 방향의 vector로 분해한다.
  $$\left[\begin{array}{cc}a& b\end{array}\right]=\left[\begin{array}{cc}a& 0\end{array}\right]+\left[\begin{array}{cc}0& b\end{array}\right]and\left[\begin{array}{cc}c& d\end{array}\right]=\left[\begin{array}{cc}c& 0\end{array}\right]+\left[\begin{array}{cc}0& d\end{array}\right]$$
• Property 1 (property of linearity)을 각 row에 적용한다.
  $$\begin{array}{rl}\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|& =\left|\begin{array}{cc}a& 0\\ c& d\end{array}\right|+\left|\begin{array}{cc}0& b\\ c& d\end{array}\right|\\ & =\left|\begin{array}{cc}a& 0\\ c& 0\end{array}\right|+\left|\begin{array}{cc}a& 0\\ 0& d\end{array}\right|+\left|\begin{array}{cc}0& b\\ c& 0\end{array}\right|+\left|\begin{array}{cc}0& b\\ 0& d\end{array}\right|\\ & =ad-bc\end{array}$$
  • 두 개의 row가 동일한 coordinate 방향에 있으면, 즉 column에 zero vector가 있으면 그 matrix의 determinant는 0이 된다.
  • Determinant가 0이 되지 않기 위해서는 nonzero term이 모두 다른 column에 있어야 한다.
• $n$개의 nonzero determinant를 배분하는 방법은 $n!$개이다.
  • Example: 3 by 3 matrix의 경우 $3!=6$개의 determinants 존재
    $$\begin{array}{rl}\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{23}& a_{33}\end{array}\right|& =\left|\begin{array}{ccc}{a}_{11}& & \\ & a_{22}& \\ & & a_{33}\end{array}\right|+\left|\begin{array}{ccc}& a_{12}& \\ & & a_{23}\\ a_{31}& & \end{array}\right|+\left|\begin{array}{ccc}& & a_{13}\\ a_{21}& & \\ & a_{32}& \end{array}\right|\\ & +\left|\begin{array}{ccc}{a}_{11}& & \\ & & a_{23}\\ & a_{32}& \end{array}\right|+\left|\begin{array}{ccc}& a_{12}& \\ a_{21}& & \\ & & a_{33}\end{array}\right|+\left|\begin{array}{ccc}& & a_{13}\\ & a_{22}& \\ a_{31}& & \end{array}\right|\end{array}$$
• $a_{ij}$를 factoring out하면,
  $$\begin{array}{rl}\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{23}& a_{33}\end{array}\right|& =a_{11}{a}_{22}{a}_{33}\left|\begin{array}{ccc}1& & \\ & 1& \\ & & 1\end{array}\right|+a_{12}{a}_{23}{a}_{31}\left|\begin{array}{ccc}& 1& \\ & & 1\\ 1& & \end{array}\right|+a_{13}{a}_{21}{a}_{32}\left|\begin{array}{ccc}& & 1\\ 1& & \\ & 1& \end{array}\right|\\ & +a_{11}{a}_{23}{a}_{32}\left|\begin{array}{ccc}1& & \\ & & 1\\ & 1& \end{array}\right|+a_{12}{a}_{21}{a}_{33}\left|\begin{array}{ccc}& 1& \\ 1& & \\ & & 1\end{array}\right|+a_{13}{a}_{22}{a}_{31}\left|\begin{array}{ccc}& & 1\\ & 1& \\ 1& & \end{array}\right|\\ & =\sum _{\alpha ,\beta ,\gamma }{a}_{1\alpha }{a}_{2\beta }{a}_{3\gamma }(\text{det}{P}_{\alpha ,\beta ,\gamma })\end{array}$$

결과적으로 일반적인 n by n matrix의 determinants는
$$\text{Big Formula}\text{det}A=\sum _{\text{all }{P}^{\prime }s}(a_{1\alpha }{a}_{2\beta }\cdots a_{n\nu })\text{det}P$$

• n by n matrix의 계산은 number $(1,\dots ,n)$이 이룰 수 있는 모든 $n!$개의 permutation $(\alpha ,\dots ,\nu )$을 합산한다.
• $\text{det}P$는 row exchange 횟수에 따라 짝수번이면 $+1$, 홀수번이면 $-1$이 된다.

Property 3에 의하면 n by n matrix의 determinant는 first row인 $a_{11},a_{12},\dots ,a_{1n}$에 depend하다.

• 모든 $(a_{1\alpha }{a}_{2\beta }\cdots a_{n\nu })$ term중 $a_{11}$을 포함하는 경우를 생각해보자.

  • 첫 column($\alpha =1$)을 제외하면 남은 column은 $(2,\dots ,n)$이 이루는 순열 $(\beta ,\dots ,\nu )$이다.
  • 남은 term $(a_{2\beta }\cdots a_{n\nu })$을 하나의 coefficient로 합쳐 표현하면 위의 term을 $a_{11}{C}_{11}$와 같은 꼴로 나타낼 수 있다.
  • 이 때, $a_{11}$의 coefficient $C_{11}$은 row1과 column1이 제거된 sub-matrix의 determinant와 같다.

  $$\text{Cofactor of }{a}_{11}{C}_{11}=\sum (a_{2\beta }\cdots a_{n\nu })\text{det}P=\text{det(sub matrix of A)}$$

• 이와 같은 방식으로 모든 term을 나타내면
  $$\text{Cofactors along row 1}\text{det}A=a_{11}{C}_{11}+a_{12}{C}_{12}+\cdots +a_{1n}{C}_{1n}=\sum _{j=1}^n{a}_{ij}{C}_{ij}$$

Example

For 3 by 3 cases

$$\begin{array}{rl}\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{23}& a_{33}\end{array}\right|& =\left|\begin{array}{ccc}{a}_{11}& & \\ & a_{22}& a_{23}\\ & a_{23}& a_{33}\end{array}\right|+\left|\begin{array}{ccc}& a_{12}& \\ a_{21}& & a_{23}\\ a_{31}& & a_{33}\end{array}\right|+\left|\begin{array}{ccc}& & a_{13}\\ a_{21}& a_{22}& \\ a_{31}& a_{23}& \end{array}\right|\\ & =a_{11}(a_{22}{a}_{33}-a_{23}{a}_{32})+a_{12}(a_{23}{a}_{31}-a_{21}{a}_{33})+a_{13}(a_{21}{a}_{32}-a_{22}{a}_{31})\end{array}$$

Expansion of $\text{det}A$ in Cofactors

---

• 동일한 term에서 어떤 row나 column도 두 번 쓰일 수 없다.
• Cofactor $C_{1j}$를 만들 때 첫 번째 row와 j번째 column은 이미 $a_{ij}$가 차지하고 있다.
• 이는 Cofactor $C_{1j}$는 완전히 다른 column에만 연관(depend)이 있다는 것을 의미한다.
• Cofactor를 만드는 submatrix $M_{1j}$는 기존의 matrix에서 $row1$과 $columnj$를 제거해 만든다.

$$\text{Cofactors of row 1}{C}_{1j}=(-1{)}^{1+j}\text{det}{M}_{1j}$$

이를 확장해서 다른 어떤 $rowi$에도 적용할 수 있다.

• $row1$과 $rowi$를 exchange해서 증명 가능하다.

$$\begin{array}{c}\text{det}A=a_{i1}{c}_{i1}+a_{i2}{C}_{i2}+\cdots +a_{in}{C}_{in}\\ C_{ij}=(-1{)}^{i+j}\text{det}{M}_{ij}\end{array}$$

Exmaple

$$A4=\left[\begin{array}{cccc}2& -1& 0& 0\\ -1& 2& -1& 0\\ 0& -1& 2& -1\\ 0& 0& -1& 2\end{array}\right]$$

계산이 쉽도록 $a_{ij}=0$이 많은 $i$번째 row를 선택한다. 예시의 경우 $row1$

$$\begin{array}{rl}\text{det}{A}_4& =2\left|\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right|-(-1)\left|\begin{array}{ccc}-1& -1& 0\\ 0& 2& -1\\ 0& -1& 2\end{array}\right|\\ & =2\left|\begin{array}{ccc}2& -1& 0\\ -1& 2& -1\\ 0& -1& 2\end{array}\right|-\left|\begin{array}{cc}2& -1\\ -1& 2\end{array}\right|\\ & =2\cdot det{A}_3-det{A}_2=2(4)-3=5\end{array}$$

이 matrix에서는 $A_5,A_6,A_n$에서도 동일한 관계가 반복된다.

$$\text{Recursion by cofactors}det{A}_n=2(det{A}_{n-1})-det{A}_{n-2}$$