[선형대수학] Linear Equations in Linear Algebra

Linear Algebra and Its Applications by David C. Lay, Steven R. Lay, Judi Mcdonald

 

인공지능 분야와 양자 컴퓨팅 분야에서도 선형대수학은 필수이다.

 

 

1.1 Systems of Linear Equations

책에서는 matrix를 linear system(연립 일차 방정식)을 간단히 나타낸 직사각형 모양의 array로 정의한다.

즉, 

$$x_1-2x_2+x=0$$

$$2x_2-8x_3=8$$

$$5x_1-5x_3=10$$

같은 linear system은

 

coefficient matrix:

$$\[\begin{bmatrix}1 & -2 & 1 \\ 0 & 2 & -8 \\ 5 & 0 & -5 \end{bmatrix}\]$$

 

또는 augmented matrix:

$$\[\begin{bmatrix}1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &  10 \end{bmatrix}\]$$

로 나타내질 수 있다

 

 

Row equivalence

• 만약 elementary row operation으로 하나의 row가 다른 row와 같아질 수 있다면 두 row는 row equivalent하다 라고 정의한다.
  • Elementary row operation은 연립 일차 방정식에서 solution set을 변경시키지 않는 operation들을 뜻한다
  • 이런 row operation들은 reversible 하다

 

 

1.2 Row Reduction and Echelon Forms

Reduced echelon form은 다음과 같다.

$$\[\begin{bmatrix}1 & 0 & 0 & 4 \\0 & 1 & 0 & -3 \\0 & 0 & 1 & 5 \\0 & 0 & 0 & 0\end{bmatrix}\]$$

• 각 row의 첫번째 숫자는 1이고
• 각 row의 leading 1은 그 column의 유일한 0이 아닌 숫자이다.

 

Theorem 1

• Each matrix is row equivalent to one and only one reduced echelon matrix

즉 어떤 matrix에 어떤 순서로 row reduction을 진행해도 같은 reduced echelon matrix가 만들어지게 된다.

이는 우리가 흔히 알고 있는 일차 연립 방적식의 특성과 같다.

 

 

Pivot position

• Reduced echelon form에서 1의 위치를 뜻한다
• Pivot column은 pivot position이 위치한 column을 뜻한다

 

이런 reduced echelon form과 pivot position은 linear system의 solution을 이해하는데 큰 도움을 준다.

 

Basic variable

• Pivot column에 위치한 변수들

Free variable

• Pivot column에 위치하지 않은 변수들
• 말 그대로 그 어떤 제약 조건도 존재하지 않는 변수

예시로 augmented matrix는

$$\[\begin{bmatrix}1 & 0 & -5 & 1 \\0 & 1 & 1 & 4 \\0 & 0 & 0 & 0 \end{bmatrix}\]$$

• $x_1=1+5x_3$
• $x_2=4-x_3$
• $x_3$ - free variable

위 예제처럼 free variable $x_3$은 linear system의 서로 다른 solution을 결정하게 된다.

 

 

Theorem 2

• Linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column
  • If and only if an echelon form of the augmented matrix has no row of the form [0 ... 0 b] with b nonzero
• If linear system is consistent, the solution set is either
  • unique solution (no free variable)
  • infinitely many solutions (at least one free variable)

[0 ... 0 b] 형식의 augmented matrix는 0 = b 형식을 가진다. 이때 b가 0이 아니라면 linear system은 해를 가지지 않는다.

만약 해를 가지고 free variable이 없다면 unique solution을, free variable이 있다면 infinitely many solution을 가지게 된다.

 

 

1.3 Vector Equations

Vector의 다양한 operation이 설명된다.

 

Linear combination

• $\mathbf{y} = a_1\mathbf{v}_1 + a_2\mathbf{v}_2 + \dots + a_n\mathbf{v}_n$
  • $v_1, v_2, ...$: vectors
  • $a_1, a_2, ...$: coefficients
  • Vector y는 vector $v_1, v_2, ...$들의 linear combination이고 정의된다

즉 주어진 vector들에 어떠한 scalar를 곱한 값들의 합으로 만들수 있는 모든 vector는 주어진 vector들의 linear combination이다.

 

