2. Linear Algebra (2)

2.3 Solving Systems of Linear Equations

2.3.1 Particular and General Solution

이와 같은 선형식 시스템이 존재한다고 하였을 때, 우리는 4개의 미지수와 2개의 식이 주어지게 된다

=> 일반적으로 무한히 많은 해를 가질 것으로 예상됨

 

우리는 미지수 x1, x2, x3, x4 에 대한 스칼라 값을 찾고 싶은 것이고 

다음과 같이 각 행렬의 열 성분과 미지수들의 곱으로 나타낼 수 있게 된다.

위 식의 우변에 나온 열 성분 중 가장 간단한 열 2개는 첫 번째 열과 두 번째 열이다

위 방정식의 해 중 하나는 첫 번째 열을 42배하고 (x1 = 42) , 두 번째 열을 8배 (x2 = 8) 하고 나머지 변수를 0으로 두는 것이다

따라서 여러개의 해답 중 하나의 해답은 [42, 8, 0, 0]⊤ 이 된다

이러한 해답을 우리는 특수해 (particular solution, special solution) 이라고 함

 

그러나 이 답이 선형방정식 시스템의 유일한 해는 아니며, 다른 모든 해를 찾기 위해서는 행렬의 열을 이용하여 non-trivial한 방식으로 생성하는 창의적인 접근이 필요

즉, 특수해만으로 전체 해 공간을 설명할 수 없기 때문에 행렬의 나머지 열을 이용해 추가적인 해를 찾아야 함

=> 사용하지 않았던 2개의 열을, 해를 구하는데 사용한 2개의 열을 활용해 표현

=> 먼저 세 번째 열을 살펴볼 것임

 

갈색으로 표시된 첫 번째와 두 번째 열을 활용하여,

초록색으로 표시된 세 번째 열을 표현해보는 것이다

이와 같이 구한 해를 일반해 (general solution) 이라고 함

아래의 단계를 거쳐서 일반적으로 선형식 시스템의 해를 찾을 수 있다고 정의할 수 있다

(1) Ax = b 선형식의 특수 해를 하나 찾아낸다

(2) Ax = 0 의 모든 해를 찾아낸다

(3) 위의 두 단계의 해를 결합하려 일반해를 찾아낸다

 

여기서 중요한 점은, 특정 해도 일반 해도 1개만 존재하지 않는다는 것이다

즉, 조합을 어떻게 하고 접근을 어떻게 하느냐에 따라 해는 무수히 많이 그 수가 증가한다

 

이 예제에서 다룬 선형 방정식 시스템은 행렬이 편리한 형태를 가지고 있기 때문에 특정해와 일반 해를 쉽게 구할 수 있었다

그러나 모든 일반적인 선형 방정식 시스템이 이러한 편리한 형태를 가지는 것은 아님

가우스 소거법 (Gaussian elimination)이라는 알고리즘적인 방법이 존재

가우스 소거법의 핵심은 기본행 연산 (elementary transformation) !

 

 

2.3.2 Elementary Transformation

elementary transformation의 핵심 => 정답셋을 변화시키지 않는 선에서 선형 방정식 시스템을 간단한 형태로 변환시키는 것

3가지 기본행 연산

(1) 두 행을 교환(행렬에서 행은 방정식을 나타냄)

(2) 행을 스칼라 배

(3) 서로 다른 두 행을 더하기

 

이 기본행 연산을 거쳐서 row-echelon form (행사다리꼴)로 바꾸면 특이해와 일반해를 쉽게 구할 수 있다

 

해당 식을 예제로 살펴보면, 기본행 연산을 거쳐 row-echelon form으로 바꾸어 특이해와 일반해를 쉽게 구할 수 있다

위 선형식 시스템을 첨가행렬 (augmented matrix) 로 변환한 뒤 첫 번째 행과 세 번째 행을 교환한다

교환한 행렬의 첫 번째 행을 활용하여,

첫 번째 행의 첫 번째 요소 아래를 다 0으로 만든다 (R1을 활용하여)

이 과정을 반복하면 이와 같은 row-echelon 형태 (행사다리꼴 형태) 가 완성된다 

row-echelon form (REF) 은 굉장히 편리한 식인데,

augmented matrix를 위와 같은 선형식 시스템으로 바로 변환할 수 있기 때문이다

 

💡 pivot 각 '행'의 첫 번째 요소를 pivot이라고 한다

 

그리고 이 pivot이 존재하는 '열' 을 pivot column 이라고 부르게 되는데, 여기서
=> pivot column에 해당하는 x는 basic variable이라고 부르고,
=> 그 외 column에 해당하는 x는 free variable이라고 부른다

 

