이번 강의에서는 다음에 대해서 배운다.

• Column space of A : Solving Ax=b
• Nullspace of A

Column space of A : Solving Ax=b

다음 예제에 대해서 생각해보자.

위 예제의 Column space는 어떻게 표시되는가? Column space of A=$C(A)$=All linear combnations of columns of A 이다.

그렇다면 여기서 질문을 하나 던져보자.

Ax=b의 식에서, A는 모든 b에 대해서 해를 갖는가?

답은 No이다. 그 이유에 대해서 알아보자.

위 관계식 보았을 때, 어떤 b의 값들이 위 관계식의 해를 갖게 할까?

답은 b가 A의 Column들의 linear combination으로 이루어지는 것이다.

쉽게 말해서 b=$c_1Col_1(A) + c_2Col_2(A) + c_3Col_3(A)$로 표현되면 된다.

그렇게 된다면, $x_1=c_1, x_2=c_2, x_3=c_3$가 될 것이다.

위 예시에서 해는 무엇을까? x=(1,1,0) or (0,0,1) or (2,2,-1) 등 무수히 많을 것이다.

그렇다면, X=c_1(1,1,0) + c_2(0,0,1) 단 (c_1=c_2=0 제외) 로 나타낼 수 있다.

그런데 이 방정식의 해 중에서 x=(0,0,0)이 포함되지 않으므로, X는 공간을 만든다고 볼 수없고, 단지, 두 벡터로 이루어진 평면을 만들 뿐이다.

Nullspace of A

Nullspace(영공간)이란 무엇일까?

Nullspace of A는 $AX=0$를 만족시키는 모든 X의 선형결합이 만드는 공간이다.

이때 X=(0,0,0), (1,1,-2), (2,2,-4) …이다. ( (0,0,0)은 항상 해가 된다. )

그리고 X = c(1,1,-1)로 표현될 수 있다.(c는 임의의 상수)

또한, AX=b의 경우와 다르게, x=(0,0,0)이 위 방정식의 해 중에서 존재하므로, x는 선 모양의 공간을 형성한다고 할 수 있겠다.

이번 강의에서는 PA=LU, Vector space & Sub-space 에 대해서 학습한다.

P : Permutation matrix

PA=LU (LU decomposition with permutation)

P : Permutations - execute row exchanges 갑자기 여기서 P는 왜 언급이 된 것일까? 그것은 바로, 그냥 A를 이용하여 가우스 소거법을 진행했을 때, 중간 피벗이 0이 되는 경우가 발생할 수 있기 때문이다. 그렇게 된다면, 0이 되지 않는 행과 위치를 바꿔줘야한다.(row exchange) 이때 사용되는 행렬이 P(Permutation matrix)이다. PA는 즉, 행 교환이 일어난 A행렬을 의미한다. 이렇게 행을 바꾸고 난 후, LU분해를 진행하여 나온 식이 PA = LU이다.

The number of permuation matrix

Permutation matrix는 Linear algebra-Lecture 02 에서 언급했었다. Permutation matrix는 행 또는 열의 위치를 서로 바꿔주는 행렬을 의미한다. nxn의 permutation matrix는 몇 개가 존재할까?

정답은 바로 n!개 이다.(세 사람이 순서가 있는 세 자리에 앉는 경우의 수와 동일하다.)

3x3행렬의 예제를 살펴보자.

4x4행렬은 4! 이므로, 24개가 나올것이다. 시간이 있다면 직접 한 번 해보자.

Property of permutation matrix

또한, permutation matrix는 다음과 같은 중요한 성질을 만족한다.

S : Symmetric matrix

Symmetric matrix

Symmetric matrix(대칭행렬)은 주 대각선을 기준으로 마주보는 원소가 같은 행렬이다. 식으로 표현하면 다음과 같다.

그리고 위 식은 다음과 같은 성질을 만족함을 의미한다.

Properties of symmetric matrix

1. $A=A^T$
2. $AA^T = S$

proof

$(A^TA)^T = (A^T)(A^T)^T$ $(A^T)(A^T)^T=(A^T)A$ 이므로 대칭행렬의 성질인 1번 성질을 만족.

ps. 대칭행렬과 반대칭행렬의 성질 $A = 1/2{(A+A^T) + (A-A^T)}$

여기서, $A+A^T$=대칭행렬, $A-A^T$는 반대칭행렬이다.

Vector spaces

전에 선형대수학을 공부한 적이 있다면, 벡터공간이 성립되기 위한 8가지 조건들이 있는 것을 본적이 있을 것이다. 그렇다면 그 조건을 다 외워하는걸까? 그렇지 않다. 이 강의에서 Gilbert Strang교수님은 조건을 풀어서 설명을 해주신다. 그 조건은 다음과 같다.

