Properties of Determinants

그동안은 Rectangular Matrix에 집중해왔다.

이젠 Square Matrix에 관련된 내용을 다뤄보자.

Determinant를 다루는 이유는 여러가지가 있지만, 제일 중요한 것은 Eigenvalue이다.

Determinant

행렬식은 Square Matrix에서만 정의된다.

Determinant notation:
det \(A\), \(|A|\)

행렬식은 행렬에 대한 많은 정보를 압축한다.

det.이 0이면 singular matrix이고,
0이 아니면 invertible matrix이다.

그 외에도 더 많은 정보를 담고있다.

prop 1

det \(I = 1\)

prop 2

Exchange rows:
reverse sign of determinant

P: Permutation matrix
det P=1, even # of row exchanges
det P=-1, odd # of row exchanges

prop 3-1

하나의 row에 스칼라 t를 곱하면, det.는 t배가 된다.

prop 3-2

하나의 row벡터에 다른 벡터를 더하면, 그 벡터들을 기준으로 det을 나눠, 그 det들의 합으로 나타낼 수 있다.

3-1과 3-2를 합쳐, row에 대해 Linear Combination이 적용 된다는 것을 확인할 수 있다.

즉 determinant함수는 Linear Function이다.

그렇지만 다음과 같은 선형성은 아니다.
det(A+B) != det(A) + det(B)

각각의 row에 대해서만 선형성을 띈다.

prop 4

two equal rows:
determinant = 0

row exchange를 해보면, 같은 row끼리 exchange하면 부호가 달라져야하는데, 같은 row끼리 exchange한 결과는 행렬이 같다.
즉 같은 행렬에 대한 det이 부호가 달라도, 같아지려면 0이 되어야 한다.

prop 5

\(row_k - l*row_i\):
determinant doesn’t change!

소거(elimination)과정에 determinant는 변하지 않는다.

prop 3-2과 3-1를 통해 확인할 수 있다.

그러나 row exchange의 경우 부호 확인해야한다.

prop 6

Row of zeros:
det(A)=0

zero row가 하나라도 있으면 det.은 0이된다.
prop 3-1을 생각해보자.

prop 7

triangular matrix의 det.은 대각 성분의 곱만으로 계산할 수 있다.

prop 5를 통해 elimination을 하여 rref로 만들어보자.
이 때 소거과정에서 row exchange의 경우 부호 확인해야한다.

A가 singular matrix가 아니라면, determinant는 대각 원소들의 곱으로 계산할 수 있으며, 결과가 0이 아니게 된다.

prop 8

when A is singular: A=0
when A is invertible: A!=0

Full rank가 아니면 소거과정에서 zero row가 발생하고, prop 6에 의해 0이 된다.
Full rank라면 소거 후 대각 성분이 0이 아니게 되므로, prop 7에 의해 0이 아니게된다.

이제 특성을 이용해 2x2 행렬의 determinant를 유도해보자.

elimination:
\(A= \begin{bmatrix} a & b \\ c & d \\ \end{bmatrix} = \begin{bmatrix} a & b \\ c-\frac{c}{a}a & d-\frac{c}{a}b \\ \end{bmatrix} = \begin{bmatrix} a & b \\ 0 & d-\frac{c}{a}b \\ \end{bmatrix} =U\)

이제 대각 성분을 곱해보자.
ad-bc가 나온다.

prop 9

det AB=(det A)(det B)

덧셈에 대한 선형성은 없었지만, 특이하게 곱에대한 선형성은 존재한다.

이는 매우 유용하다. 이를 이용해 역행렬의 det을 쉽게 구할 수 있다.

\(A^{-1}A=I\)
\((det A^{-1})(det A)=1\)

\[(det A^{-1})=\frac{1}{(det A)}\]

만약 A의 역행렬이 존재하지 않으면? 그 역행렬에 대한 행렬식도 1/0 꼴이 되므로 정의할 수 없게 된다.

det \(A^2\) = \((detA)^2\)

n개의 row에 대해서는,
det \(2A\) = \(2^ndetA\)

prop 10

\(det(A^T)=det(A)\)

row exchange뿐만 아니라 column exchange에 대해서도 부호가 바뀐다.

영행렬에 대해서 생각해볼 수도 있고,
LU Decomposition을 이용해 유도해볼 수도 있다.

Determinant and Cofactor

Determinant Formulas

행렬식을 실제로 계산하는 방법을 알아보자.

Determinant split

행렬식의 계산을 분리(split)를 통해 더 간단하게 해보자.

prop 1에서 우린 단위 행렬의 determinant가 1이며, prop 2에선 row exchange가 det.의 부호를 바꾼다고 했다.

prop 3을 이용하면 다음과 같이 분리하는 것이 가능하다.
\(\begin{vmatrix} a & b \\ c & d \\ \end{vmatrix} = \begin{vmatrix} a & 0 \\ c & d \\ \end{vmatrix} + \begin{vmatrix} 0 & b \\ c & d \\ \end{vmatrix}\)

