Elimination with Matrices

선형 시스템 A에 관한 해(solution)를 구하는 방법론이 소거법(Elimination)이다.
이 방법은 수학자 Gauss의 아이디어이며, 선형대수를 다루는 소프트웨어들은 모두 이 방법을 사용한다.
이 소거과정은 방정식을 함의한 행렬 형태(Matrix form)으로 표현된다. 이 때 소거과정을 연산하는 행렬을 소거행렬(Elimination matrices)라고 한다.

Elimination

Augmented matrix를 통해 REF인 행렬 u를 생성.

Success

REF이 0인 pivot 없이 Upper triangular matrix로 나올 때.

Failure

pivot이 0인 경우 Row exchange를 통해 소거한다. 이 때 exchange하는 pivot column이 0이어선 안된다.

Row exchange를 통하여 생성된 REF에 zero row가 존재하지 않으면 non-singular, invertible한 행렬이다.
그러나 zero row가 존재한다면, singular, non-invertible한 행렬이다.

Back-substitution

Augmented matrix인 [A | b] 를 이용해 A를 REF인 u로 만들고, 이 결과에서 각각의 row를 다시 방정식화 하면, 맨 아래의 row부터 각 row당 한개의 미지수를 구하여 다시 위로 대입할 수 있게 된다.
결과적으로 모든 미지수를 구할 수 있게 된다.
만약 이를 RREF로 만들었을 때 I가 되면 [I | solution], 즉 그냥 우측의 벡터가 솔루션 벡터가 된다.

Elimination matrices and Matrix Multiplication

역행렬을 구하기 위한 초석이다. EA->u 인 E를 구하는것이 목표.
하삼각 행렬인 Elementary matrix와 Permutation Matrix를 조합해서 만들어진 것이 Elimination matrix인 E이다.

Multiplication and Inverse Matrices

먼저 행렬간 곱셈을 네가지 관점에서 살펴보고, 역행렬에 다뤄본다.

Matrix Multiplication

이제까지 행렬과 벡터의 곱셉에 대해 다루었으나, 이젠 행렬과 행렬의 곱셉에 대해 살펴본다. 사실 마찬가지다.

row*column

내적

column-wise

AB=C
C의 column은 A의 column들의 combination이다.
이 때 B의 column이 coefficient vector가 된다.

row-wise

AB=C
C의 row는 B의 row들의 combination이다.
이 때 A의 row가 coefficient vector가 된다.

column*row

rank 1의 행렬이 된다.

Block Multiplication

행렬을 구획으로 나누어 묶더라도, 하나의 element와 같은 방식으로 취급하여 계산할 수 있다.

Inverse Matrix

역행렬은 non-singular, invertible matrix인 경우에만 존재한다.
\(A^{-1}A=I=AA^{-1}\)
교환법칙은 성립한다.

singular, non-invertible case

특이행렬(singular matrix)은 역행렬이 존재하지않는다.
정방행렬(square matrix)이면서 full rank인 행렬만이 역행렬이 존재한다.

중요한 점은, \(Ax=0\) 을 만족하는 영벡터가 아닌 벡터x가 존재한다면, A는 singular matrix라는 것이다. 이는 필요 충분 조건이다.
이는 양변에 A 역행렬을 곱해보면 모순임을 쉽게 보일 수 있다.

Gauss-Jordan Elimination

역행렬이 존재하는 경우 Gauss-Jordan Elimination을 통해 역행렬을 구할 수 있다.
Gauss-Jordan Elimination은 Gaussian Elimination과 비슷한 아이디어를 공유하는데, Gauss Elimination이 해를 구하는 데에 사용된다면, Gauss-Jordan Elimination은 해를 구하는 과정을 이용해 역행렬을 구하는데 사용된다.

다음 x1, x2를 구해야 한다고 생각하면 Gauss Elimination과 같다.
\(Ax_1= \begin{bmatrix} 1 \\ 0 \\ \end{bmatrix}\)
\(Ax_2= \begin{bmatrix} 0 \\ 1 \\ \end{bmatrix}\)

그런데, \([x_1 x_2] = X\) 라고 두면,
\(AX=I\)
와 같고, 즉 \(X=A^{-1}\)이다.

결국 우변에 I를 두고 X의 해를 구하면 A의 역행렬을 구할 수 있게 되는 것이다.

이는 Augmented Matrix를 \([A | I]\) 로 두고 좌측 행렬을 I로 만드는 Elimination Matrix를 양쪽에 곱해주면 된다.
단순히 좌측 행렬을 I로 만드는 연산을 양쪽에 동일하게 해주기만 하면 된다.(이 연산을 row reduce라고 하는데, 이 과정을 거치고 나면 Reduced Row Echelon Form(RREF)이 된다.)

이는 다음과 같이 표현된다.
\([E][A | I] = [I | E]\)
즉, E가 A의 역행렬인 것이다.

Factorization into A = LU