그리고 이를 응용하면, 특이하는 Ax = b 를 만족하는 x이며, free variable에 0 값을 대입하면 쉽게 구할 수 있게 된다.

즉, 위 예시 식에서 x2 와 x4에 0을 대입하여 x1, x3, x5 를 구하는데, 이를 특이해라고 할 수 있다

위 예시의 경우 [x1, x2, x3, x4, x5] = [2, 0, -1, 1, 0] 이 특이해가 된다

 

이제 일반해를 구해야 하는데, Ax = 0 를 만족하는 x를 구한 다음 특이해와 더하면 일반해를 구할 수 있음

 

💡 Row Echelon Form 행 사다리꼴 형태 (Row Echelon Form, REF) 이기 위해서는 다음의 조건을 만족해야 한다 =>모든 원소가 0인 행은 행렬의 맨 아래에 위치해야 한다 => 각 행의 첫 번째 0이 아닌 숫자, 즉 pivot은 바로 윗 행의 pivot 보다 오른쪽에 위치해야 한다

즉, REF는 행렬을 계단처럼 정렬한 형태를 가지고 있어야 한다

REF가 되기 위한 조건을 요약하면 아래와 같다

1. 0이 아닌 원소를 갖는 행에서 맨 처음 나오는 0이 아닌 수는 1이어야 한다. 이러한 1을 선도 1(leading one)이라고 한다.

2. 모든 원소가 0인 행은 행렬의 맨 아래로 내려가야 한다.

3. 0이 아닌 원소를 갖는 연속된 두 행은 해당 행의 leading 1이 윗 행의 leading 1보다 오른쪽에 있어야 한다.

 

 

(+) 추가

💡 Reduced Row Echelon From 기약 행 사다리꼴 형태 (Reduced Row Echelon From, RREF)  => 행렬의 pivot이 있는 열을 제외한 나머지 열 (non-pivot col) 을 피벗 열의 선형 결합으로 나타낼 수 있도록 변형한 행렬 => 특정한 규칙을 만족하는 행렬 형태, 행 연산을 통해 변형이 가능하다

 

즉 RREF가 되려면 위의 REF가 되기 위한 조건에 아래의 조건이 하나 더 만족해야 한다

4. leading 1이 있는 열의 나머지 원소들은 모두 0이어야 한다.

예시는 다음과 같다

 

 

 

2.3.3 The Minus -1 Trick

위 행렬은 기본행 연산으로 만들어진 RREF 형태의 행렬이다

위 행렬에 행을 추가하여 정방행렬의 형태 (n*n) 로 만들어줄 건데, 여기서 중요한 점은 non-pivot column에 -1을 추가하는 것이다

변형된 행렬의 최종적인 form은 다음과 같다

이와 같은 행렬은, 이제 -1을 포함하는 열이 Ax = 0의 해가 된다

A 행렬의 pivot 열은 Ax = b 의 해 공간의 basis 기저를 형성한다

A 행렬의 -1 pivot 열은 Ax = 0 해 공간의 기저를 형성한다

이것을 kernel  또는 null space 라고 한다

 

 

 

2.3.4 Algorithms for solving a System of Linear Equation

특정한 경우에는 역행렬 A^-1 을 구해서 방정식 Ax=b 의 해를 x=A^−1 * b 로 표현 => 이는 A가 가역행렬이고 정방행렬일 때만 가능

따라서 조금 완화된 조건의 무어-펜로즈 의사역행렬 (Moore-Penrose pseudo inverse) 를 활용해 해를 구할 수 있음

이를 활용하여 최소제곱의 해를 구할 수 있다

 

 

 

2.4 Vector Spaces

현재까지 선형방정식 시스템과 이를 푸는 방법에 대해 살펴보았고, 이를 행렬로 간단히 표현할 수 있다는 것을 확인했다

이제부턴 벡터가 존재하는 구조적인 공간인 vector space 에 대해 자세히 살펴볼 것이다

 

우리는 벡터를  덧셈 연산, 스칼라배 연산이 가능한 객체라고 비공식적으로 정의하였다

이제부터 살펴볼 group (군) 이라는 개념을 도입하여 공식적으로 정의를 해야할 때가 왔다.

 

2.4.1 Group

💡 Group 군 집합 G 와 연산 ⊗ : G * G -> G 가 주어졌을 때, G:=(G,⊗) 가 group이 되기 위한 조건은 다음과 같다 (1) 닫힘성 Closure (2) 결합법칙 Associativity (3) 항등원 Neural element (4) 역원 Inverse Element

 

즉 group 이란, 특정한 연산이 정의된 원소들의 집합으로, 이 연산이 집합의 구조를 일정하게 유지하도록 하는 성질을 가진다