이렇게 나누어도 determinant는 같다.
한번 더 분리할 수 있다.
\(\begin{vmatrix} a & b \\ c & d \\ \end{vmatrix} = \begin{vmatrix} a & 0 \\ c & d \\ \end{vmatrix} + \begin{vmatrix} 0 & b \\ c & d \\ \end{vmatrix}\)
\(= \begin{vmatrix} a & 0 \\ c & 0 \\ \end{vmatrix} + \begin{vmatrix} a & 0 \\ c & d \\ \end{vmatrix} + \begin{vmatrix} 0 & b \\ c & 0 \\ \end{vmatrix} + \begin{vmatrix} 0 & b \\ 0 & d \\ \end{vmatrix}\)

마지막 줄에서 첫번째와 네번째 행렬이 singular matrix인 것을 알 수 있다.
Singular matrix인 경우 determinant가 0이므로, 가운데의 두 det.만을 이용해 계산하면 된다.

이러한 분리 과정을 통해 계산식을 더 간단히 하는 것이 가능하다.

ad-bc가 어떻게 나오는지 생각해보자.

그러면 원소를 중심으로 row와 column에 오직 자신만 존재하는 determinant만 0이 아니게 된다.

Big formula

nxn 모양의 행렬에 모두 적용할 수 잇는 일반적인 determinant 공식이다.

nxn 행렬에서 0이 아닌 행렬식의 수는 n!개이다.(전체 케이스는 \(n^n\)개)

행렬식을 쪼갠 식 중에서 0이 아닌 살아 남는 식들은 바로 치환 행렬(permutation matrix) 형태의 식이다.

이 때 절반은 부호가 +, 나머지 절반은 부호가 -가 된다.

Cofactor

Cofactor를 이용해 Big formula를 분할할 수 있다.

Factor와 Cofactor는 n by n의 determinant를 한 단계 작은 크기인 (n-1) by (n-1)의 determinant로 표현할 수 있게 한다.

Factor는 \(a_{ij}\), 즉 행렬의 한 원소에 해당한다. 그러나 determinant 분리를 할때 간단하게 하기 위해 주로 첫번째 row를 전부 factor로 고른다.

Cofactor를 정의하면,

cofactor of \(a_{ij}=C_{ij}\)
+- det n-1 matrix with row i, col j removed
i+j=even, +
i+j=odd, -

즉, \(C_{ij}\)는 ith row와 jth column을 제거한 (n-1) by (n-1) 행렬에 대한 determinant를 의미한다.

이렇게 표현할 수도 있겠다.
\(C_{ij}=(-1)^{i+j}D, where D is determinant of n-1 matrix with row i, col j removed from A\)

\[\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{vmatrix} = \begin{vmatrix} a & b \\ c & d \end{vmatrix}\]

이는 다음과 같다.
\(a_{11}C_{11} + a_{12}C_{12} = ad+b(-c)\)

4 by 4의 예제는 링크에서 확인
Link

복잡한 식으로 계산할 필요 없이 더 작은 행렬의 determinant로 분리하면서 풀어나가는 과정을 확인할 수 있다.

**시험 칠때 4 by 4는 시험에 꼭 나오는듯하다. **

Determinant and Inverse Matrix

Determinant with Inverse Matrix

고등학교때 배운건 이렇게 배웠음.

\[\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix}\]

이 식의 정체는 다음과 같다.
\(\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}^{-1} = \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c & a \\ \end{bmatrix}\)
\(A^{-1}=\frac{1}{det(A)}C^{T}\cdots (1)\)

우변은 cofactor matrix의 transpose를 determinant로 나누어 준 것이다.

Gauss-Jordan 방식으로 Inverse Matrix 구하는 것을 Numerical Method라고 하고,
이 방식으로 구하는 것을 Algebraic Method라고 한다.

결국 우리는 어떤 임의의 정방행렬의 역행렬에 대한 공식(Formula)를 구한 것이다.

이는 다음으로부터 유도된다.
\(AC^T=(det(A))I \cdots (2)\)

이는 (1)의 양변에 (det A)A를 곱해준 식이다.

(2)가 참이라면 (1)도 참이다.

여기서 좌변은 A와 \(C^T\) 행렬의 곱, 우변은 대각행렬로 표시된다.
각 대각행렬의 원소는 모두 det(A)로 통일된다.

이제 각 대각 element를 살펴보면 다음과 같은 방정식이 생성된다.

cofactor formula:
det(A) = \(a_{11}C_{11}+a_{12}C_{12}+\codts+a_{1n}C_{1n}\)
det(A) = \(a_{21}C_{21}+a_{22}C_{22}+\codts+a_{2n}C_{2n}\)
… det(A) = \(a_{n1}C_{n1}+a_{n2}C_{n2}+\codts+a_{nn}C_{nn}\)

