Fundamentals/Linear Algebra

[Linear Algebra] Lecture3, 행렬곱셉(Matrix multiplication), 역행렬(Inverse matrix) 그리고 Gauss-Jordan

츠벤 2016. 11. 19. 22:44

지난 강의에서 행렬 곱셈(Matrix multiplication)에 대해서 다루었다. 이번 강의에서는 행렬 곱셈과 그 규칙에대해 좀 더 알아보고

역행렬과 Gauss-Jordan이 제안한 소거법을 이용해 역행렬을 구하는 방법에 대해 알아보도록 하자. 

 

 

1. 행렬 곱셈(Matrix multiplication)

 

- row*column: 

 

이번 section에선 행렬 곱셈을 총 네 가지 관점에서 살펴볼 것이다. 먼저 살펴볼 것은 row*column의 방법이다. 

아래 두 개의 행렬이 어떻게 곱해지는지를 살펴보자. 행렬 A와 B가 있고 곱해진 결과를 C라고 해보자. 

C에서 c32, 즉 C에서 row3, column2에 존재하는 원소는 어디로부터 어떻게 만들어지는가? 

 

 

 

 

바로 행렬 A의 row3과 행렬 B의 column 2와의 곱으로부터 만들어진다. 이 곱을 우리는 A의 row3와 B의 column2의 벡터의 내적(dot product)이라고 볼 수 있다. 이 dot product 과정을 다시 써보면 식(2)와 같다. 

 

A의 row3의 첫 번째 원소 a31은 B의 column2의 첫 번째 원소 b12와 곱해진다. 이 값은 두 번째 원소들 a32와 b22의 곱의 값에 더해진다. 이렇게 n개의 각 원소까지 곱하고 더하는 과정을 거쳐 c32값이 계산되어진다. 이를 일반적인 형태로 작성하게 되면 식 (2)의 세 번째 줄과 같아진다. 

 

 

그렇다면 C의 모양은 어떻게 될까? 만약 A와 B 둘다 정방행렬(square matrix)인 경우 row와 column의 수가 같기 때문에 결과 행렬인 C도 같은 모양을 취하게 된다. 

그러나 A가 3x4(row3, column4)인 반면 보다시피 B는 4x3로 모양이 다르다. 그런데 C의 모양은 3x3인 정방행렬이다. 어떻게 이러한 결과가 나온 것일까? 

 

식 (1)을 보자. 곱해지는 두 행렬 중 앞쪽에 위치한 행렬은 mn이 되어야 하고 그 다음 행렬은 n x p가 되어야 한다. 이때 곱의 결과 모양은? m (rows of A) x p (columns of B) 가 된다. 결국 행렬 C는 A의 m=3, B의 p=4에 의해 3x4로 된 것이다. 

또한 어떤 행렬 둘을 곱한다고 했을 때, n의 크기는 반드시 같아야 한다. 

 

지금까지 살펴본 내용은 행렬 곱셈을 하는 가장 일반 적인 방법이다. 고등학교때 배웠던 행렬의 연산은 대부분 이 방식을 배웠을 것이다. 똑같은 연산을 좀 더 다른 관점에서 살펴보도록하자. 전체 row혹은 column-wise의 꼴로 행렬 곱셈을 살펴보는 관점에서 말이다. 

AB=C를 다시 한 번 써보자. 

 

 

- column-wise: 

 

 

 

 

A와 B의 곱을 column의 관점에서 살펴보도록 하자. 행렬 A가 B의 각 column 별로 곱해진다고 생각해 봤을 때, 즉 행렬 A 전체와 B의 각 column 벡터와의 곱으로 생각해 봤을 때 이 곱셈의 결과는 C의 column이 된다. 식 (3)에서 행렬 A와 B의 청록색 column을 곱하면 그 결과는 C의 청록색 column이 되고, 행렬 A와 B의 두 번째 column인 녹색 부분을 곱하면 C의 두 번째 column인 녹색이 되는 것이다. 이를 식으로 나타내면 (4)와 같다. 이것이 위 식을 column별로 보는 것이다. 

 

 

