• Elimination - Success / Failure
• Eliminatioin Matrices
• Matrix Multiplication

Elimination - Success / Failure

• Success

다음과 같은 방정식이 주어졌다고 가정하자. $x + 2y + z = 12$ $3x + 8y + x = 12$ $4y + z = 2$

이 방정식을 풀 때 upper triangle 형태로 만들면 쉽게 unknown들을 찾을 수 있다. upper triangle을 만드는 과정은 다음과 같다.

1. 우선 A와 b를 합친 형태의 matrix를 형성한다. 이와 같이 서로 다른 matrix를 하나의 matrix로 합친 형태를 augmented matrix라고 한다.
2. Upper triangle을 만들기 위해 우선 (2,1) position 값을 0으로 만들 필요가 있다. 이를 위해 $3\cdot row1$ 을 $row2$에서 빼준다.
3. 비슷한 방식으로 (3,2) position을 0으로 만들기 위해 $2\cdot row2$를 $row3$에서 뺀다.

이렇게 생성된 matrix는 A에 위차하는 부분이 upper triangle이 되고, 앞으로 이러한 matrix를 $u$(Uppper triangle matrix), $b$에 해당하는 column은 $c$라고 지칭한다.

Matrix에서 특정 column position의 아래 값이 전부 $0$인 경우 해당 column의 $0$이 아닌 가장 아래 값을 pivot이라고 칭한다.

이렇게 생성된 $u$를 이용하면 back-substitution을 통해 아주 쉽게 unknown들을 찾을 수 있다.

• Failure

이러한 방식으로 항상 solution을 찾을 수 있는 것은 아니다. 만약 upper triangle을 형성하는 과정에서 특정 row가 모두 0이 되는 경우, 해당 연립방정식의 해는 찾을 수 없다.

Elimination Matrices

Elimination matrix는 행렬 내 특정 값을 0으로 만들기 위해 사용되는 행렬을 뜻한다. 위 그림의 과정에서 elimination matrix가 사용되는 것을 나타내면 다음과 같다.

여기서 각 $E_{row,col}$는 $row$행 $col$열에 해당하는 poisition의 value를 $0$으로 만들기 위해 사용되는 elimination matrix를 의미한다.

이와 같은 elimination matrix는 다음과 같이 나타내는 것도 가능하다. 행렬에서 mutiplication order가 바뀌지 않는다면 두번째 항과 같이 괄호 위치가 변경 가능하다.(Associative law) 따라서 elimination matrix를 하나의 행렬 형태로 나타내는 것이 가능하다. 하지만 elimination matrix 여러개를 곱하여 하나의 elimination matrix를 계산하고 이를 통해 unknown들을 찾는 방법은 비효율적이다. 이를 좀 더 효율적으로 수행하는 방법은 다음 게시물에서 소개한다.

Matrix Multiplication

여기서는 몇가지 유용한 matrix multiplication들에 대해 소개한다.

Column multiplication 각 column을 특정 multiplier로 곱해주는 경우에 사용 ( 각 column에 순서대로 3, 4, 5를 곱하는 예제 )

Row multiplication 각 row를 특정 multiplier로 곱해주는 경우에 사용 ( 각 row에 순서대로 1, 2, 7을 곱하는 예제 )

Permutation matrix 행렬 요소의 위치를 바꾸는데 사용되는 행렬. 각 열에는 하나의 1과 0으로만 이루어진다.

다음 두가지 사항에 대해서도 추가로 꼭 기억하자.

1. Column에 대해 연산 혹은 행렬 조작이 수행되는 경우는 Matrix 앞에 multiplier 위치
2. Row에 대해 연산 혹은 행렬 조작이 수행되는 경우는 Matrix 뒤에 multiplier 위치

이번 Lecture에서는 linear equation의 geometry에 대해 이야기한다.

• $n$ equations, $n$ unknowns
• Row picture / Column Picture / Matrix Form

2-D case

$2x-y = 0\ -x+2 = 3 $

위 equation을 row picture로 나타내면 다음과 같다. $$\begin{bmatrix} 2 & -1\ -1 & 2 \end{bmatrix} \begin{bmatrix} x\ y \end{bmatrix} = \begin{bmatrix} 0\ 3 \end{bmatrix} $$

위 행렬에서 $$\begin{bmatrix} 2 & -1\ -1 & 2 \end{bmatrix}$$=$$A$$, $$\begin{bmatrix} x\ y \end{bmatrix}$$=$$\text{x}$$, $$\begin{bmatrix} 0\ 3 \end{bmatrix}$$=$$b$$ 라고 했을 때 다음과 같은 equation으로 나타 낼 수 있다.

• $$A\text{x}=b$$

Row picture에서는 좌표 평면을 그려서 각 equation에 해당하는 직선을 그려 교점을 찾는 방식으로 $x$와 $y$ 값을 찾을 수 있따.

같은 equation을 column picture로 나타내면 다음과 같다.

• Linear combinations of columns $$ x \begin{bmatrix} 2\-1 \end{bmatrix}
• y \begin{bmatrix}
• 1\2

  \end{bmatrix}

  \begin{bmatrix} 0\3 \end{bmatrix} $$

Column picture에서는 $$\text{x}$$를 찾기 위해 각 unknown을 vector에 매칭시켜 문제를 해결한다.

여기서 중요한 점은 모든 가능한 $$b$$에 대하여 $$\text{x}$$를 고려하면 이는 xy 평면을 형성한다는 것이다.

3-D case

$ 2x-y=0\ -x+2y-z=1\ -3x+4z=4\ $

이 때, $$ A = \begin{bmatrix} 2 & -1 & 0\ -1 & 2 & -1\ 0 & -1 & 4 \end{bmatrix}, b = \begin{bmatrix} 0\-1\4 \end{bmatrix} $$

같은 방식으로 3-D에서

3개의 방정식을 row picture로 나타내고 좌표 공간에서 $$\text{x}$$를 구할수는 있지만, 2-D case에 비해 visualization시의 명확성이 떨어지고 차원이 커질 수록 이러한 경향은 더 심해진다.

하지만 이러한 문제는 column picture로 생각하면 단순히 $$\text{x}$$ 값을 찾는데 집중 할 수 있어 훨씬 쉬워진다.(Gilbert Strang의 경우 column picture를 선호한다고 함)

우리는 다음과 같은 질문을 던질 수 있다.

• Can I solve $$A\text{x}=b$$ for every $b$?
• Do the linear combinations of the columns fill 3-D space? (in 3-D case)

이에 대한 답은 현재 주어진 case의 $$A$$에 대해서는 YES 이다.

하지만 어느 한 원소가 나머지 vector들로 인해서 생성되는 평면 위에 존재하는 경우 해당 equation들로는 3-D space를 생성 할 수 없다.

n-D case

n차원에서도 기본 logic은 동일하다. $n$개의 vector가 존재 할 때, 각 vector들이 나머지 vector들로 생성되는 n차원 space에 속하지 않는다면 linear comb.를 통해 n-D space를 형성 할 수 있다.

아주 기초적인 내용이었지만 row picture와 column picture의 구분을 통해 linear combination을 직관적으로 설명하는 부분이 매우 인상적이었다.