이것이 cofactor로 표현한 A의 determinant에 대한 식임을 확인할 수 있다.
이는 당연히 참이고, 어떤 row를 기준으로 하느냐에 따라 n가지 방식이 있는 것일 뿐이다.
A의 row2와 \(C^T\)의 column2와의 내적은,
A의 row3과 \(C^T\)의 column3과의 내적과 동등하다.

그런데 여기서 같은 index의 row와 column의 곱으로 나타나는 대각 원소에 대해서는 det(A)가 되지만 다른 index의 원소끼리의 내적은 0이 된다는 것을 볼 수 있다.
이는 서로 다른 index를 가진 row와 column을 곱하는 것은 똑같은 row를 두개 이상 가진 singular matrix의 determinant를 구하는 것과 같기 때문이다. singular matrix의 determinant는 0이다.

링크에서 2 x 2 케이스의 전개식을 확인해보자.
Link

(2)가 옳으므로, (1)도 옳다.

행렬 A에서 어떤 원소 하나만 값이 바뀌어도 A의 역행렬에서 모든 원소가 영향을 받는다. determinant의 계산에 A의 모든 원소가 영향을 주며, determinant로 cofactor matrix원소를 나누어 역행렬을 계산하기 때문

Cramer’s Rule

어떤 Linear system equation인 Ax=b에 대해 solution은 아래와 같이 정의할 수 있다. 이는 정방행렬인 경우에만 해당된다.

\(Ax=b\)
\(x=A^{-1}b\)
\(x=\frac{1}{detA}C^Tb\)

x의 각각의 row는 \(C^T_{i,:}\)와 b의 내적을 det(A)로 나눈 값과 같다.

\(x_1=\frac{c_{11}b_1+c_{21}b_2+\cdots+c_{n1}b_n}{det(A)}=\frac{det(B_1)}{det(A)}\)
\(x_2=\frac{c_{12}b_1+c_{22}b_2+\cdots+c_{n2}b_n}{det(A)}=\frac{det(B_2)}{det(A)}\)
…

이렇게 벡터 b와 cofactor들을 내적하면 어떤 식이 될까?
이는 b와 관련된 어떤 행렬 B의 determinant를 구하는 식이 된다.
그 행렬 B라는 것은 A행렬에서 하나의 column이 b로 대체된 행렬이다.

3 x 3 행렬을 예로들면,
\(A= \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix}\)

\[x_1=\frac{1}{det(A)} \begin{vmatrix} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \end{vmatrix} = \frac{c_{11}b_1+c_{21}b_2+c_{31}b_3}{det(A)} = \frac{det(B_1)}{det(A)}\]

\(x_2=\frac{1}{det(A)} \begin{vmatrix} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \end{vmatrix} = \frac{c_{12}b_1+c_{22}b_2+c_{32}b_3}{det(A)} = \frac{det(B_2)}{det(A)}\)
…

이렇게 solution을 determinant를 이용해 풀 수 있다는 것이다.

Cramer’s Rule은 Square matrix이면서 Singular matrix가 아닌 행렬에 대해 다음을 의미한다.

\[x_j = \frac {c_{1j}b_1+c_{2j}b_2+\cdots+c_{nj}b_n} {det(A)} = \frac {det(B_j)} {det(A)} = \frac { \begin{vmatrix} a_{11} & \cdots & b_1 & \cdots & a_{1n} \\ a_{21} & \cdots & b_2 & \cdots & a_{2n} \\ \cdots \\ a_{n1} & \cdots & b_n & \cdots & a_{nn} \\ \end{vmatrix} } { \begin{vmatrix} a_{11} & \cdots & a_{1j} & \cdots & a_{1n} \\ a_{21} & \cdots & a_{2j} & \cdots & a_{2n} \\ \cdots \\ a_{n1} & \cdots & a_{nj} & \cdots & a_{nn} \\ \end{vmatrix} }\]

Consideration of the Cramer’s Rule

Cramer’s Rule은 가우스 소거법을 대수적 공식으로 깔끔히 정리한데에 의미가 있다.

하지만 효율이 너무 떨어진다. 재사용성이 낮다.
실제로 컴퓨터도 이러한 방법을 사용하지는 않는다.

Geomatrical Analysis of Determinant

행렬식은 기하학적으로 2D에서는 넓이를, 3D에선 부피를 의미한다.

증명은 링크로.
Link

Q행렬은 회전한 모양이므로 2D에선 넓이가 1, 3D에선 부피가 1로 나타난다.

그리고 prop 3-1에서 한 row에 상수 t를 곱한 것은, 해당하는 축으로 길이를 t배 늘린 것과 같아진다. 그래서 넓이나 부피가 t배가 되는 것이다.

determinant는 eigenvalue와 Linear transformation에서 필수적인 개념이다.