Vector equation

• $x_1\mathbf{v}_1 + x_2\mathbf{v}_2 + \dots + x_n\mathbf{v}_n = \mathbf{b}$
• 는 다음과 같은 augmented matrix를 가지는 linear system과 같은 solution set을 가진다.
• $\[\begin{bmatrix}v_1 & v_2 & ... & v_n & b \end{bmatrix}\]$

 

또한 matrix에 대응하는 linear system의 해가 존재 해야만 b는 $a_1, a_2, ...$들의 linear combination으로 생성될 수 있다.

 

 

Span

• If $\mathbf{v}_1, ...,  \mathbf{v}_p$ are in $R^n$, then the set of all linear combinations of $\mathbf{v}_1, ..., \mathbf{v}_p$ is denoted by Span $\{\mathbf{v}_1, ..., \mathbf{v}_p\}$ and is called the subset of $R^n$ spanned by $\mathbf{v}_1, ..., \mathbf{v}_p$. 

즉 크기가 n인 vector들 {$\mathbf{v}_1, ..., \mathbf{v}_p$}의 모든 가능한 linear combination은 Span {$\mathbf{v}_1, ..., \mathbf{v}_p$}로 정의된다.

 

따라서 vector $\mathbf{b}$가 Span{$\mathbf{v}_1, ..., \mathbf{v}_p$}안에 있는지 묻는 것은

$$x_1\mathbf{v}_1 + x_2\mathbf{v}_2 + \dots + x_n\mathbf{v}_n = \mathbf{b}$$

가 해가 있는지 묻는 것과 같다.

 

기하학적으로는 다음과 같은 의미를 가진다.

 

 

1.4 The Matrix Equation Ax=b

m x n matrix A가 column $\mathbf{a}_1, ..., \mathbf{a}_n$을 가지고 있을 때 A와 x ($x \in R^n$)의 곱은 Ax로 나타내진다.

Ax는 A의 각 column들을 x의 가중치로 가지는 linear combination이다.

$$Ax = \left[,\mathbf{a}_1\quad\mathbf{a}_2\quad\cdots\quad\mathbf{a}_n,\right]\begin{bmatrix}x_1\\\vdots\\x_n\end{bmatrix}=x_1\mathbf{a}_1+x_2\mathbf{a}_2+\cdots+x_n\mathbf{a}_n$$

 

 

이제까지 나온 정의들을 합치면 다음과 같은 theorem을 얻을 수 있다.

Theorem 4

• m x n matrix A에 대해 다음 명제들은 모두 동치이다
  • $R^m$에 있는 각 b에 대하여 Ax=b의 해가 존재한다
  • $R^m$에 있는 각 b는 A의 column들의 linear combination이다
  • A의 column들은 $R^m$을 span 한다
  • A는 각 row에 pivot position이 존재한다

 

첫번째 3개의 명제는 span과 linear combination의 정의를 이용해 쉽게 이해할 수 있다.

마지막 명제의 경우 augmented matrix [A b]를 생각해보자. U를 A의 echelon form이라 생각했을 때 [A b]는 reduce되어 [U d]로 나타내질 수 있다.

이때 d를 마지막 값이 1인 아무 vector라 가정한다. 즉, [U d]는 해가 존재하지 않는 linear system을 나타낸다. 따라서 [A b] 또한 inconsistent하다고 증명할 수 있다.

 

 

1.5 Solution Sets of Linear Systems

Terms

• Homogenous equation: Ax = 0 형식으로 나타내질 수 있는 linear system
• Trivial solution: 위 homogenous equation의 해 중 x = 0인 해
• Nontrivial solution: 위 homogenous equation의 해 중 x = 0이 아닌 해

 

Homogenous equation Ax = 0 has a nontrivial solution if and only if the equation has at least one free variable.

Free variable이 존재한다면 free variable에 의해 다른 solution을 가지게 되기 때문이다.

 

 

Theorem 6

Ax = b가 어떤 b에 대해서 consistent 하고 p가 그 solution이라 가정한다. 그렇다면 Ax = b의 solution set은 w = p + $\mathbf{v}_h$를 만족한다. 이때 $\mathbf{v}_h$는 homogenous euqation Ax = 0의 어떤 solution이다.

 