LU Decomposition은 LU Factoriation이라고도 불린다. Factorization이란 것은 인수분해(Factorization)와 같이 구성요소들로 분해한다는 뜻이다.
사실 이렇게 Decomposite하는 방법은 여러가지다. 그러한 과정을 일반적으로 Matrix Decomposition이라고 하며, 어떤 행렬을 여러 행려들의 곱으로 표현하는 것을 의미한다.

LU분해는 하삼각행렬(Lower triangular matrix)와 상삼각행렬(Upper triangular matrix)의 곱으로 분해하여 나타낸 것이다.

LU분해는 Elimination과 관계가 깊다. 이것은 Gauss Elimination에 의한 Elimination Matrix 형태로 볼 수 있으며, Permutation matrix를 포함하기도 한다. 컴퓨터는 선형 방정식 계산을 할 때 LU Decomposition을 사용하며, 역행렬 계산과 행렬식 계산에도 사용된다.

행렬곱셈의 Inverse와 Transpose

Inverse

\((AB)^{-1}=B^{-1}A^{-1}\)

Transpose

\((AB)^{T}=B^T A^T\)

\(AA^{-1}=I\)
Transpose
\((AA^{-1})^T=I^T\)
\((A^{-1})^T (A)^T = I\)

\[(A^{-1})^T=(A^T)^{-1}\]

LU Decomposition

Matrix Decomposition의 목적은 주로 계산의 편리함과 분석적 용이성을 위함이다. 계산을 간편하게 하고 어려운 문제를 좀 더 쉽게 풀기 위해 이용하는 것이다.

LU Decomposition

정방행렬 A에 소거법을 적용해 최종적으로 U행렬을 만든다고 할 때, A와 U사이의 연결고리를 알고 싶다고 하자. 그 연결고리 역할을 L행렬이 하는 것이다.(그런데 일반적인 사각 행렬에도 적용은 가능함. L이 square matrix가 되고, U는 rectangular matrix로)

\(EA=U\)가 되도록 하는 소거행렬 E가 있을 때,
\(A=E^{-1}U\)로 나타낼 수 있고, 이 E의 역행렬이 L이다.
\(A=LU\)

여기서 L은 Elimination Matrix의 각 요소인 Elementary Matrices의 역행렬의 곱과 같다. 이 때 Elementary Matrices 역행렬의 순서에 주의하여야 한다. 위에서 서술한 법칙에 따라 역행렬들은 순서를 거꾸로 곱하여야한다.

LDU Decomposition

Pivot들을 따로 떼어 분해하고 싶을 때 LDU Decomposition을 할 수 있다. 이 때 U의 pivot값만을 떼서 D에 대각행렬 형태로 담을 수 있다. D가 U의 각 row를 스케일링만 하는 행렬이 되는 것이다.

여기서 D는 Diagonal Matrix의 뜻이다.

building L

row exchange가 없다면, multiplier들은 L행렬의 각자 위치에 그대로 들어가면 된다. 역순으로 계산되기 때문이다. Elementary matrices의 역행렬의 곱이 L이므로, L의 대각성분은 전부 1이다.

Permutations

I를 포함하여 row의 순서를 바꿔주는 행렬을 치환행렬(Permutation Matrix)이라고 한다. Permutation Matrix의 갯수는 nxn 행렬일 경우 n! 개 존재한다.

Permutation Matrix인 \(P\)의 역행렬은 \(P^T\)와 같다.
모든 P행렬은 invertible하다.
Symmetric한 경우 \(P\)의 역행렬은 \(P=P^T\)와 같다.

행교환이 필요한 경우의 LU Decomposition의 경우는 PA=LU 꼴로 분해할 수 있다.

Advantages of LU Decomposition

LU 분해의 이점이 몇가지 있다.

먼저 Ax=b를 LUx=b로 표현할 수 있는데, Ux=y로 두면, 다음으로 Ly=b로 둘 수 있다.
L과 U는 미지수를 구하기 편하도록 정리된 형태이기 때문에 미지수가 많더라도 빠르게 방정식을 풀 수 있게 된다.
이를 factor-solve 접근법이라고 한다.
Ly=b에서 Augmented matrix [L | b]를 만들어 L을 row redcution하면 y가 나오고, [U | y]를 만들어 U를 row reduction하면 x의 solution을 구할 수 있다.

또한 행렬식(determinant)은 LDU분해의 D의 대각 성분의 곱과 같다.

그리고 이 행렬식을 이용해 역행렬의 존재여부를 알 수 있다.

또한 삼각행렬을 이용해 역행렬을 구하는 것도 간단하다.

Transposes, Permutations, Vector Spaces

Permutations

행렬 소거시 pivot이 0인 경우 permutation을 해준다.

Transpose

Symmetirc Matrix

어떤 행렬 S가 Symmetric하다면, \(S^T=S\)이다.

어떠한 행렬 A에 대해서도 \(AA^T=S\)라고 할 때 이는 Symmetric하다. 전치(Transpose)한 결과가 같기 때문이다. Element-wise하게 계산해보아도 같을 수 밖에 없다.

Symmetric Matrix는 그 특성 때문에 다양한 곳에 이용된다.