Linear combination, vector equation, Four views of matrix multiplication

• 아래 내용은 [김도형 박사님의 선형대수 강의안],(https://datascienceschool.net/view-notebook/04358acdcf3347fc989c4cfc0ef6121c/) edwith의 인공지능을 위한 선형대수 강의와 KOCW의 한양대학교 이상화 교수님의 선형대수학 강의를 보고 정리한 내용이다.

• 앞서 언급했던 것과 같이 벡터에 스칼라를 곱하여 더한 조합이 선형 조합이다.

• 아래 그림처럼 일반적으로 연립방정식으로 생각하기 보다는 column form으로 나타내 linear combination으로 나타내는 것이 solution을 찾는데 기하학적으로나 직관적으로 해석하기 더 쉽다. 이제 부터 그 이유에 대해서 살펴 볼 것이다.

• 이전에는 아래 수식에서 Unique한 Solution이 존재하려면 행렬 A에 대한 역행렬이 존재해야 한다고 설명했다. 수식적으로 이해를 했다면 이제는 기하학적으로 살펴보자.

• Solution의 집합이 어떤 형태인지 어디에 속해있는지를 다루기 위해서는 먼저 Vector Space에 대해 알고 있어야한다.

Vector Space

• space : set(집합) closed under addition and scalar multiplication

  • 즉, 덧셈과 곱셈에 대하여 닫혀있는 집합을 Space라고 한다. 위에서의 벡터의 선형조합을 보면 scalar와의 곱셈에의해 닫혀있고 벡터간의 덧셈에 대해 닫혀 있으므로 하나의 space를 갖는다고 볼 수 있다.

• 좀 더 엄밀히 말하자면 다음을 만족해야 한다.

• for any vectors $x, y \in R^{n}$, any scalar $c \in R$

  • 1) $x+y = y+x$
  • 2) $x+(y+z) = (x+y)+z$
  • 3) There is a zero-vector such that $x+o = o+x = x $
    • 여기서 0(zero-vector)는 벡터의 덧셈연산에 대한 항등원이다. 이 처럼 항등원이 있는지를 확인할 경우에는 항상, 교환법칙이 성립하는 지도 확인 해야한다.
    • 위의 사실로 부터 vector Space가 되려면 원점을 포함해야한다는 사실을 알 수 있다.
    • 참고로 원점을 포함하지 않는 공간을 아핀 공간(Affine Space)라고 한다.
  • 4) For each vectore $x, x+(-x) = (-x) + x = o$
    • $-x$ 벡터의 덧셈 연산에 대한 역원이다. 또한 -x는 unique하다.
  • 5) $1 \cdot x=x$
  • 6) $c(x+y) = cx+cy$
  • 7) $(c_{1}+c_{2})x=c_{1}x+c_{2}x$

• 이해가 잘 가지 않을 수 있기 때문에 예시를 들자면 2차 다항함수가 아래와 같이 존재할 때의 vector Space는 3차원이다.

$$\begin{align} a x^{2}+ b x +c \Rightarrow \begin{bmatrix} a \\ b \\ c \end{bmatrix} \in R^{3} \end{align}$$

Subspace

• 임의의 벡터들에 대한 선형조합의 결과도 여전히 그 set에 대해 닫혀 있으면서도 전체 Vector Space에 부분집합을 Subspace라고 한다.

• 임의의 벡터들을 가지고 온갖 종류의 linear combination을 해서 vector space를 만들어 내는 것을 Spanning이라고 하고, 공간을 만든 벡터들은 특정한 vector space를 span한다라고 표현한다.

• all linear combination of vectors $\{ v_{1}, v_{2}, \cdots ,v_{n} \}$ construct a vector space

  • $= \{v_{1}, v_{2}, \cdots ,v_{n} \}$ span vector space

• Span의 개념에 대한 예시는 다음과 같다. 아래와 같은 두 개의 vector를 갖고 어떤 형태로 linear combination을 하던지 span할 수 있는 vector 공간은 x, y 평면이라는 2차원 공간밖에 안된다. 각 벡터의 차원은 3차원이지만 전체 vector space의 차원은 2이다.