즉 Ax = b의 해가 존재한다면 그 solution set은 Ax = 0의 solution set을 어떤 하나의 해인 p만큼 translate 시켜 얻을 수 있다.

 

 

1.6 Linear Independence

Linear independence

• Indexed set of vectors {$\mathbf{v}_1, ..., \mathbf{v}_p$}가 vector equation $x_1\mathbf{v}_1 + x_2\mathbf{v}_2 + \dots + x_p\mathbf{v}_p = \mathbf{0}$에 대해 단 하나의 trivial solution만을 가진다면 vector들은 linear independent하다

Linear dependence

• Indexed set of vectors {$\mathbf{v}_1, ..., \mathbf{v}_p$}가 vector equation $x_1\mathbf{v}_1 + x_2\mathbf{v}_2 + \dots + x_p\mathbf{v}_p = \mathbf{0}$에 대해 trivial solution이 아닌 다른 해를 가진다면 vector들은 linear dependent 하다

 

Set of indexed vector들을 column vector들로 나타내면 다음과 같이 해석 가능하다.

• Matrix A의 column들은 linearly indepedent 하다
  <= if and only if =>
  Ax = 0이 오직 trivial solution만을 가진다

 

Theorem 7

두개 이상의 vector로 구성된 indexed set S = {$\mathbf{v}_1, ..., \mathbf{v}_p$}이 linearly dependent 하다

<= if and only if =>
S 안에 있는 적어도 하나의 vector가 다른 vector들의 linear combination이다.

 

위 theorem은 span과 연관지어 생각할 수 있다.

한 vector v가 다른 vector들의 linear combination이라는 말은 다른 vector들이 span하는 공간에 v가 존재함을 의미한다.

반대로 vector v가 linearly independent하다는 말은 다른 vector들이 span하는 공간에 v가 존재하지 않음을 의미한다.

위 그림을 보면 이해하기 쉽다.

 

Theorem 8

하나의 set이 각 vector의 entry보다 더 많은 vector를 가지고 있다면 그 set은 linearly dependent 하다.

즉, set {$\mathbf{v}_1, ..., \mathbf{v}_p$} $\in R^n$은 p > n인 경우 linearly dependent 하다.

 

증명:

$A = \left[\mathbf{v}_1 \quad \cdots \quad \mathbf{v}_p\right]$라고 정의해보자. A는 n x p 모양을 가지고 Ax = 0은 n개의 식과 p개의 미지수를 가진다. 만약 p > n이라면 식보다 더 많은 미지수가 존재하기 때문에 반드시 free variable이 생기게 된다. 따라서 Ax = 0이 nontrivial solution을 가지게 되고 linear dependence 정의에 의해 A의 column들은 linearly dependent하다.

 

Theorem 9

Set {$\mathbf{v}_1, ..., \mathbf{v}_p$} $\in R^n$이 zero vector를 포함한다면 그 set은 linearly dependent하다.

 

Zero vector column에 의해 nontrivial solution을 가지게 되기 때문이다.

 

 

1.8 Introduction to Linear Transformation

이제까지 matrix를 linear system의 표현으로 이해했다면 이제 matrix를 vector를 transformation 시키는 하나의 object로 이해해보자.

예를 들어 

$$\begin{bmatrix}4 & -3 & 1 & 3 \\ 2 & 0 & 5 & 1\end{bmatrix}\begin{bmatrix}1 \\ 1 \\1 \\ 1\end{bmatrix}=\begin{bmatrix}5 \\8\end{bmatrix}$$

의 경우 matrix A를 통해 x를 b로 transform했다고 이해할 수 있다.

 

조금 더 일반화해 $R^n$에서 $R^m$로의 transformation T란 $R^n$에 있는 vector x를 $R^m$에 있는 vector T(x)로 배정하는 규칙이라 말할 수 있다.

 

이때 $R^n$은 domain, $R^m$은 codomain으로 정의한다.

