[Lecture 4] MIT Linear Algebra - Gilbert Strang

Linear Algebra 4강

Factorization into A = LU

인수 분해라는 말을 한국에서 학교를 다녔다면 모를 수가 없다.

보통 인수분해는 다항식의 연산에서 나오는 개념인데, 선형대수학에서도 인수분해가 쓰인다

Factorization이 바로 인수분해라는 뜻이다.

 

선형대수학에서의 인수분해란, A라는 matrix를 Lower Triangle 과 Upper Triangle로 나눈 것이다.

 

 

지난 시간에 위의 식에 대해서 공부했었다.

어떤 matrix A와 그 inverse를 서로 multiplication 시켜주면, 순서에 상관없이, Identity matrix I가 나온다.

 

여기서 우리는 질문을 가지고 인수분해를 시작한다.

A 대신 AB 라는 두 matrix의 곱을 대입해보자. (A, B는 모두 invertible 하다는 전제 하에)

그럼 AB라는 matrix의 inverse는 어떻게 되어야할까? 어떻게 되어야 위처럼 곱했을때 identity matrix I가 나올까?

위와 같이, B의 inverse와 A의 inverse를 곱한 것(순서 조심)을 AB와 곱해주면 I가 나오는 것을 볼 수 있다.

 

AB와 B-1A-1 순서를 서로 바꿔도 마찬가지이다.

따라서 어떤 두 matrix의 곱 AB의 inverse는, B-1A-1인 것을 알 수 있다.

 

 

이제 inverse 에 transpose를 적용시켜보자.

AA-1 = I 라는 위 문장에서 양변을 똑같이 transpose하면 어떻게 될까?

먼저, 위와 같은 transpose의 성질에 유념해야한다. AB matrix에 transpose를 적용하면 각 matrix A, B에 각각 transpose가 적용되되, 그 순서가 바뀐다.

이 성질을 이용하여 AA-1 = I를 양변 transpose 해보자.

 

당연하게도, 양변을 transpose 취하면 오른변은 I의 transpose, 즉 I가 그대로 나온다.

즉, (A-1)T = (AT)-1이 같다는 것을 알수가 있고,

다르게 말하면 어떤 single matrix A에 대해 transpose와 inverse 적용 순서 상관없이 같은 결과가 나온다는 걸 알 수 있다.

 

(transpose에 대한 구체적 설명없이 그냥 이런 성질을 보여주려고 언급하신 부분이고, transpose는 다음 강의에 더욱 자세히 나옵니다)

 

LU decomposition

그럼 이제 본격적으로 matrix를 인수분해 해보자.

이전에 했던 간단한 matrix 연산들에 등장했던 개념으로 lower triangle, upper triangle 등이 있었다.

약자로 나타내면 각각 L, U 인데, 어떤 matrix A를 이렇게 L과 U로만 나타내는 것을 LU decomposition이라고 한다.

upper triangle, lower triangle 이란 위처럼 삼각형 부분에만 값들이 있고 나머지 부분은 0 인 matrix!

 

위와 같이 A라는 matrix가 있다고 하자. 얘를 upper triangle로 만들려면 어떻게 해야할까?

위와 같이 A의 두번째 row에서, 첫번째 row에 4를 곱한것을 빼주면 upper triangle matrix가 된다.

그리고 "두번째 row에서, 첫번째 row에 4를 곱한것을 빼주면" 이라는 문장을 matrix로 나타낼 수 있다.

matrix로 나타내면 위와 같다.

즉 A를 U로 만들기까지의 최종 식은 위와 같다.

주목할 것은 E21이 lower triangle matrix 형식이라는 것이다.

이때 양변에 E21의 inverse를 곱해주면 좌변에는 A만 남는다.

E21의 inverse를 양변에 곱하면?

E21의 inverse는 단순히 -4에서 +4로 부호를 바꿔주면 된다. 하지만 이건 해당 example 이 clear 한 방법이라서 가능하고, 모든 inverse가 부호를 바꿔서 되는 것은 아니다.

 

여하간 이 예제에서는 위와 같이 A를 decomposition 시켰다.

 

LDU decomposition

이번에는 pivot 분리를 원하는 경우에 대해 살펴보자.

이럴 때는 각 pivot이 속해있는 row pivot 값을 나눠주어야 한다.

LDU decomposition인 이유는, Lower triangle, Diagonal matrix, Upper triangle matrix로 분해하기 때문이다.

밑의 예시를 보면 알 수 있다.

가운데 D matrix는 대각행렬, 즉 diagonal 부분만 요소를 가지고 나머지는 0인 것을 알 수 있다.

more balanced matrix라 할 수 있다. 나머지 행렬들은 모두 대각 행렬 요소가 1이고, 가운데 D 행렬만 대각행렬 요소가 1이 아니기 때문이다.

 

Example

decomposition을 유도하는 방법에는 같아보이지만 다른 두가지 방법이 있다.

위의 두개이다.

어떻게 다른지 살펴보자.

 

먼저 첫번째 경우이다. Elimination matrix E를 만들기 위해 E32, E21등을 서로 곱하면 숫자가 커진다.

만들어진 E의 왼쪽 하단 element는 벌써 10이 된 걸 볼 수 있다.

3x3이라 망정이지, 더 큰 matrix면 계산이 복잡해지기 쉽다.

 

두번째 경우를 보자.

E21-1의 2 요소와 E32-1의 5 요소가 E-1의 같은 자리에 그대로 간 걸 볼 수 있다.

E의 inverse 버전끼리 곱하면 아까 위에서처럼 10이라는 뜬금없는 큰 숫자가 나오지 않는다.

이게 두번째 방법의 장점이다.

 

즉, 두번째 방법을 쓰면

if no row change, the multipliers go directly into L 이라 할 수 있다.

 

 

Transpose and Permutation

강의의 마지막 부분에서는 permutation과 transpose에 대해 다룬다.

Row exchange를 가능하게 해주는게 바로 permutation matrix인데,

강의 예시로는 3x3 에서의 permutation 예시를 든다.

이 6개가 3x3 matrix에서의 permutation의 전부이다.

그런데 중요한것은, 이 6개의 permutation 끼리는 서로 곱해도 결과가 이 6개의 permutation 중 하나이다.

또, 얘네들의 inverse도 다 얘네들끼리이다.

 

하나 예시를 들어보면, 2번째 matrix는 row 1과 row 2 를 서로 switch 해주는 matrix이다.

row 1과 row 2를 switch 한 상태에서, 다시 원래대로 돌아가려면 permutation의 inverse를 취해주면 되는데

직관적으로 생각하면 다시 row 1과 row 2를 바꿔주면 된다.

그래서 2번 matrix의 inverse는 자기 자신이다.

 

또, 5번 matrix와 6번 matrix는 inverse 관계이다. 5번은 위로 한칸씩 올리는 matrix고 6번은 아래로 한칸씩 내리는 matrix 이기 때문이다.

 

여기서 우리는 permutation matrix의 중요한 성질을 알 수 있다.

바로 permutation matrix의 inverse는, transpose와 같다는 것이다.

 

또, permutation matrix의 개수는 nxn matrix일때 n! (팩토리얼) 개이다.

 

 

이렇게 간단하게 permutation에 대해 배워보고, 다음 강의에서는 본격적으로 이것들을 이용할 것이라 하고 4강은 끝났다.