2. Linear Algebra

2. Linear Algebra

선형 대수는 벡터를 다루기 위한 규칙과 벡터에 관한 연구이다. 8장에서는 데이터를 벡터로 표현한다.

벡터

---

• 기하학적 벡터

• 다항식

  

• 음성 신호

• $\mathbb{R}^{n}$에 있는 실수 튜플

Linearity

---

f(x) function, operation satisfies Additivity and Homogeneity

Geometry of Linear Equation

---

• row from: Intersection of lines, planes, hyperplanesSingular Cases: no solution: parallel infinite solutions: line, plane of intersection

• column from: Combination of column vectorsSingular Cases:

  

가우스 소거법

---

• Forward Elimination → Triangular System (Upper Triangular Matrix) → Back-substitution

  

  ref. https://slideplayer.com/slide/5340300/

• Do pivoting when Zero appears in a pivot position. When all pivots are non-zero after G.E then It has unique solution.

LU 분할

---

• Elementary Matrix

  

  

  ref. https://home.iitk.ac.in/~arlal/MTH102/la.pdf

• Triangular Factors and Row Exchanges

  $E_{32}E_{31}E_{21} A = U$

  $A = E_{32}E_{31}E_{21} = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} U = LU$

• LDU 분할

  

• 특징

  det(A) = det(L) * det(U)

  L은 가우스 소거법의 history를 갖고 있다.

  LU분할은 A에 대해 유일하게 결정된다.

  Ax = b를 쉽게 풀게 해준다.

  

  ref. 50/542 https://ia802906.us.archive.org/18/items/StrangG.LinearAlgebraAndItsApplications45881001/[Strang_G.]_Linear_algebra_and_its_applications(4)[5881001].pdf

Inverses and Transposes

---

• 역행렬 특징
  • n개의 피벗이 있다면 역행렬이 존재하며 이는 필요충분조건이다.
  • 역행렬은 유일하다.
  • 행렬 A가 가역행렬이라면, 선형연립방정식의 해는 Ax=b 는 유일하다. $x = A^{-1}b$
  • 동차 선형연립방정식을 만족하는 0벡터가 아닌 해가 있다면, A는 역행렬이 없다. Ax = 0
  • determinant가 0이 아닌 경우, 역행렬은 존재한다
  • Gauss Jordan Method

    ref. https://www.mathsisfun.com/algebra/matrix-inverse-row-operations-gauss-jordan.html

    

• Symmetric Matrix

  $A^{T}= A$

  $L^{T}= U$

  대칭행렬은 가역행렬이다.

Groups (군)

---

군은 컴퓨터 공학에서 중요한 역할을 한다. 집합의 연산에 관해 기초 프레임워크를 제공하며, 암호학, 코딩 이론(coding theory), 그래픽에 주로 사용한다.

아벨군(Abelian Group)은 집합과 연산이 다음 다섯가지를 만족하면 된다.

• 군과 아벨군

  

  

• 일반선형군(General Linear Group)

  정방가역행렬과 행렬곱의 군은 위의 4가지는 만족하지만 교환법칙(commutative)이 성립하지 않는다. 이러한 군을 General Linear Group이라 한다.

  

벡터 공간

---

벡터 공간은 $\mathcal{V}$집합과 덧셈과 스칼라곱으로 이루어져 있다. 덧셈연산과는 아벨군을 이룬다. 스칼라곱은 분배법칙(Distributivity)과 결합법칙(Associativity) 항등원(neutral element)가 있으며, 스칼라와 벡터집합이 아닌 연산하기 때문에 스칼라 곱은 outer operation이라고 한다.

• 벡터공간

  

이러한 $\mathbb{x}\in V$ 벡터공간의 원소를 벡터라고하며, neutral element는 0벡터이다.

벡터곱은 일반적으로 정의 되지 않는다. 이론적으로 요소곱(element-wise multiplication)으로 정의할 수 있다. 하지만, 이러한 곱셈은 프로그래밍 언어에서는 보편적이지만, 수학적인 기존 규칙에 제한적이다. 대신에 행렬곱을 사용해 다음과 같이 정의 할 수 있다.

outer product: $\boldsymbol{ab}^{T} \in \mathbb{R}^{n \times n}$

inner/scalar/dot product: $\boldsymbol{a^{T}b} \in \mathbb{R}$

$\mathcal{V}$를 $\mathbb{R}^{n}$이나 $\mathbb{R}^{m\times n}$으로 놓고 아래와 같이 벡터공간의 연산을 정의할 수 있다.

벡터부분공간(vector subspace, Linear subspace)

---

• 정의

  

$\mathcal{U}\subseteq\mathcal{V}$이고 V가 벡터공간이면, V의 부분공간 U는 V의 성질을 공유한다.

모든 $\boldsymbol{x} \in \mathcal{V}$에 대해, $\boldsymbol{x} \in \mathcal{U} \subseteq\mathcal{V}$이다. U가 V의 부분공간이기 위해 아래임을 보여야한다.