하나의 점 T(x)는 하나의 x값에 대한 image라 정의되고 이런 image들의 모든 집합을 range라 정의한다.

 

 

Linear Transformation

• Transformation T는 linear 하기 위해 다음 두 조건을 만족해야 한다:
  • T(u + v) = T(u) + T(v) for all u, v in the domain of T
  • T(cu) = cT(u) for all scalars c and all u in the domain of T

모든 matrix transformation은 linear 하다!

 

또한 만약 T가 linear transformation이라면 다음 두 식이 성립한다.

• T(0) = 0
• T(cu + dv) = cT(u) + dT(v)

 

 

1.9 The Matrix of a Linear Transformation

Theorem 10

• T: $R^n -> R^m$을 하나의 linear transformation으로 정의하자. 그렇다면 다음을 만족하는 유일한 matrix A가 존재한다:
  T(x) = Ax for all x in $R^n$
• 또한 A는 m x n 크기에 j번째 column이 T($\mathbf{e}_j$)인 matrix이다. $\mathbf{e}_j$는 j번째 entry만 1이고 나머지는 모두 0인 vector를 뜻한다.

흥미롭게도 어떤 linear transformation도 matrix A로 나타내질 수 있고 또 transformation matrix A가 유일하다고 말하고 있다.

증명은 위 linear transformation의 정의를 이용해 보일 수 있다.

 

 

Onto

• T: $R^n -> R^m$에 대해 각 $R^m$에 있는 b 값이 적어도 하나의 $R^n$에 있는 x의 image라면 T는 onto $R^m$이라 정의된다.

 

One-to-one

• T: $R^n -> R^m$에 대해 각 $R^m$에 있는 b 값이 최대 하나의 $R^n$에 있는 x의 image라면 T는 one-to-one $R^m$이라 정의된다.

 

Onto이면서 one-to-one일수도 있고 onto가 아니면서 one-to-one도 아닐 수 있다.

 

 

Theorem 11

• T: $R^n -> R^m$가 linear transformation이라 가정한다.
  T는 one-to-one이다
  <= if and only if =>
  T(x) = 0이 trivial solution을 가진다

역함수의 개념에 대입하면 이해하기 쉽다.

 

증명:

T가 linear 하기 때문에 T(0) = 0이다. T가 one-to-one이라면 T(x) = 0이 최대 하나의 해를 가지고 따라서 trivial solution만이 존재한다.

만약 T가 one-to-one이 아니라면 적어도 두개의 $R^n$에 있는 서로 다른 vector u와 v의 image인 b가 존재한다. 즉, T(u) = b이고 T(v) = b이다. 이때 T가 linear 하기 때문에

$$T(\mathbf{u}-\mathbf{v})=T(\mathbf{u})-T(\mathbf{v})=\mathbf{b}-\mathbf{b}=\mathbf{0}$$

가 성립한다.
u와 v는 서로 다른 vector이기 때문에 u - v는 0이 아니다. 즉, T(x) = b는 하나 이상의 해, nontrivial solution을 가진다.

 

 

Theorem 12

• T: $R^n -> R^m$가 linear transformation이라 가정한다. 또 A가 T의 standard matrix이다 가정한다.
  • T 가 $R^n$을 $R^m$으로 맵핑한다
    <= if and only if =>
    A의 column들이 $R^m$을 span 한다
  • T가 one-to-one이다
    <= if and only if =>
    A의 column들이 linearly independent 하다

 

증명

• A 가 $R^m$을 span 한다 <=> $R^m$에 있는 각 b에 대해 Ax = b (T(x) = b)가 적어도 하나의 solution을 가진다 <=> T 가 $R^n$을 $R^m$으로 맵핑한다
• T 가 one-to-one이다 <=> Ax = 0이 trivial solution만을 가진다 <=> A의 column들이 linearly independent 하다

 

 

 

 

 

Chapter 1에서는 먼저 matrix를 linear system의 관점으로 소개한다. 이 linear system 관점에서 solution과 linear combination, span, linear independence를 설명한다. 그 후 matrix를 linear transformation 관점으로 다시 소개한다. 그리고 linear transformation을 linear independence와 span에 연결시키며 마무리한다.