• 아래의 벡터들의 linear combination은 2차원 공간(x,y 평면)을 span한다. 똑같은 vector space라고 하더라고 span하는 vector들의 조합은 무한하다.

$$\begin{align} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \end{align}$$

Column Space of A (C(A))

• 임의의 행렬 A의 열 벡터의 모든 선형조합(Linear combination)의 집합을 Column Space라고 한다.

$$\begin{align} A = \begin{bmatrix} a_{1} & a_{2} & \cdots & a_{N} \end{bmatrix} \Rightarrow \sum^{n}_{i=1} c_{i} a_{i} \end{align}$$ $$\begin{align} Ax= \begin{bmatrix} a_{1} & a_{2} & \cdots & a_{M} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{M} \end{bmatrix} = x_1 a_1 + x_2 a_2 + \cdots + x_M a_M = b \end{align}$$

• if $b \in C(A)$, there is at least one solution. else if $b \notin C(A)$
  • 벡터 $x$라는 해가 존재한다는 것은 모든 Combination 중 하나가 벡터 $b$이라는 이야기이므로 벡터 $b$가 column space에 속하면 해가 존재하는 것이고 속하지 않으면 해가 존재하지 않는다.

• span한 결과가 모든 space를 만드러 내느냐 그렇지 않는냐는 행렬 A의 inverse가 존재하느냐 안하는냐에 달려 있다.

$Ax=b$ 에서 unique한 solution이 존재할 조건은 임의의 행렬 $A$에 대하여 역행렬이 존재하는 것이다. 역행렬($A^{-1}$)이 존재한다면 항상 $b \in C(A)$이다.

• left Null space와 상호 보완관계
  • 전체 Space의 차원 = Column space의 차원 + left Null space의 차원

Example) 아래와 같은 행렬 $A$는 역행렬( $ A^{-1} $ )이 존재하지 않기에 모든 3차원 공간의 벡터를 표현할 수 없다. 그러므로 solution은 존재하지 않거나 무수히 많을 것이다.

$$\begin{align} A= \begin{bmatrix} 1 & -2 & 1 \\ 2 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix} \end{align}$$

• 아래 그림에서와 같이 non-zero 벡터이며 서로 상수배로 만들어질 수 없는 3차원 크기의 $v_{1}, v_{2}$ 벡터들은 3차원 상에서 평면을 span한다.

• 만약 벡터 $b$가 column 벡터들의 linear combination으로 표현되어질 수 있다면, column space안에 벡터 $b$가 포함되어있다는 이야기가 된다.

Null Space of A (N(A))

• Set of vectors such that $Ax = 0$,

  • $N(A)=\{ x| A x = 0 \}$

• space는 덧셈과 곱셈에 대하여 닫혀있어야 하므로 다음과 같이 증명해 보일 수 있다.

• 1) closed under addition

  • for $Ax_{1}=0, Ax_{2}=0$ $x_{1}+x_{2} \in N(A)$이려면, $A(x_{1}+x_{2})=0$인지 확인해주면 된다.
  • $Ax_{1} +Ax_{2} = 0 + 0 = 0$ 이므로 $x_{1}+x_{2} \in N(A)$이다.

• 2) closed under scalar multiplication

  • for $Ax=0, for any c cx \in N(A)?$
  • $A(cx)=cAx=0$이므로 $cx \in N(A)$이다.

• Row space와 상호 보완관계

  • 전체 Space의 차원 = Row space의 차원 + Null space의 차원

• 비대칭 구조인 rectangular system에서는 미지수하고 방정식의 개수가 똑같지 않은 비대칭적인 구조이기 때문에 해가 없을 때도 있겠지만 해가 존재하는 경우에는 무수히 많다. 무수히 많은 해 집합인 경우 $Ax=b$에 대한 해는 $Ax=0$인 방정식의 해집합과 상당히 연관이 높은데 그 이유는 $Ax=b$에 대한 해집합은 $Ax=0$인 경우에 대한 해인 Null space와 나머지로 나누어지기 때문이다.