모든 부분공간 U는 동차선형계(homogeneous system of linear equation)의 해공간이다. $\boldsymbol{Ax = 0}$ for $\boldsymbol{x} \in \mathbb{R}^{n}$

• example 2.12

  trivial subspaces, 자명한 부분공간

  비동차 선형계의 해집합은 $R^n$의 부분공간이 아니다.

  

  • 추가 (이상화 교수님 선형대수 2장, strang 선형대수)

    • Space: x and y should be closed under addition and scalar multiplication

      $x, y \in \mathbf{V} , c_{1}x + c_{2}y \in \mathbf{V}$

    • There is a unique "Zero Vector" such that x + 0 = x .

      (원점을 포함하지 않으면 벡터 공간이 될 수 없음

    • Subspace: non empty subset that satisfies the requirements for a vector space. The origin is smallest subspace.

    • 행렬 A의 열벡터 공간 (Column space of A)

      

    • A의 영공간

      Nullspace of Matrix A consists of all vectors x such that Ax=0

    • 행렬 A의 부분공간

      

선형 독립

---

• 추가 (이상화 교수님 선형대수 2장, strang 선형대수)

  • Linear Independence

    선형 결합 식 $c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} = 0$ 에서 모든 $c_{i} = 0$ 일 때만 성립하면 벡터들 끼리 서로 Linearly independent하다고 한다. 벡터들 끼리 dependent 하다는 것은 One vector is a combination of the others 라는 것이다.

    행렬 A에 가우시안 소거법 이후, m 개의 non-zero row가 있다면, m개의독립적인 열벡터가 존재하는 것이다.

  • Spanning All linear combination of vectors $\left\{ v_{1},v_{2}, ..., v_{n} \right\}$

  • Basis (Vectors) number of minimum linearly independent vectors to span the vector space 이 때 linear combination is unique from basis (일대일 대응) 하지만 vector space에서 basis는 unique 하진 않다. 또한 basis vector 들 끼리 Orthogoanl하면 좋다.(Chapter 3) maximal independent set & minimal spanning set.

  • Dimension of a Vector Space number of basis vectors = number of linearly independent vectors infinitely many different bases. degree of freedom

  • Rank of A = # of independent column vectors = # of independent row vectors = # of pivots in Gaussian Elimination of A (independent column vectors 를 찾는 방법) = Dim of $\mathbf{C}(A)$

• 유용한 성질

canonical/standard basis (정준기저, 표준기저)

---

• 기저를 고르는 방법 예시

  

  (x3은 x1과 x2로 만들 수 있음)

rank

---

행렬 A의 선형독립 열 벡터 수

• 성질

  전치행렬과 기존 행렬의 rank는 같다.

  가우시안 소거법 이 후, 피벗열의 수와 같음. 열벡터가 이루는 부분공간을 image, range라고도 함.

  nxn 정방가역행렬이면 rank는 n개임.

  비동차선형계는 rk(A)와 rk(A|b)가 같은 경우에만 풀 수 있음.

  ex. augmented matrix [A|b] 예시

  

  동차선형계의 해공간은 영공간 또는 커널이라고 함.

  mxn 행렬 A의 Rank가 min(m,n)이면 full rank라고 함.

선형 사상(Linear Mapping)

---

• 정의

  

선형사상은 벡터 공간의 성질을 보존하며, 선형사상을 행렬로 표현할 수 있다. 선형사상을 선형변환(linear transfromation), 준동형(vector space homomorphism)이라고도 한다.

• 사상의 종류

  단사(injection): 각 원소의 목적지가 모두 다른 원소인 경우

  전사(surjection): 목적 집합(치역)의 모든 원소에 시작 집합(정의역)과 연결되는 경우

  전단사(bijection, one-to-one correspondence): 단사 + 전사

  

  

  ref) https://www.mathsisfun.com/sets/injective-surjective-bijective.html

  추가로 특별한 선형 사상의 경우 아래와 같이 정의한다.

  

• 정리) 유한차원 벡터공간 V와 W에 isomorphism한 사상은 두 벡터 공간의 차원이 같은 것과 필요충분 조건이다. (55pg, MML)

  두 벡터공간의 차원이 같다면, 손실없이 변환할 수 있다는 것을 의미한다. 또한 mxn 행렬의 공간과 mn의 벡터 공간이 동일하게 다룰 수 있다는 정당성을 제공한다.

  이는 n차원 벡터공간은 R^n에 isomorphic하다는 것이다. 그리고 이를 이용해 좌표계를 정의할 수 있다.

  

변환 행렬(transformation Matrix)

---

두 벡터공간 V(n차원), W(m차원)와 각 공간의 정렬된 기저 B, C와 V→W로 하는 선형사상 파이에 대해 행렬로 다음과 같이 나타낼 수 있다.

기저 변환

---

