Linear Algebra(18.06) - 2.Elimination with matrices

Elimination(소거법)은 선형방정식을 풀기 위해 가장 흔하게 사용되는 기법이다.

Elimination은 경우에 따라 원하는 결과가 나올 수도 있고 그렇지 않을 수도 있다.

다음과 같은 선형 방정식이 있다고 가정하자,  이 식은 Ax=b로 표현이 될 수 있음을 1강에서 확인했다.

Ax=b로 표현 한 후에 A의 1행 1열의 원소를 Pivot이라 한다. (이때 1은 첫번째 Pivot) 

 

소거를 시작하기 위해서 적당한 multiplier를 찾아야 한다.

일단 첫번째 식에 적당한 수를 곱해 두번째 식에서 빼야 하는데 3을 곱해서 뺀다.

 

그결과 2행 1열의 원소가 0이된다는 것을 확인 할 수 있고, 두번째 pivot은 2이다.

다음은 3행 1열을 0으로 만들어야 하는데, 이미 0이 되어 있으므로 3행 2열을 0으로 만든다.

적당한 multiplier는 2

 

그 결과 다음과 같이 대각선을 빗변으로하는 삼각형(?)의 형태가 만들어 진다.

이를 U라고 쓰며 Upper Triangular의 약자이다.

 

 

지금까지 A에만 초점을 맞췄는데, A가 소거를 진행하는 동안 A가 multiplier를 곱해서 빼는 만큼 b에서도 뺴줘야 한다.

결과는 b'=( 2 , 6 , -10 )이 된다. 

 

A와 b를 같이 쓴 행렬을 Augmented Matrix라고 한다. 

A에 행을 하나 더 만들어서 b를 넣고, elimination을 해줄때 첨가된 열에 대해서도 소거를 진행해주면 된다.

 

맨 처음에 원하는 결과가 나올수 도 있고 그렇지 않을 수도 있다 하였는데,

원하는 방향대로 되지 않는 다면 행을 교환할 수 있다. 행 교환하는 기준은 U를 만들수있느냐 없느냐 이다.

행을 교환해도 U가 만들어지지 않는다면 pivot이 없는 경우 이다.

 

예를 살펴보자

소거를 진행 한 후에 2행 2열이 0이기 때문에 2행과 3행을 교환하였더니 U가 된 케이스이다.

 

소거를 진행한 후에는 방정식의 해를 쉽게 찾을 수 있다.

z,y,x순으로 대입해서 해를 찾기 때문에 Back-subsitituion이라 부르는 것 같다.

 

 

1강에서 행렬을 바라보는 시각 2가지를 배웠는데, 이번엔 행렬 곱할때의 시각을 다룬다.

A를 기준으로 열벡터가 오른쪽에 있으면 column들의 combination

A를 기준으로 행벡터가 왼쪽에 있으면 row들의 combination으로 생각하자.

 

이 그림들을 잘 기억하자. Elimination을 하면서 흔적을 남길때 사용 할 수 있다.

우변의 행렬을 A'이라 하자. 2행에 대해서 소거를 진행하므로,

A와 A'의 1행과 3행이 같다는 사실을 확인 할 수 있다.

따라서 흔적을 남기려는 행렬의 1행 3행을 각각 [1,0,0] , [0,0,1]으로 남겨둔다.

 

( cf- n by n행렬에 대각선의 원소만 1인 행렬을 곱하면 자기 자신이 되며 이를 identity matrix라고 한다.)

2행과 A를 곱해서 [0,2.-2]로 만드려고 할 때, 

row2 = -3row1 + row2 라는 사실을 기억하면 ?이 들어간 행에는 

[-3 , 1, 0]이 와야한 다는 사실을 쉽게 알 수 있다.

이때, 왼쪽의 행렬은 2행 1열의 원소를 E21이라 한다.

 

위의 예제와 같은 행렬이기 때문에 E31은 없고 E32는 마찬가지로 구해보면 3번쨰 행은 [0,-2,1]이다.

 

결과적으로 E32E21A = U로 쓸 수 있다.

이때행렬을 곱하는 순서를 다르게 해도 식이 성립한다. 즉 결합법칙(Associative Law)이 적용된다.

( E32 E21 )A = E32( E21 A )

 

행의 순서를 바꿔주는 행렬을 Permutation Matrix라고 한다.

위의 row picture로 바라본다면 [0,1] 은 A의 두번째 행을 A'의 첫행으로 선택하겠다는 뜻이고

[1,0]은 A의 첫행을 A'의 둘째행으로 선택하겠다는 뜻으로 해석할 수 있다.

 

행이아닌 열을 바꾸고 싶은 경우엔??  ==> P행렬을 오른쪽에 둔다.

 

위에 결합법칙이 성립된다 하였는데, 교환법칙은 성립하지 않는다.

행렬의 곱셈을 할라면 A를 n by m, B를 m by k 행렬이라 가정하면, A의 열과 B의 행의 개수가 일치해야 하는데,

교환법칙이 성립한다면 k = n이여야 한다는 조건이 생기는데 아닌경우도 있으므로 모순이다.

 

마지막으로 역행렬(Inverse Matrix)은 단위행렬(Identity Matrix)을 만들어주는 행렬이다.

 

E를 단위행렬 I로 만들어주기 위해서는 위의 방식을 이용한다.

row2 = 3* row1 + row2  operation이 필요하므로 2번째 행이 [3,1,0]인 행렬을 만들수 있다.

이때 왼쪽의 행렬을 역행렬이라 하며 지수부분에 -1을 써 역행렬임을 나타낸다.