이것이 말하는 것이 무엇일까? 이는 바로 C의 column들은 A의 column들의 조합이라는 것이다. (개념이 조금 헷갈리시는 분들은 Lecture2의 식(14)를 참조하면 이해가 갈 것이다!) 이는 C의 각 column의 벡터 길이(=m)가 A의 column의 벡터 길이(=m)와 같음을 봐도 알 수 있다.  

 

 

- row-wise: 

 

 

이번엔 똑같은 행렬을 row의 조합 관점에서 살펴보자. 식 (5)를 살펴보면 C의 row3는 A의 row3와 행렬 B와의 곱으로 나타내어진다. 

이를 마찬가지로 식으로 나타내면 식 (6)과 같다. 

 

 

column-wise와 비교해보면 column일 때는 행렬 A와 B의 column의 곱으로, row-wise일 때는 A의 row와 B와의 곱으로 C의 column과 row가 각각 정의되었다. row-wise를 다시 정의한다면 C의 row들은 B의 row들의 조합이다. 

 

즉 식(5)의 경우에서 a31*B(row1) + a32*B(row2) + ... 와 같은식으로 B의 모든 row마다 A의 row3의 각 원소들이 계수처럼 곱해져서 C의 row3이 만들어지는 것이다. (역시 개념이 헷갈린다면 Lecture2의 식(17)참조!)

 

 

 

- column*row: 

 

네 번째로 살펴볼 것은 column벡터와 row벡터의 곱셈 형태이다. 

맨 처음에 살펴봤던 형태(row*column)와 그 순서가 반대이다. row*column형태에서는 곱셈의 결과가 단 하나의 값(scalar)으로 나왔으며 이는 내적(dot-product)라 하였다. 그렇다면 그 반대는 어떻게 될 것인가? 분명히 row*column의 결과와는 다를 것이다. 다음을 보자. 

 

 

 

위에서 예를 들었던 AB=C에서 A의 column은 어떤 모을 갖는가? 바로 m개의 row원소가 1개의 column을 이루는 모양이다. 

B의 row는 반대로 p개의 column원소가 1개의 row를 이루는 모양이다.  

 

그렇다면 이들의 곱셈 결과는 어떤 모양이 될 것인가? 결론부터 말하자면 하나의 full size의 큰 행렬이 만들어진다. 아래의 예를 가지고 실제로 계산을 해보자. A는 3x1의 column 벡터이고 B는 1x2의 row벡터이다. 결과는 오른쪽과 같이 만들어지는데, 어떻게 이런 결과가 나오는 것인가? 

 

 

 

앞서 배웠던 row-wise와 column-wise를 생각해보면 쉽게 계산할 수 있다. 

 

row-wise인 경우...

a11*B(row1)=[2  12], 

a21*B(row2)=[3  18],

a31*B(row3)=[4  24]

와 같이 계산된다. 

 

column-wise인 경우...

A(col1)*b11=[2    3   4]T, (T는 transpose를 의미)

A(col1)*b12=[12 18 24]T

와 같이 계산된다. 

 

네 번째 방법을 다시 정리하자면..  행렬곱셈 AB는 A의 column * B의 row의 합이다. 

 

좀 더 일반적인 예를 들어보면 두 개의 column과 두 개의 row인 경우를 들 수 있다. 이 경우 A의 col1과 B의 row1, A의 col2와 B의 row2의 합으로 나타낼 수 있다. 두 번째 텀은 0과 곱해지기 때문에 무시하고 결과는 식(8)과 같다. 

 

 

 

여기서 한 가지 짚고 넘어가야 할 부분이 있다. 식 (8)을 다시 보자. 

 

 

위 곱셈의 결과 행렬 C는 굉장히 특별한 행렬이다. 혹시 무엇인가 보이는가? 그 특별한 점은 바로 

C의 모든 row는 B의 row를 따라 같은 line 선상에 존재한다

C의 모든 column은 A의 column를 따라 같은 line 선상에 존재한다.

 