1. 벡터를 표현하기 위한 기준점(Origin)이 있어야 한다.
2. 공간안의 벡터끼리 덧셈, 뺄셈, 상수배, 곱셈 등 연산이 가능해야 한다. 즉, 모든 Linear combination을 표현할 수 있으면 된다. (물론, 엄밀한 정의가 존재하겠지만 나는 이렇게 받아들였다.)

이 두 가지 뿐이다.

그렇다면, $R^2$는 vector space일까?, 그렇다. 먼저 vector를 공간안에서 표현하기 위한 원점(0,0)이 존재하며, $R^2=(x,y)$로 표현되는 모든 벡터끼리 연산이 가능하다.

Sub sapces

그렇다면 sub space(부분공간)이란 무엇을 의미할까? 밀 그대로 어떤 공간의 부분인 공간이다. 집합적으로 설명하자면, 어떤 큰 공간에 포함되어있는 공간이다. Vector space의 조건을 만족하면서 말이다!!! 즉, 한 마디로 하면, vector space의 부분적인 공간이 sub space이다.

그렇다면 당연히 1, 2번 조건을 만족해야한다.

1번 조건을 만족하기 위해서는 원점(zero vector)을 포함해야 하며, 2번 조건을 만족하기 위해서는 양,음연산에 의한 결과를 모두 포함해야 한다.

위에서 예를 들었던 $R^2$공간을 다시 예시로 사용해보자. $R^2$의 부분공간은 무엇이 있을까? 총 3가지가 있다.

1. All of $R^2$

2. Any line through (0,0)

3. Zero vector only

이렇게 3가지 부분 공간이 있다. 생각해보면, 1,2번 조건을 모두 만족하는 것을 알 수 있다. 세 부분공간은 모두 zero vecotr을 포함하며, 각 vector에 0,-2,4 와 같은 어떤 상수를 곱해도, 해당 공간에 포함되며, 덧셈, 뺄셈 등의 연산에 관해 서도 닫혀있다.

Column space & Row space

다음 그림을 살펴보자.

위 그림에서 A라는 행렬이 있을 때, A라는 행렬의 열에 있는 벡터가 만드는 공간을 열공간(Column space)라 하고, 행에 있는 벡터가 만드는 공간을 행공간(Row space)라 한다.

열공간, 행공간 역시, Vector space의 조건을 만족시켜야한다.

이번 강의에서는 저번에 미쳐 다루지 못한 Inverse of AB, A^T와 Product of elimination matrices, A=LU(no row exchanges) 에 대해서 다루도록 하겠다. 이번 장은 비교적 간단하게 넘어 가도록 하겠다.

Some properties

이번 장에서 세세한 증명은 없지만, 전치(Transpose)연산과 역행렬(Inverse)연산에 대해서 간략하게 설명이 나온다.

Inverse and Transpose

1.$ AA^{-1}=A^{-1}A=I$ (역행렬의 정의)

2.$ (AB)^{-1}=B^{-1}A^{-1}$

proof

$ABB^{-1}A^{-1}=I$

3.$ (A^T)^{-1}=(A^{-1})^T$

proof

$AA^{-1}=I$ $(AA^{-1})^T = (A^{-1})^TA^T = I$ $(A^{-1})^T=(A^T)^{-1}$

4.$L^T = U$ (여기서 L이나 U는 형태만을 의미한다.)

5.$U^T = L$

6.$L^{-1}=L$

7.$U^{-1}=U$

LU decomposition

위의 성질들을 모두 알았다면, LU분해는 매우 간단하다. 앞 장에서 우리는 가우스 소거 법을 이용하여 A를 U형태로 변환시켰다. 만약 A=3x3 의 행렬이라고 한다면,

$E_{32}E_{21}A=U$ 의 형태를 얻었다.

$E_{32}E_{21}$는 어떤 형태의 행렬일까?

$E_{32}E_{21}=L$ 이다. 왜냐하면, 밑에 행에서 위에 행을 빼는 연산이기 때문에,

위 연산은, 주 대각선 기준으로, 윗 부분이 아닌, 아랫 부분에 수가 붙는다.

그러면, $E_{32}E_{21}A=U$ 는 $LA=U$로 바꿔 쓸 수 있다.

$A=L^{-1}U$ 이고, 위에 설명한 성질 중 7번 성질에 의하여 $L=L^{-1}$이므로,

$A=LU$를 만족한다.(물론 $L$과 $L^{-1}$의 값은 다르다. 여기서는 형태 만을 고려한 식이다.)

위 과정을 거치면 LU분해가 모두 끝난다.

이번 강의에서는 Matrix multiplication(4ways), Inverse of A, AB, $A^T$, Causs-Jordan/find $A^{-1}$에 대해서 학습한다.

