[혁펜하임: 보이는 선대] 3강: 가우스-조던, 행렬식, trace, 최소자승법

Lecture or Textbook Review/Linear Algebra

[혁펜하임: 보이는 선대] 3강: 가우스-조던, 행렬식, trace, 최소자승법

-ˋˏ ♡ ˎˊ- 2024. 6. 24. 22:35

3-1강: Gauss-Jordan Elimination

선대는 연립 일차방적식을 Ax = b의 형식인 행렬과 벡터의 곱으로 나타내고, 여기서 x의 해를 찾는 것이라고 하였다. 여기서 이 x를 찾는 방법이 가우스-조던 소거법이다.

보통 연립 일차방정식을 풀 때는 하나의 식의 양변에 상수를 곱하고 다른 식에 더하거나 빼며 풀었다. 하지만 변수와 식의 개수가 많아지면서 이에 따라 행렬과 벡터의 곱으로 연립 방정식을 나타내기 시작했고, 이렇게 나타낸 방정식에서 해를 쉽게 찾는 방법이 가우스 조던 소거법이다. 방정식의 해를 찾는 원리는 기존과 동일하지만 방법만 살짝 다르다.

예를 들어 아래의 연립 일차 방정식이 있다고 하자. 이 식을 행렬과 벡터의 곱셈으로 나타내면 그다음 수식과 같다.

$$\begin{cases} 2x + y -z = 8 \\ -3x -y + 2z = -11 \\ -2x + y + 2x = -3 \end{cases}$$

$$\begin{bmatrix} 2 & 1& -1 \\ -2 & -1& 2 \\ -2& 1 & 2 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 8 \\ -11 \\ -3 \end{bmatrix} $$

위 행렬과 벡터의 곱으로 나타낸 방정식에서, 상수를 가지는 행렬 벡터만 아래의 형식으로 바꾸는 것을 확장 행렬이라고 한다.

$$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3\end{array}\right]$$

이렇게 확장 행렬로 나타냈다면, 가우스 조던 소거법의 목표는 왼쪽 행렬을 항등행렬로 만드는 것이다. 왼쪽 행렬이 항등 행렬이 되었다고 생각하고 방정식으로 다시 바꾼다면, 오른쪽 행렬이 각각 변수의 해가 됨을 알 수 있다. 가우스 조던 소거법을 수행하는 방법은 다음과 같다.

양 변에 0이 아닌 상수배를 해준다.
상수배한 행을 다른 행에 더하거나 뺀다.
행끼리 자리를 바꾼다.

위 방법을 알맞게 사용한다면 쉽게 연립 일차방정식의 해를 구할 수 있다. 위에서 보여줬던 연립 방정식을 가우스 조던 소거법을 사용하여 차례로 풀어보면 다음과 같이 풀 수 있다.

상수로 이루어진 확장 행렬을 항등행렬로 나타내기 위해서 순서대로 off-diagonal 성분을 0으로 만든다. 모두 0으로 만들었다면 각 행을 상수배하여 대각 성분을 1로 만들면 왼쪽 행렬이 항등행렬이 된다.

2. Inverse Matrix

먼저 역행렬이 중요한 이유는 Ax = b에서 양변에 A의 역행렬을 곱해주면 x의 해를 바로 구할 수 있기 때문이다.

아래와 같이 2 x 2 행렬이 있다. 이 행렬의 역행렬은 아래 수식의 우변이다. 아래의 역행렬 수식을 유도하는 법을 가우스 조던 소거법을 통해 알아보자.

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

일단 행렬 A가 있을 때 곱해서 항등행렬이 나오게 하는 행렬이 역행렬이다. 행렬과 행렬의 곱은 같은 계수를 가진 두 개의 서로 다른 연립 일차방정식을 동시에 나타내는 것이라고 했다.

$$\begin{bmatrix} a&b\\c&d \end{bmatrix} \begin{bmatrix} a\prime & b\prime \\ c\prime & d\prime \end{bmatrix} = \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix}$$

위의 수식에서 행렬 A의 역행렬을 유도해 보자. 가우스 조던 소거법으로 간단하게 구할 수 있다. 일단 위의 행렬곱을 확장행렬로 나타내야 한다. 이는 아래의 수식과 같다.

$$\left[ \begin{array}{cc|c} a&b&1\\c&d&0\end{array} \right]$$

$$\left[ \begin{array}{cc|c} a&b&0\\c&d&1\end{array} \right]$$