결국 식(8)의 결과 행렬은 rank가 1인 행렬이다. (rank는 이후 포스팅에서 다룰 예정: linearly independent한 row or column의 수)

 

위 행렬이 진짜로 같은 라인에 존재하는지 구현해보자. 아래는 MATLAB으로 해당 row 벡터들을 시각화한 결과이다. 세 벡터들이 같은 선상에 존재하기 때문에 앞에서 그려졌던 벡터들은 이후에 그려진 벡터들에의해 가려져 보이지 않음을 알 수 있다. 

 

 

 

 

아래 결과 사진은 column벡터를 그린 것이다. 역시 처음 그려진 벡터가 겹쳐서 보이지 않음을 알 수 있다. 실제로 코드를 돌려서 돌려보며 확인해 보도록하자. 

 

 

 

 

**결국 어떠한 벡터이던간에 column*row인 경우 위와 같은 특별한 행렬이 만들어지게 된다. 이를 잘 기억해 놓자. 

 

 

아래는 구현 코드이다. 

 

Row 출력 코드

 

Column 출력 코드

 

 

- Block Multiplication: 

 

행렬 곱셈의 형태 중 마지막으로 살펴볼 것은 블록(Block)단위의 행렬 곱셈 방법이다. 예를 들어 20x20크기의 행렬이 있다고 가정했을 때, 이를 10x10 네 개로 분할하여 똑같이 행렬 곱셈을 적용해도 같은 결과가 나온다. 아래 행렬을 보자. 

 

 

 

 

행렬 A는 20x20의 크기를 가지고 있고 이 행렬들을 10x10 크기의 Block으로 나눈다. 이때 각 Block(A1, B1....)을 하나의 원소로 생각하고 행렬 연산을 해주면 기존 행렬 연산과 똑같은 결과가 나오게 된다. 예를 들면 아래와 같은 연산을 참고하면 쉽게 이해할 수 있다. 

 

 

 

 

 

2. 역행렬(Inverse Matrix)

 

- Invertible, nonsingular case:

 

이제 역행렬을 계산하는 법을 살펴보겠다. 우선 정방행렬(square matrices)에 대해 생각해보자. 어떤 정방 행렬 A가 있다고 생각했을 때, 이 행렬의 역행렬이 존재(invertible, nonsingular)한다고 가정하자. (역행렬은 존재할수도, 존재하지 않을 수도 있다)

 

이때의 관계를 아래와 같이 쓸 수 있다. 행렬 A에 역행렬을 곱해주면 그 결과는 단위행렬(identity matrix)이 된다. 또한 이 역행렬을 오른쪽에 곱해줘도 결과는 같다. 

 

 

행렬은 곱셈의 순서에 따라 결과가 달라진다는 것은 이미 알고 있을 것이다. 따라서 역행렬을 앞에 곱하는 결과와 뒤에 곱하는 결과는 당연히 달라질 것이라고 생각하는데, 일반적인 행렬(Rectangular Matrix)인 경우에는 이것이 맞다. 하지만 정방행렬(Square Matrix)인 경우에는 식(12)와 같이 앞에 곱하나 뒤에 곱하나 그 결과가 같다. MATLAB에서 inv() 명령어로 확인해보면 바로 알 수 있다. 

 

 

 

- no inverse, singular case

 

이번엔 역행렬이 존재하지 않는 경우를 살펴보자. 이를 다른 말로 특이행렬(singular matrix)라고도 한다. 아래의 행렬 A를 보자. 아래 행렬 A는 역행렬이 존재하지 않는 특이행렬이다. 그렇다면 왜 역행렬이 존재하지 않는 것일까?

 

 

우리는 위 행렬 A의 역행렬이 존재하지 않는 다양한 이유를 찾을 수 있다. 어떤 것들이 있을까?

 

이후 포스팅에서 따로 다루겠지만, 먼저 행렬 A의 행렬식(determinant)은 0이 된다(1/(ad-bc)). 따라서 역행렬이 존재하지 않는다. 

 