Matrix multiplication(4ways & block multiplication)

1.Standard

A의행, B의 열의 모든 조합에 대해서, 위와 같은 방식으로 C의 모든 원소를 구했다.

2.Column way(with Matrix)

여기서 이해가 안가는게 Columns of B 이여야 할 것 같은데, Columns of A라고 말한 점이다. 식을 곱하는것을 보면 Columns of B가 맞는거 같다. 하지만 바로 밑에 나오는 Decomposition을 본다면 왜 그렇게 말하는지 알 수 있을 것이다. 행렬C는 $(Columns\ of\ A * Rows\ of\ B)$의 합으로 이루어지기 때문이다.

3.Row way(with Matrix)

4.Decomposition with Column & Row

위 연산의 결과를 보면, 모든 행은 행끼리 같은 선상에 있고, 모든 열은 열끼리 같은 선상에 있는 것을 알 수 있다.

그리고 위 연산을 식으로 더 아름답게 표현할 수 있다.

더욱 일반화된 연산은 다음과 같다.

Block multiplication

block multiplication은 행렬 안에 있는 원소들을 일정 크기의 블록으로 묶은 다음, 그 블록을 마치 행렬의 원소처첨 취급한다음, 행렬곱을 하여도, 기존의 결과와 같아진다는 원리를 나타낸것이다. 다음 예시를 보고 이해해보자.

Inverses

A의 역행렬(Inverse)는 A^{-1}로 표기한다. 이 때, 역행렬은 다음과 같은 성질이 존재한다.

역행렬이 존재하면, invertible 또는 non-singular라고 부른다.

역행렬을 가지지 않을 조건(Conditions of singular case)

1. 결정자(Determinant) = 0
2. 마지막 Pivot = 0 또한, 만약 A가 역행렬을 가지지 않을 경우, AX=0의 식에서 X는 해를 가지지 않는 것을 알 수 있다. 왜냐하면, 미지수는3개 이고, 식도 3개이지만, 마지막 pivot이 0 이 되는 경우, 한 개의 방정식은 있으나 마나 한게 되버리므로, 식2개로 미지수 3개가 표현되기 때문에, 정확한 해를 알 수없고 단순한 비로만 나타낼 수 있다.

Gauss-Jordan (Solve 2 equations at once)

가우스-조르단 소거법은 2개의 식을 한번에 풀어낸다. 다만 그 방정식의 bias가 단위행렬이고, 이 방법을 이용하여 역행렬을 구한다. 다음 예시를 보고 이해해보자.

가우스 조르단 소거법은 원래 A행렬을 단위행렬로 만들면 그 과정이 끝난다.

위 식을 다음과 같이 이해하면 좋을것 같다. A의 역행렬은 A와 곱해졌을때 단위행렬의 결과를 내어놓는 행렬이다. 즉, A의 역행렬을 A를 변환시키는 행렬로 생각을 한다면, A의 역행렬은 A를 단위행렬로 만드는 행렬이다. 가우스-조르단 소거법의 과정은 A를 단위행렬로 변환시키는 과정이다. 그 과정에서 최종식의 오른쪽에는, A를 단위행렬로 변환시키는 연산이 남아있고, 그 연산은 A의 역행렬이라고 말할 수 있을것이다.

사실 가우스 조르단 소거법은, 우변을 각각 (1,0), (0,1)을 잡고 a,b에 대한 해를 구하는 식이다. 이걸 생각하면 만약, (1,0), (0,1) 이 아니고 (2,5), (-1,3)같이 다른 값을 넣어두고 똑같은 방법을 수행하면 다른 방정식의 해를 구할 수 있을 것이다. 사실 해를 구하는 과정에서 왼편을 단위행렬로 만들기 때문에 역행렬이 곱해지는 과정은 동일하다.

가우스-조르단 소거법은 역행렬이 곱해져도 변하지 않게 하기 위해, 구하려는 값을 특별히 (1,0), (0,1)로 둔 것 뿐이다.

구하려는 값을 (1,0), (0,1)외에 다른 값을 넣어서 가우스-조르단 소거법을 해보자.

이번 강의에서는 Elimination & Back substitution에 대해서 배우고, Row picture와 Clomun picture에서의 방정식, 벡터간의 연산을 어떻게 행렬안에서 표현하는지, 그리고 Augmented Matrix, Permutation Matrix에 대해서 배운다.

Elimination & Back substitution

복습할겸, 다음과 같은 관계를 Row picture와 Column picture로 표현해보자.

위와 같이 생각했다면, 정답이다.