$$\begin{align} \boxed{\begin{matrix} \phantom{} & \phantom{} & \phantom{} & \phantom{} & \phantom{} \\ & & M & &\\ \phantom{} & \phantom{} & \phantom{} & \phantom{} & \phantom{} \\ \end{matrix}} \, \boxed{\begin{matrix} \phantom{\LARGE\mathstrut} \\ v \\ \phantom{\LARGE\mathstrut} \end{matrix}} = \boxed{\begin{matrix} \phantom{} \\ Mv \\ \phantom{} \end{matrix}} \end{align}$$ $$Rectangular system에서의 해집합 = Null space + particular solution$$

• 지금부터 그에 대한 예시를 풀면서 이해해 볼 것이다. 아래 수식에 대한 해집합을 구해보자.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 \\ 2 & 6 & 9 & 7 \\ -1 & -3 & 3 & 4 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align}$$

• 가우스 소거법을 사용하여 행렬을 풀어준다.
  • 첫 번째 행에 2를 곱하여 두 번째 행에 빼준다.
  • 첫 번째 행을 세 번째 행에 더해준다.
  • 위의 2단계를 거치면 아래와 같은 행렬을 얻게 될 것이다.
    • 아래 행렬처럼 $ A_{2,2}=0 $이 되어 pivot이 되지 못하므로 그 다음 0이 아닌 수가 있는 $ A_{2,3} $이 pivot의 자리를 갖는다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 6 & 6 \end{bmatrix} \end{align}$$

• 두 번째 행에서 2를 곱해 세 번째 행에서 빼준다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 \\ 0 & 0 & 3 & 3 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align}$$

• 모든 pivot의 자리를 1로 만들어 주어야 하므로 두 번째 행을 3으로 나누어 준다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align}$$

• 마지막으로 pivot이 존재하는 column에 pivot이 존재하는 자리를 제외하고는 0으로 만들어 주기 위해 위에서 소거해준 방법을 사용하여 정리해준다.
  • 소거해주기 위해 두 번째 행에 3을 곱한뒤 첫 번째 행에서 빼주면 아래와 같은 행렬을 얻을 수 있다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align}$$

• 최종적으로 얻은 행렬을 다시 처음 방정식에 맞춰서 정리하면 다음과 같다.
  • pivot variable : u, w
  • free variable : v, z

$$\begin{align} \begin{bmatrix} 1 & 3 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \end{align}$$

• 위의 방정식을 풀어 써서 row form으로 바꿔 보면 아래와 같다. 또한 pivot variable을 free variable의 형태로 표현하면 행렬의 Null space를 구할 수 있다. 또한 pivot variable의 개수가 해당 행렬의 Null space의 차원이다. 예시의 행렬은 $Dim(N(A))=2$이다.

$$u + 3v -z =0 \\ w+z = 0$$ $$u = =3v + z \\ w = -z$$ $$\begin{align} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = \begin{bmatrix} -3v+z \\ v \\ -z \\ z \end{bmatrix} \end{align}$$

• 위와 같이 방정식을 모두 풀지 않아도 그 전 Row Reduced form 행렬에서 Null space를 구할 수 있다.
  • Row Reduced form에서 free variable들의 column에 계수들을 pivot variable인 경우에는 부호를 바꿔주고 자기 자신의 순서인 자리에는 1을 나머지 free variable 자리에는 0을 넣어주면 된다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 0 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{align}$$

• 자세하게 설명하자면 pivot variable을 free variable의 형태로 표현하는 것이므로 먼저 free variable의 column인 두 번째 열과 네 번째 열만 가져와 위의 방법 처럼 진행하면 아래와 같은 두 free variable 벡터의 조합을 구할 수 있으며 이 조합이 Null space이다.