이 두 확장행렬의 해를 각각 구해도 되지만, 더 효율적이게 아래의 수식과 같이 더 확장된 확장행렬을 푼다면 바로 해를 구할 수 있다. 아래의 수식에서 왼쪽 행렬을 항등행렬로 만들면 오른쪽 행렬이 역행렬이 될 것이다.

$$\left[ \begin{array}{cc|cc} a & b & 1 & 0 \\ c & d & 0 & 1 \end{array} \right]$$

이를 차례로 유도하면 Figure 2와 같다.

이를 정리해서 나타내면 아래의 수식과 같다.

$$A^(-1)= \frac{1}{ad-bc} \begin{bmatrix} d & -b \\ -c &a \end{bmatrix}$$

만약 ad-bc = 0이라면 위 수식의 행렬 앞의 분수가 정의되지 않는다. 따라서 역행렬은 존재하지 않는다. ad-bc를 determinant라고 한다. ad - bc로 역행렬의 유무를 알 수 있기 때문이다.

[정사각행렬 A가 invertible하다]와 동치인 것들

det(A) ≠ 0: determinant가 0이 아니여야 역행렬을 가지기 때문
A가 full rank: 즉, det(A) = 0 ⇔ A가 rank deficient
N(A) = 0: A가 full rank면 무조건 null space에 0 벡터 밖에 없기 때문

역행렬 관련 property

(AB)^-1 = B^-1 x A^-1: 교환법칙이 성립하지 않기 때문에 순서를 잘 생각해야 함
(A^-1)^-1 = A
(kA)^-1 = 1/k x A
(A^T)^-1 = (A^-1)^T
det(A^-1) = 1/det(A)

3. Determinant

3. 1. 3 x 3 행렬의 determinant

determinant 관련 property를 배우기 전에, 먼저 3 x 3 행렬의 determinant를 구해보자.

$$A = \begin{bmatrix} a & b & c \\ d & e& f \\ g & h & i \end{bmatrix}$$

위 수식과 같이 3 x 3 행렬이 있을 때, 이 행렬의 determinant는 아래 수식과 같다.

$$det(A) = a(ei-fj) - b(di-fg) + c(dh-eg)$$

determinant 수식을 하나하나 뜯어서 생각해 보자. 먼저 괄호 속 수식이다. 괄호 앞에 곱해진 변수가 속한 행과 열을 제외하고 남은 2 x 2의 determinant이다. 쉽게 설명하면 Figure 3과 같다.

다음으로 각 항의 부호는 앞에 있는 변수의 열을 제외한 열 번호의 합이 짝수면 -, 홀수면 +이다. 예를 들어 b(di-fg) 항에서 제일 앞에 있는 변수가 b, 근데 이 b가 위치한 2번째 열을 제외한 1번째, 3번째 열번호의 합 = 1 + 3 = 4, 즉 짝수이므로 부호가 -이다.

3. 2. Determinant 관련 properties

det(A) = 0 ⇔ A is singular(= invertible X)
A가 rank-deficient ⇔ det(A) = 0
For diagonal matrix, det(A) = a_11 x a_22 x ... x a_nn (대각 성분의 곱)
For triangular matrix*, det(A) = a_11 x a_22 x ... x a_nn (대각 성분의 곱)
det(I) = 1
det(cA) = c^n det(A) (단, 행렬 A의 크기는 n x n)
det(A^T) = det(A)
det(AB) = det(A)det(B)
det(A^-1) = 1/det(A)
det(A) = λ_1 x λ_2 x ... x λ (eigen value가 모두 0이 아닐 때만 역행렬 존재)

*삼각행렬: 대각 성분을 기준으로 위쪽이나 아래쪽을 제외한 부분이 0인 행렬(위로 삼각형이면 upper triangular matrix, 아래로 삼각형이면 lower triangular matrix)

4. Trace

trace는 diagonal element를 다 더한 값이다. 그렇다면 이 trace를 어디에 사용할까? 예를 들어 loss를 최소화하는 최적화를 할 때를 생각해 보자. loss 함수는 행렬의 함수이기 때문에 행렬로 미분해야 하는 그런 불상사가 생긴다. 이때 trace를 사용한다.

trace는 정사각행렬에 대해서만 정의가 내려진다. 표기는 tr(A)와 같이 한다. 식으로 정의하자면 아래와 같다.

$$tr(A) = \sum^n_{i = 1} a_{ii}$$

이렇게 trace를 계산하면 결과는 스칼라 값이 나온다는 것이 중요하다. 아까 설명했던 loss 함수에서 변수를 바꿔가며 최적화를 한다는 이야기는 무조건 크기를 이야기할 수 있어야 된다. 벡터나 행렬처럼 여러 수가 있는 경우에는 수가 크다 작다를 표현할 수 없다. 그렇다면 loss 함수에 trace를 취하면 스칼라 값을 얻을 수 있어서 미분하기가 수월해진다.