위의 예제를 다시보면, 3개의 방정식이 있고, 3개의 미지수가 있다. 예전에 중학생 때 배운 수학을 다시 되새겨보자. 방정식을 풀 때 우리는 하나의 식을 정하고, 그 식에 어떤 상수를 곱한 다음, 그 식을 다른 식에 더하거나 빼서 미지수를 제거하였다. 그렇게 해서 운이 좋아서, 한 번의 시도 끝에, 한 관계식에 하나의 미지수만 남았다면 그 미지수를 알 수 있었고, 하나의 미지수만 제거되어 2개의 미지수만 남았다면, 그 중 하나의 미지수를 제거해 최종적으로 한 개의 미지수에 대한 값을 알기위한 연산을 하였다. 이 과정을 모든 미지수를 알 때 까지 반복하였다. 우리도 모르게 우리는 Elimination & Substitution을 하고 있었다.

Elimination

이 과정을 선형대수적 관점에서 살펴보자. 위에서 우리가 계산했던 Row picture을 다시 가져오자.

그림을 보면 First pivot이란게 추가 되어있다. n’th Pivot(n번째 피벗)이란 행렬의 n번 째 행에서 최초로 0이 아닌 원소를 의미한다.

우리는 첫 번째 피벗 아래의 모든 원소의 값을 0으로 만들고 싶다고 하자. (여기서, 첫 번째 피벗 아래의 모든 원소란, 첫 번째 피벗을 제외한 1열의 모든 원소를 말한다.)

3행 1열의 원소는 이미 0 이므로, 2행 1열의 원소만 0으로 만들어주면 된다. 우리가 방정식을 풀 때, 한 원소만 건드는게 아니고, 관계식 전체끼리 연산을 하였으므로, 여기서의 원리도 그와 같다. 다음 연산을 하고 나면 Row picture는 어떻게 변화할까?

다음과 같이 변해있을 것이다.

이렇게 되면, 첫 번째 피벗 아래의 모든 원소는 0이 되어있다.

그 다음에는 두 번째 피벗에 대해서도 다음과 같은 연산을 똑같이 진행한다. 그 결과는 다음과 같다.

그리고 세 번째 피벗은 마지막 피벗이므로 해당 연산의 반복을 종료한다.

강의 중 살짝 언급된던 것이지만, 만약, 마지막 pivot이 0이라면(Failure), 그 행렬은 역행렬이 없다고 한다. 그리고 만약, 마지막 피벗이 아닌, 중간 번째 pivot이 0이 나온다면(Failure), 밑에 행과 바꿔치기하여 연산을 다시해야 한다.

다시 돌아와서, 위 과정까지 수행했다면 우리는, Elimination 과정을 완료한 것이다. 이제 우리는 Back substitution을 수행해야 한다.

Back substitution

이 과정은 간단하다. 마지막 피벗부터 살펴보면 된다. 마지막 행을 본다면 5z=-10이라는 것을 알 수 있다. 그렇다면 z=-2 이다. 이제 두 번째 행으로 가자. 밑에서 z=-2 이라는 것을 알았으므로, z를 대입하면, 미지수는 y하나만 남으므로 y의값을 알 수 있다. y=2이다. 같은 방식으로 첫 번째 행으로 가서, 같은 연산을 수행하면 x=0 이 계산된다. 이 과정이 back substitution이다.

Augmented Matrix

Aumgented Matrix(확장행렬)은 다음 그림 한 장으로 설명을 대신한다.

Row, Column operation

Row, Column operation

위 그림에서 보여지는 두 가지 연산을 봐보자. 두 가지 연산 모두, Elimination과 관련된 연산은 어느것일까? 바로 두 번째 연산이다. 두 번째 연산이 어떻게 Elimination연산과 관련이 있을까? 바로 단위 행렬을 이용하면 알 수 있다.

만약에 우리가 전에 수행했던 row2 = -3xrow1 + row2연산을 수행하려면 어떻게 해야할까? 다음과 같이 바꿔주면 된다.

이렇게 연산이 수행되는 이유는 제일 처음 보여줬던 연산의 의미를 잘 고민해보면 알 수 있다.(아니면 직접 계산을 해보자!) 그 후, row3 = -2xrow2 + row3연산을 하려면 어떻게 해야할까? 결과는 다음과 같다.

그렇다면 처음부터 지금 까지 연속적인 연산(선형변환)은 다음과 같이 쓸 수 있을 것이다.

Elimination과 상관은 없지만 여기서는 행 끼리 연산을 나타냈다. 만약 열 끼리 연산을 표현하고 싶으면 어떻게 해야할까? 단순하게 변환행렬을 왼쪽에 두는게 아니고, 오른쪽에 두면 된다.

Permutation Matrix(치환행렬)

위의 과정을 이해했다면, 치환행렬은 매우 이해하기 쉽다. 치환 행렬은, 행 또는 열의 위치를 서로 바꿔주는 행렬을 의미한다. 설명은 다음 그림 한장으로 대신한다.