이것 보다는 좀 더 좋은 이유가 필요하다. 또 다른 이유는 뭐가 있을까? 행렬 A의 column picture를 살펴보자. 혹시 무엇이 보이는가? 이전 포스팅을 잘 공부한 분이라면 행렬 A의 각 column들이 같은 line상에 위치한다는 것을 알 수 있다. 즉 두 column은 똑같은 방향을 가르키고 있는 것이다. 

 

A의 rank는 1이며 선형 독립(linearly independent)인 차원의 개수가 A의 차원보다 작기때문에 특이행렬이다. 따라서 행렬 A로는 2차원이 아닌 오직 line만 표현이 가능하다. A의 column 1인 [1 2]T벡터에 상수 3을 곱해주면 바로 column 2인 [3 6]T벡터가 나오는 것을 확인하면 알 수 있다. row도 마찬가지다.

 

이를 확인할 수 있는 또 다른 방법은 각 column을 정규화(normalization)해서 같은지 비교해 보는 것이다. A의 column 벡터들의 2-norm 정규화식 (14)를 실제 계산해서 확인해보기 바란다.

 

 

 

그런데 또 다른 이유가 있다. 이것이 가장 중요한 이유인데, 잘 기억해두도록 하자. 그것은 바로..

 

**만약 를 만족하는 벡터 x를 찾을 수 있다면, 그 행렬은 역행렬이 존재하지 않는다. (이때 A는 정방행렬, x는 0이 아닌 벡터)**

 

다시 말하면, 당신이 어떤 정방행렬 A에 대해서 그 행렬에 어떤 0이 아닌 벡터 x를 곱했을 때 우변이 0벡터가 된다면 그 행렬은 역행렬을 만들 수 없다(not invertible, singular case).  

 

식(13)의 행렬 A는 우변을 영벡터로 만들 수 있는 x가 존재하는가? x=[3 -1]T 를 곱하면 우변이 영벡터가 된다. 

 

자 이를 다시 생각해보자. 

스템 A가 어떤 벡터 x를 0으로 보냈다. 이럴 경우, 이렇게 0으로 보낸 x를 다시 원래의 위치로 돌아오게끔 하는 시스템이 존재하는가?를 생각해보자. 선형대수에서의 연산은 선형 결합, 즉 변수에 어떤 계수들을 곱하고 더해서 계산 되는 것인데, 애초에 변수 자체가 0이 되어버렸으면 어떤 계수들을 곱해도 이를 복원시킬 방법이 없는 것이다. 

 

위 시스템 A의 경우 2차원 상의 벡터인 x를 곱할 경우 이를 1차원 상의 공간으로 보내버린다. 게다가 0으로 만들어버리는 경우도 있는 것이다. 이런 상황에서 원래 지점으로 되돌리는 역행렬이 존재한다는 것이 말이 될 것인가? 선형 시스템을 다루는 선형 대수에서는 어불성설(語不成說)이

 

위의 개념을 잘 이해하기를 바란다.

(※ 정방행렬이 아닌 임의의 직사각 행렬(Rectangular Matrix)은 pseudo inverse라는 방법을 이용해 계산해야 한다. 이와 관련해서는 이후 포스팅에서 다룰 예정)

 

 

 

- Gauss-Jordan idea

 

이제 다시 돌아가서 역행렬이 존재하는 경우를 살펴보자. 행렬 A를 다시 아래와 같이 정의하자.  

 

 

식 (15)의 행렬 A에 대해 위에서 다룬 역행렬이 존재하지 않는 경우에 대한 방법들을 적용해보자. 행렬식(determinant)은 0이 아니고, 각 column들은 서로 다른 방향을 가리키고 있다. 또한 Ax=0를 만족하는 x를 찾을 수 없다.

 

자 이제 A가 역행렬을 가질 수 있음을 알았다. 그럼 이제 실제로 어떻게 역행렬을 구할 수 있을까? 행렬 A에 역행렬을 곱하면 그 결과는 단위행렬 I가 되어야한다. 아래 식을 보자. 

 

 

