[선형대수] Lecture 2: Elimination with matrices

https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/video_galleries/video-lectures/

위 수식을 보고 x, y, z 값을 찾아보자. 어떻게 하면 규칙을 통해 값을 찾을 수 있을까?

우선 다음과 같이 $Ax = b$ 형태의 행렬로 변환해보자.

이제 Elimination을 통해 값을 찾아보자.

우선 $A$ 행렬에서, (1, 1)에 해당하는 값(즉, 1)을 pivot으로 선정하여 아래 행들의 같은 열 값들 중 (1, 1)만 남기고 나머지를 0으로 만들어 보자.

이를 위해 $row_2 - 3row_1$을 해야 한다.

이제 (1, 1) 다음 pivot을 선정해보자. (2, 2)를 pivot으로 선정한다. 그리고 아래 행(2, 3)의 값을 0으로 만들어 보자.

이를 위해 $row_3 - 2row_2$를 해야 한다.

이제 최종 목적지인 $u$(under-triangle) 행렬을 구했다.

하지만 만약, pivot이 0이 되면 어떻게 될까?
-> 이 경우 우리는 더 이상 elmination을 할 수가 없다. 따라서 규칙을 통해 값을 구할 수가 없게 된다.

이제 $Ax=b$에서 b가 위 과정에서 어떻게 변하는지 살펴보자.
순서대로 $row_2 - 3row_1$, $row_3 - 2row_2$가 적용될 것이다.

이렇게 해서 최종 목적지인 C 행렬을 구했다. 이제 U와 C를 통해 수식을 다시 정리해 보자.

Back-Substitution 과정을 통해 차례대로 변수들의 값을 구해보자.
그러면 순서대로 z=-2, y=1, x=2라는 걸 알 수 있다.

---

그러면 일반적인 방법론은 무엇일까?

우선 "linear combinations of columns"와 "linear combinations of rows"를 비교해 보자.

위는 linear combinations of columns다. 즉 오른쪽 행렬의 값을 왼쪽 행렬의 열들에 매칭시킨 값이 결과가 된다.

반면에 linear combinations of rows는 왼쪽 행렬의 값을 오른쪽 행렬의 행들을 기준으로 매칭시킨 값이 결과가 된다.

이제 아까 x, y, z 값을 구할 때 했던 과정을 다시 살펴보자.
(1번 과정) $row_2 - 3row_1$
(2번 과정) $row_3 - 2row_2$

위에서 $E_{21}$은 1번 과정에 해당하는 행렬이다. 의미는 다음과 같다.
(1, 0, 0): $1row_1 + 0row_2 + 0row_3 = [1, 2, 1]$
(-3, 1, 0): $-3row_1 + 1row_2 + 0row_3 = [0, -2, 2]$
(0, 0, 1): $0row_1 + 0row_2 + 1row_3 = [0, 0, 5]$

즉, linear combinations of rows를 통해서 $E_{21}$을 구할 수 있다.

마찬가지로 2번 과정인 $E_{32}$도 다음과 같이 구할 수 있을 것이다.

이제 그러면 아까 위에서 값을 구했던 전체 과정을 $E_{32}, E_{21}$ 노테이션을 통해 간단하게 작성해 보자.

그러면 아까의 과정을 다음과 같이 간단하게 표현할 수 있을 것이다.

위에서 $(E_{32}E_{21})$ 연산을 먼저 해도 값에는 변화가 없다는 걸 기억해두길 바란다.

다만, 연산 위치가 변하면 그건 다른 값이 되니 주의가 필요하다.
예를 들어 행렬 Permutation에서,

위는 행 기반 combinations로, 오른쪽 행렬의 결과값들은
[c, d] = 0[a, b] + 1[c, d]
[a, b] = 1[a, b] + 0[c, d]
를 의미한다.

이제 반대로 $P$ 위치를 바꿔서 연산해 보자.

오른쪽 행렬의 결과값들은
$col_1$인 [b, d] = 0[a, c] + 1[b, d]
$col_2$인 [a, c] = 1[a, c] + 0[b, d]
를 의미한다.

이처럼 행렬 위치가 바뀌게 될 경우, 그 결과는 다르게 나온다.

Inverse Matrix에 대해서 간단히 알아보자.

위에서 $E^{-1}$은 Inverse Matrix를 의미한다. 즉, $E$가 $I$가 되도록 만들기 위해, E의 행들에 대해서 다음과 같은 연산을 수행한다.
(1) $1row_1 + 0row_2 + 0row_3$
(2) $3row_1 + 1row_2 + 0row_3$
(3) $0row_1 + 0row_2 + 1row_3$
과정을 수행한다.
그리고 이를 행렬로 표현한 $E^{-1}$이 $E$의 Inverse Matrix를 의미한다.