$$\begin{align} v \begin{bmatrix} -3 \\ 1 \\ 0 \\ 0 \end{bmatrix} + z \begin{bmatrix} 1 \\ 0 \\ -1 \\ 1 \end{bmatrix} \in N(A) \end{align}$$

• 만약 위의 예시 문제가 $Ax=b$를 푸는 문제라고 가정해보자.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 \\ 2 & 6 & 9 & 7 \\ -1 & -3 & 3 & 4 \end{bmatrix} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = \begin{bmatrix} b_{1} \\ b_{2} \\ b_{3} \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 | b_{1} \\ 0 & 0 & 3 & 3 | b_{2} - 2b_{1} \\ 0 & 0 & 6 & 6 | b_{3}+b_{1} \end{bmatrix} \end{align}$$

• 행렬 A의 column vector들의 linear combination이 $b$이어야 하므로 해가 존재한다면 $b \in C(A)$일 것이다. 그런데 여기서는 그 $b$라는 벡터가 $5b_{1} - 2b_{2} + b_{3}=0$임을 만족해야 해가 존재한다. 그 이유는 아래 행렬을 살펴보면 마지막 행은 미지수들과 곱을 해도 0이 되기 때문이다.

$$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 | b_{1} \\ 0 & 0 & 3 & 3 | b_{2} - 2b_{1} \\ 0 & 0 & 0 & 0 | 5b_{1} - 2b_{2} + b_{3} \end{bmatrix} \end{align}$$

• $5b_{1} - 2b_{2} + b_{3}=0$를 만족하는 벡터 $b$는 해를 찾을 수 있으므로 조건을 만족시키는 조합만 찾는다면 해를 구할 수 있다. 그러므로 해는 무한하다. 아래의 예시에서는 벡터 $b$를 다음과 같이 정의 할 것이다.

$$\begin{align} \begin{bmatrix} 1 \\ 5 \\ 5 \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 | 1 \\ 0 & 0 & 3 & 3 | 3 \\ 0 & 0 & 0 & 0 | 0 \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 & 3 & 3 & 2 | 1 \\ 0 & 0 & 1 & 1 | 1 \\ 0 & 0 & 0 & 0 | 0 \end{bmatrix} \end{align}$$ $$\begin{align} \begin{bmatrix} 1 & 3 & 0 & -1 | -2 \\ 0 & 0 & 1 & 1 | 1 \\ 0 & 0 & 0 & 0 | 0 \end{bmatrix} \end{align}$$

$ X = Null space + particular solution$으로 이루어져있음을 확인 할 수 있다. 원래 원점을 지나는 평면인 Null space이었는데 particular solution만큼 평생이동된 평면이 해 집합이 되었다는 것으로 해석 할 수 있다.

$$\begin{align} \begin{bmatrix} u \\ v \\ w \\ z \end{bmatrix} = v \begin{bmatrix} -3 \\ 1 \\ 0 \\ 0 \end{bmatrix} + z \begin{bmatrix} 1 \\ 0 \\ -1 \\ 1 \end{bmatrix} + \begin{bmatrix} -2 \\ 0 \\ 1 \\ 0 \end{bmatrix} \in N(A) \end{align}$$

• 행렬의 곱을 이제는 linear combination의 관점으로 계산하는 방법에 대해 살펴보자. 아래 그림에서 보듯이 행렬을 column vector로 나누어 linear combination으로 행렬의 곱을 볼 수 있다.

• 아래와 같이 column vector말고 row vector를 사용한 곱의 방법을 사용할 수도 있다. 위의 경우와의 차이는 왼쪽의 행렬에 관한 관점으로 바라볼때는 column vector들의 linear combination 오른쪽의 행렬의 관점으로 곱을 계산할 경우는 row vector들의 linear combination으로 계산 할 수 있다.

• 위의 개념들을 생각하여 외적을 계산할 수 있다. 아래 그림에서와 같이 두 행렬의 외적을 2부분으로 나누어 계산하면 손쉽게 계산할 수 있다.