에잇 나도 잘 모르겠음

그냥 특정 연산이 성립되는 원소들의 집합으로 이해하고 넘어가면 될 것 같음

 

 

2.4.2 Vector Spaces

💡 Vector Space 벡터 공간 벡터 공간이란 두 벡터의 덧셈과 스칼라곱을 성립하는 벡터들의 집합 벡터 공간의 요소들을 벡터이다

 

동일한 벡터 공간 내에 있는 두 벡터는

=> 벡터 덧셈, 벡터 스칼라곱, 분배법칙, 결합법칙이 성립한다

이 네 가지 조건이 만족될 때, 두 연산에 대해 정의된 벡터라고 이야기한다.

 

그리고 이 집합에 속한 원소 x를 가리켜서 벡터(vector) 라고 한다

 

특히 벡터 덧셈에 대해 [0, 0,...,0] 으로 되어있는 벡터를 영벡터 (zero vector) 이라고 하고 

벡터에 곱하는 실수를 스칼라 (scalar) 라고 하며

스칼라와 벡터의 곱셈을 스칼라곱 (multiplication by scalar) 이라고 하며 이는 내적과 조금 다른 개념이다

 

참고로 벡터 간 곱셈은 정의되지 않는다

이론적으로 각 원소끼리의 곱을 정의되지 않는다. 이론적으로는 정의되나 수학에서는 행렬의 곱 외에는 따로 사용 X

 

ex) 벡터 공간 예시 - 덧셈 : x+y == (x1​,…,xn​) + (y1​,…,yn​) == (x1​+y1​,…,xn​+yn​), 즉 element wise addition - 스칼라곱 : x+y == (x1​,…,xn​) + (y1​,…,yn​) == (x1​+y1​,…,xn​+yn​) 이는 행렬 공간이 벡터 공간일때도 동일하게 성립한다

 

 

이를 정리하면,

• n차원의 실수 tuple 집합은, element-wise addition & scalar multiplication이 성립하는 vector space를 형성한다
• n*m 차원의 행렬에서도 마찬가지로, element-wise addition & scalar multiplication이 성립하는 vector space를 형성한다
• 복소수도 마찬가지로 덧셈과 실수배로 형성

 

** 추가 설명

행벡터 1*n 과 열벡터 n*1은 명확하게 다르게 취급되어야 하는 것이 맞다

기본적으로 벡터는 열벡터로 표기하며,

행벡터는 전치 연산을 사용하여 나타낸다

=> 이러한 표기법을 활용하면 행렬 연산과 내적 연산이 명확해지고

=> 선형변환에서 벡터의 역할을 쉽게 이해할 수 있다

 

 

2.4.3 Vector Subspaces

직관적으로 이 벡터 부분공간도 원래의 벡터 공간에 포함이되어있다

그러나 벡터공간에 정의된 연산을 부분공간에 적용시켜도 그 연산의 결과가 부분공간을 벗어나지 않음

ex) 정수 벡터공간에 짝수 부분공간 -> 짝수들의 집합에 덧셈, 스칼라배 연산을 해도 계속 짝수에 머무름

 

이러한 의미에서 벡터 부분공간은 벡터 덧셈 및 스칼라곱 연산에 대해 닫혀있다고 할 수 있다

💡  Vector Subspaces 벡터 부분 공간 하나의 벡터 공간 V가 주어졌을 때, 영집합이 아니고 V 내에 속하는 집합 U가 다음 조건을 만족하면 U는 V의 벡터 부분공간 (vector subspace, linear subspace) 라고 한다 => U가 벡터공간의 연산인 덧셈과 스칼라곱에 대해 닫혀있으며 => 0벡터를 포함해야한다

ex) Vector subspace 예시

위 그림에서 ℝ^2 의 부분공간은 오직 D만 해당한다

• A, C 의 경우 닫힘 성질 (Closure Property) 이 위배되기 때문에 부분공간이 아님
  => 벡터 덧셈과 스칼라곱을 만족해야하는데 영역이 제한되어있기 때문
• B는 0벡터를 포함하지 않으므로 부분공간이 될 수 없다

나아가 Ax = 0을 만족하는 해의 집합은 ℝ^n의 부분집합이 된다

그러나 Ax = b (b != 0) 의 해들은 0벡터를 포함하지 않으므로 부분공간이 되지 않는다

 

여러 부분공간의 교집합은 여전히 부분공간이다

 

 

 

2.5 Linear Independence

해당 챕터에서는 벡터 공간의 원소인 벡터로 할 수 있는 것에 대해 자세히 살펴볼 것이다 => 특히 덧셈연산과 스칼라배