V → W로 변환행렬을 $A_{\phi}$라고 할 때, 벡터공간 V에서의 기저는 $B, \ \tilde{B}$로 바뀌고, 벡터공간 W에서의 기저는 $C, \ \tilde{C}$로 바뀐다. 이 때, V와 W에서 바뀐 기저에서의 변환행렬 $\tilde{A_{\phi}}$은 다음과 같이 바뀐다.

이 때, S는 $B$에서 $\tilde{B}$로, 기존 기저 $B$로 새로운 기저 $\tilde{B}$를 표현한 변환행렬(nxn), T는 $C$에서 $\tilde{C}$로 변환해주는 행렬(mxm)이다. 이들의 관계는 아래와 같다. (보통 기존 기저는 Identity Matrix 임)

• 예시

  

  변환행렬 A가 Identity Matrix에서 B로 변환된 경우, 새로운 기저에서의 변환행렬은 $B^{-1}AB$ 를 통해 위의 $\tilde{A}$와 같이 더 쉬운 변환행렬로 변환된다. 변환행렬이 nxn일 경우 A와 $\tilde{A}$는 서로 유사행렬(similar Matrix라고 한다.)

  특징으로는 determinant와 trace가 같고, 고유값이 같다.

  ref. https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=gdpresent&logNo=220604263000

  

Equivalent and Similarity (유사행렬)

---

$\tilde{A} = Y^{-1}AS$를 만족하는 가역행렬 S(nxn)와 T(mxm)가 있다면, $A$와 $\tilde{A}$는 equivalent한 관계이다.

Image & Kernel

---

선형사상의 image와 kernel은 중요한 성질을 가지고 있는 벡터부분공간이다.

• kernel / null space (커널/영공간)

  

  0으로 보네는 벡터들의 공간

• image / range (상)

  

  사상의 치역이다. V → W에서 V는 사상의 정의역, W는 사상의 공역이다.

• mxn 선형사상(행렬) A에서

  image는 행렬 의 열공간(column space)이며, $\mathbb{R}^{m}$의 부분공간이다. 행렬 A의 랭크는 상의 차원(열공간의 차원과 같다)

  영공간(커널)은 Ax=0의 일반해이며, $\mathbb{R}^{n}$의 부분공간이다. 커널은 어떤 열벡터의 다른 열벡터의 선형 결합을 나타 낼 수 있는지에 집중한다.

  

Affine Subspace / Linear Manifold(아핀 부분공간, 선형 매니폴드)

---

• 정의

  

L을 V의 아핀부분공간, 선형매니폴드라고 한다. U는 방향공간(direction space), 방향(direction)이라고 하며, $x_{0}$을 support point라고 한다. 12장에서는 이 부분공간을 hyperplane(초평면)으로 부른다. 아핀공간은 0벡터를 포함하지 않아도 되기 때문에, V의 선형벡터 부분공간은 아니다.

아핀 부분공간을 통해 매개변수 방정식(parametric equation)을 표현할 수 있다.

$L=X_0+U$에서, V의 기저벡터를 b1, ..., bk로 놓고, 아핀부분공간의 원소는 아래와 같이 표현할 수 있다.

• example 2.26

  1차원에서의 아핀 부분공간은 선이다. 이를 그림으로 표현하면 아래와 같음.

  

  $\mathbb{R}^n$에서의 n-1 차원의 아핀 부분공간은 초평면이다. 선도 초평면이다.

• 비동차선형연립방정식의 해는 아핀부분공간이며, 이를 이용하면 커널공간은 $x_0=0$벡터인 아핀부분공간으로 볼 수 있다.

• Affine Mappings

  선형사상이 두 선형벡터공간을 변환했던 것과 마찬가지로, 아핀사상도 두 아핀공간의 변환을 나타낸다. 아핀사상과 선형사상은 연관이 깊으며, 많은 성질을 공유한다.

  

  • 성질

    

    ref. http://savanna.korea.ac.kr/wp/?page_id=659

Solving Ax=0 and Ax=b

---

• 86page, Strang

  

  

• Echelon Form U and Row Reduced Form R for Rectangular Matrix

  

  

• Pivot Variables and Free Variables

  

  Matrix 에서 Column이 Row보다 많다면 (n>m), 최소 n-m의 Free Variables가 존재한다. R의 일부 행이 0 으로 없어지면 더 많은 Free Variables 가 존재한다. 결론적으로 # of Unknowns < # of Equation인 Matrix에서는 적어도 하나 이상의 Special Solution이 존재한다.

• solving Ax=b, Ux=c and Rx=d

  

  위 식에서 d를 활용하면 free variable v = y = 0이고 u = -2, w = 1인 점을 지남을 알 수 있으므로 이를 xp로 곧바로 적용해도된다.

• Finding Ax=b

  1) [A:b]→G.E→[R:d]

  2) Find Pivot, Free variables.

  3) Find Special Solution for Null space from R

  4) Find Particular solution from d.