4. 1. trace 관련 properties

tr(A + B) = tr(A) + tr(B)
tr(cA) = ctr(A)
tr(A^T) = tr(A)
tr(AB) = tr(BA) (단, A의 크기가 m x n일 때, B의 크기는 n x m이어야 함)
tr(a^Tb) = tr(ba^T)
cyclic property: tr(ABCD) = tr(BCDA) = tr(CDAB) = tr(DABC)
tr(A) = eigen value의 합

5. Least Squares & Projection Matrix

5. 1. 문제 상황

최소자승법으로 풀어야 하는 문제 상황부터 알아보자. full column rank인 행렬 A의 크기는 10 x 3이고, rank는 3인 상황이다. 여기서 A의 column space는 10차원 안에서 3차원을 span할 것이다. 이때 10차원 안에 놓인 벡터 b가 있다고 해보자. 벡터 b는 A가 span하는 공간에 놓여 있지 않고, 다른 차원에 존재한다. 이는 A의 column space, 즉 Ax에서 벡터 x를 아무리 바꿔도 벡터 b를 만들 수 없다는 것이다. 이때 이 벡터 b와 Ax를 최대한 가깝게 만드는 벡터 x를 찾아보고자 한 것이 최소자승법의 문제 상황이다.

참고로 Figure 4에서 A의 column space는 3차원이다. 개념적으로만 아래 그림과 같이 나타낸 것이다.

벡터 b와 Ax의 차이는 오차 범위이기 때문에 error vector에서 e를 따와서 벡터 e라고 한다. 이 벡터 e가 가장 작을 때의 벡터 x를 찾고자 하는 것이다. 즉, 이 e 벡터의 길이가 가장 작아지도록 하는 벡터 x를 찾으면 되는 거고, least squares는 벡터 e의 2-norm을 줄이고자 하는 것이다. 2-norm이면 루트를 가지고 있으므로 이 루트를 없애기 위해 제곱을 해준다. 결국 벡터 e의 2-norm의 제곱을 최소화하고자 하는 것이다.

5. 2. 내적으로 풀기

벡터 e의 크기를 최소화하기 위해서는, 벡터 e와 Ax가 수직해야 한다. 그렇다면 벡터 e와 Ax를 내적 하면 0이 되도록 하는 벡터 x를 찾으면 된다. 이 x를 x_hat이라고 표기하겠다. 내적 해서 0이 되는 것을 transpose를 이용해 풀어주면 아래의 수식과 같다.

$$(\underline{b}-A\underline{\hat{x}})^T A\underline{\hat{x}} = 0$$

$$(\underline{b}^T A - \underline{\hat{x}}^T A ^T A) \underline{\hat{x}} = 0$$

위 수식에서 x_hat이 0이면 수식이 성립하지만, x_hat = 0인 상황은 우리가 찾고자 하는 상황이 아니기 때문에, 괄호 항이 0이 되도록 해야 한다. 수식을 이항으로 정리해서 쓰면 아래와 같다.

$$\underline{b}^T A = \underline{\hat{x}}^T A^T A$$

위 수식 양변에 transpose를 취하면 아래의 수식이 된다.

$$A^T \underline{b} = A^T A \underline{\hat{x}}$$

위 수식을 normal equation이라고 한다. 위 수식의 우변에서 A transpose(3 x 10)와 A(10 x 3)를 곱하면, A가 10 x 3 행렬이었으므로, 3 x 3 정사각행렬이 된다. 또, rank(A^TA)와 rank(A)는 같기 때문에, A^TA의 rank는 3이 되고, 이는 full rank matrix임을 알 수 있다. 이것이 의미하는 것이 무엇이냐 하면, A^TA는 full rank여서 invertible하기 때문에 양변에 A^TA의 inverse를 곱하여 벡터 x_hat을 구할 수 있다는 것이다. 이를 수식으로 정리하면 아래와 같다.

$$\underline{\hat{x}} = (A^T A)^(-1) A^T \underline{b}$$

위 수식을 Ax_hat에 대입하면 아래와 같은 수식을 얻을 수 있다.

$$A \underline{\hat{x}} = A(A^T A)^(-1) A^T \underline{b}$$

위 수식의 우변에서 벡터 b의 앞부분을 벡터 b에 곱함으로써 정사영된 벡터 b를 얻을 수 있으므로, 벡터 b 앞부분을 projection matrix라고 한다.