Closure Property 덕분에 위 연산을 수행하면 여전히 같은 벡터 공간 안에 있는 벡터를 얻게 된다

 

또한 우리는 특정한 벡터를 활용하여 벡터공간의 모든 벡터를 표현할 수 있다 => 기저 (basis) 라고 하며 이는 2.6 에서 다룰 것

이 전에 선형 결합 (linear combination) 과 선형 독립성 (Linear Independence) 개념을 먼저 정의할 필요가 있다

 

💡 선형 결합 Linear Combination 벡터들의 조합으로 새로운 벡터를 만드는 것 즉 벡터공간 V와, 유한 개의 벡터 xi ∈V  가 주어졌을 때, 모든 벡터 v∈V는 다음과 같은 형태로 나타낼 수 있다 여기서 λ1​,…,λk​ ∈ R 은 벡터 xi와의 선형결합이라고 설명할 수 있다

 

만약 x1​=(1,0), x2=(0,1) 이라면, 이들의 선형결합으로 2차원 평면의 점을 만들 수 있다

=> (3,4) = 3*(1,0) + 4*(0,1)

=> 즉, 이 벡터들을 조합하여 (선형결합하여) 원하는 위치를 표현할 수 있다

 

특히 0벡터는 항상 다음과 같은 선형 결합으로 표현이 가능하다

 

💡 선형 종속과 독립 Linear (In)dependence 벡터공간 V와, 유한 개의 벡터 xi ∈V  가 주어졌을 때, 만약 비자명한 선형 결합이 존재하여 다음을 만족한다면 여기서 적어도 하나의 계수 λi​ 가 0이 아닌 경우 벡터집합 xi 는 선형 종속 (linearly dependent) n이다 반대로 오직 자명한 해 (즉, λ1=λ2=⋯=λk=0) 만 존재하는 경우, 벡터집합은 선형독립 (linearly independent) 이라고 할 수 있다

 

어떠한 벡터들이 서로 중복된 정보를 포함할 때, 우리는 그 벡터들이 선형 종속 (linearly dependent) 이라고 한다
즉, 특정 벡터가 다른 벡터들의 선형 결합으로 표현될 수 있다면, 그 벡터들은 종속적이다

ex) 벡터 x1=(1,0), x2=(0,1), x3=(2,0) 가 존재한다고 하였을 때, x3은 x1의 스칼라배로 표현이 가능한 정보이다
=> 즉 이 세 벡터 중 하나는 사실 새로운 정보가 아니라 중복된 정보
=> 불필요한 벡터가 포함된 상태

 

반대로 벡터들이 서로 새로운 정보를 제공하고, 어느 하나도 다른 벡터의 조합으로 만들 수 없다면 이를 선형 독립 (linearly independent) 이라고 한다

즉, 모든 벡터가 서로 독립적인 정보를 제공하는 상태

영벡터를 만들기 위해서는 모든 계수가 λk 0이어야 하는 상태

=> 어느 하나도 나머지의 조합으로 만들어질 수 없는 경우 선형 독립이다

위 지도에 나타난 방향 벡터들은 선형 종속적이다

=> '751km West' 라는 정보를 가지는 벡터는 

=> '374km Southwest' + '506km Northwest' 정보의 조합으로 만들어낼 수 있는 정보이기 때문

=> 따라서 세 개의 벡터는 선형 종속이다

 

 

선형 독립성을 판단할 수 있는 기본 성질

• 벡터들은 선형 독립이거나 선형 종속이다 -> 둘 중 하나이며, 다른 선택지는 존재하지 않는다
• 하나이상의 벡터가 0벡터라면, 선형 종속이다
  • x1​=(0,0,0) 이 있다면, 벡터 집합은 반드시 선형 종속
  • 두 개의 벡터가 서로 동일하면, 그것들도 선형 종속
• 벡터집합 {x1​,…,xk​} 이 선형 종속일 조건
  • 일반적으로 한 벡터가 다른 벡터들의 배수로 나타나면 선형종속이고
  • 벡터 중 하나 이상이 다른 벡터들의 선형 조합으로 표현될 수 있으면 선형 종속이다
• 선형독립성은 가우스 소거법을 활용하면 실용적으로 확인이 가능하다
  • 벡터들을 행렬의 열로 표현하고, 가우스 소거법을 사용하여 REF 꼴로 변환해낸다
  • 여기서 pivot 열이 독립적인 벡터를 나타내며
  • non-pivot  열이 하나라도 존재하면 선형 종속이다
   

예를 들어,

위 행렬의 경우 x4열에 pivot이 존재하지 않으므로 linearly depedent

반대로 이 행렬의 경우 모든 열에 pivot이 존재하기 때문에 linearly independent 하다고 할 수 있다