위 식을 식(13)처럼 두 개의 column-wise 시스템으로 분리해서 생각해보자. A와 첫 번째 column인 [a b]T를 곱하면 I의 첫 번째 column인 [1 0]T이 되어야 한다. 마찬가지로 A*[c d]T = [0 1]T 이다. 이러한 관계를 정리하면 행렬 A와 그 역행렬의 j번째 column을 곱하면 I의 j번째 column이 나온다. 

 

 

식 (16)을 다시 써보면...

 

 

위와 같이 하나의 식을 두 개로 분리해서 생각할 수 있다. (18-1)과 (18-2)를 풀 수 있다면 행렬 A는 역행렬이 존재한다. 이것이 Jordan's idea의 시작이다. 

 

지난 Lecture 2에서 Gauss소거법을 배웠다. 소거법 과정에서 우변의 extra column 벡터를 오른쪽에 붙여서 만든 Augmented Matrix를 기억하는가? 이때 우리는 우변의 extra column 벡터 하나만 붙였다. 하지만 여기에 column을 하나 더 붙여서 아래 형태의 행렬을 만들어보자. 즉 (18-1), (18-2)를 붙여서 한 번에 풀어보자는 것이다. 

 

 

식 (19-1)를 지난 포스팅에서 배운 Gauss소거법을 활용해 소거해보자. 첫 번째 pivot을 설정하고 아래에 있는 원소들을 소거하기 위한 E 행렬을 만들어 곱해주자. 소거할 원소가 A의 row2, col1이므로 E21이다. row1에 -2를 곱해주고 row2에서 빼주면 소거 되므로 식은 아래와 같다. (Elimination matrix를 만들 땐 row-wise로 생각하면 쉽다)

 

 

식 (19-2)의 A의 결과는 상삼각행렬(upper triangular matrix)이 완성되었다. Gauss는 여기서 끝냈다. 하지만 Jordan은 여기서 소거를 더 진행했다. 지금까지 위에서 아래쪽으로 소거를 해 왔다면 이젠 반대로 아래에서 위쪽으로 소거를 진행하는 것이다. 즉 (19-2)에서 두 번째 pivot을 잡았는데 여기서 진행방향을 위쪽으로 잡는 것이다. 이렇게 되면 A의 row1, col2의 원소인 3을 제거한다. 이때 E행렬은 E12가 되며 현재 pivot에 3을 곱하고 row1에서 빼주면된다. 정리하면 아래 식과 같이 된다. 

 

 

 

식 (19-3)의 결과를 보면 원래 A가 있던 곳은 단위행렬로, 원래 단위행렬이 있던 곳은 어떤 행렬이 되었다. 이 어떤 행렬은 바로 A의 역행렬이다. 검증을 위해 여기에 A를 곱해보면 단위행렬이 나오는 것을 확인할 수 있다. 

 

어떤 행렬을 소거 하기 위해선 단계별로 제거 행렬(Elimination matrix)을 곱해줘야 한다. 위 예에선 E21과 E12가 그 예인데, 이 둘을 곱해주면 최종적인 E 행렬이 완성된다. 어떤 결과가 나오는지 살펴보자.

 

 

E행렬을 원래의 A 행렬에 곱해보자. 어떤 결과가 나오는가?

 

 

결국 E행렬은 A의 역행렬이다

 

 

 

 

3. 마치며...

 

이번 포스팅에선 행렬 곱셈(Matrix multiplication)과 역행렬(Inverse matrix)을 계산하는 방법을 배웠다. 행렬 곱셈에선 row*column, column-wise, row-wise, column*row의 네 가지 연산 방법을 살펴보았으며 각각의 특성과 그 의미를 파악하였다. 

역행렬에선 역행렬이 존재하는 경우와 존재하지 않는 경우를 살펴보았고 Gauss-Jordan의 소거법을 통해 실제로 역행렬을 계산하는 방법을 배웠다. 

 

이상으로 Lecture 3를 마칩니다.