[선형대수학 개론] 1.2 Row Reduction and Echelon Forms

 

이 포스팅은 인프런 강의 - 선형대수학 개론(조범희)을 듣고 개인 공부를 위해 정리하는 글로, 잘못된 내용이 있을 수 있으니 이 점 참고 부탁 드립니다.

선형대수학개론 - 인프런 | 강의

 

2023.02.03 - [수학/선형대수학] - [선형대수학 개론] 1.1 Systems of Linear Equations 에서는 선형시스템의 정의에 대해서 알아 봤다면, 이번 포스팅에서는 선형시스템의 해를 찾기 위해 알아야할 기본정의에 대해 살펴 보겠습니다.

[선형대수학 개론] 1.1 Systems of Linear Equations

그럼 포스팅 시작!

 

목차

 

Nonzero Row or Column

0 이 아닌 원소가 최소한 하나 있는 행 또는 열

• A nonzero row/column in a matrix means a row/column that contains at least one nonzero entry

Leading Entry of Row

Leading Entry of Row

• 행에서 가장 왼쪽에 있는 0이 아닌 원소
  • A leading entry of a row refers to the leftmost nonzero entry

Row Echelon Form and Reduced Row Echelon Form

Row Echelon Form

Row Echelon Form (Leading entry:■, Any value including zero : * )

다음 3가지 조건을 만족하면 행사다리꼴 행렬(Row Echelon Form) 이라 정의한다.

1번 조건

1. 모든 nonzero row는 원소가 모두 0인 행들보다 위에 있다. (원소가 모두 0인 행렬이 없다면 항상 만족)

• All nonzero rows are above any rows of all zeros

 

2번 조건

2. 각 leading entry 는 자기 자신보다 위에 있는 leading entry의 오른쪽 열에 위치 한다.

• Each leading entry of row is in a column to the right of the leading entry of the row above it

 

3번 조건

3. Leading entry 아래에 있는(열 기준) 행렬의 모든 원소는 0이다. (2번 조건을 만족하면 항상 만족)

• All entries in matrix below a leading entry are zeros

 

Reduced Echelon Form

만약 row echelon form이 다음 두 가지 조건을 만족한다면, 기약 행사다리꼴 행렬(Reduced Row Echelon Form) 이라 정의한다.

4번 조건

4. 각 nonzero row의 leading entry 가 1이다.

• The leading entry in each nonzero row is 1

 

5번 조건

5. 원소가 1인 각각의 leading entry는 해당 컬럼에서 오직 하나이다.

• Each leading 1 is the only nonzero entry in its column

 

Pivot Postion and Pivot Column

Pivot Position and Pivot Column

Pivot position : The location of a leading entry in the echelon form of a maxtrix
Pivot column : A column that contains a pivot position

[Theorem 1] Uniqueness of The Reduced Echelon Form ★★★

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

• 행렬은 reduced echelon form이 유일하게 하나밖에 나올 수 없음을 의미

 

Row Reduction of Algorithm

Row reduction of algorithm 은 다음 5가지 단계로 진행되는데, 1~4단계는 echelon form을 만드는 과정으로 forward phase 라 하고, 5단계는 reduced echelon form을 만드는 과정으로 backward phase 라고 한다.

1단계

1. 가장 왼쪽의 nonzero column에서 시작한다. 이는 pivot column 이며 최상단이 the first pivot position 이다. 이때, nonzero entry (pivot)가 최상단에 있어야 한다.

• Begin with the leftmost nonzero column. This is a pivot column and the top of the leftmost nonzero column is the first pivot position. A nonzero entry, or pivot must be placed in this position

해당 행렬은 pivot이 0이므로 다른행과 교환해야 한다.

2단계

 

2. Pivot column에서 pivot으로 nonzero entry를 선택한다. 만약, 필요하다면 다른 행과 교환한다.

• Select a nonzero entry in the pivot column as a pivot. If necessary, interchange rows to move this entry into the pivot position

 

3단계

3. Replacement 연산을 이용해서 pivot 아래의 원소들을 모두 0 으로 만든다.

• Use row replacement operations to create zeros in all positions below the pivot

4단계

4. 1~3 단계를 서브행렬에 반복 적용한다.

• Apply steps 1–3 to the submatrix that remains. Repeat the process until there are no more nonzero rows to modify

 

5단계

5. 가장 오른쪽에 있는 pivot을 1로 만들고, 각 pivot 위를 다 0으로 만든다. 만약 pivot이 1이 아니라면 scaling 연산을 적용한다.

• Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, make it 1 by a scaling operation

 

Solution of Linear Systems

Solution of Linear System

선형시스템의 해를 구하기 위해서 다음 3가지 정의를 알고 있어야 한다.

General solution :The set of all possible solutions of linear systems

Free variable : Non-pivot variable like $x_3$

Basic variable : Variable that corresponds to a pivot column like $x_1,x_2$

Ex ) Find the general solution of the following augmented matrix

 

Sol)

[Theorem 2] Existence and Uniqueness Theorem ★★★

A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column - that is, if and only if an echelon form of the augmented matrix has no row of the form $\begin
{bmatrix}
\begin{array}{cc}
0&\cdots&0&b
\end{array}
\end{bmatrix}$ with $b$ is nonzero.

If a linear system is consistent, then the solution set contains either (i) a unique solution, when there are no free variables, or (ii) infinitely many solutions, when there is at least one free variable.

의미를 살펴보면, 다음과 같다.
(1) 선형 시스템이 consistent 하다는 것과 augmented matrix에서 가장 오른쪽에 있는 컬럼의 $b$가 pivot position이 아니라는 것과 동치이다.

• 즉, augmented matrix 의 echelon form에서 $b$가 0이 아닌 행이 없어야 한다는 것과 동치이다.

 

(2) 만약 선형 시스템이 consistent하면,

1. Free variable 이 없다면 해가 1개이다. (exactly one solution)
2. Free variable 이 1개 이상이라면 해는 무수히 많다.(infinitely many solution)

 

---

 

이번 포스팅에서는 선형시스템의 해를 찾기 위해 알아야할 기본정의들을 알아봤다.

이번에 나온 개념들은 앞으로 배울 내용을 이해하기 위해 꼭 필요한 부분이기 때문에 많이 익숙해지면 좋을 것 같다.

다음 포스팅은 벡터의 정의 및 연산, 그리고 너무나도 중요한 개념인 span에 관한 내용이다.

 

- 오늘보다 나은 블로거가 될 수 있기를 바라며 -