1.2 Row Reduction and Echelon form

A nonzero row or column

* nonzero row, column는 특정 row나 column에 0이 아닌 값이 적어도 하나 존재할 경우를 뜻한다.

 

A leading entry of row

* leading entry는 column의 가장 왼 쪽에 있는 nonzero인 element를 뜻한다.

* 위 augmented matrix에서 leading entry는 1, 4, 5가 된다.

 

Echelon Form

* Echelon Form matrix(사다리꼴 행렬)의 조건은 다음 2가지이다.

1) nonzero row들은 all zeros 위에 존재한다.

2) nonzero row들의 배열은 다음과 같다 : leading entry의 위치는 바로 위 row의 leading entry보다 오른쪽에 위치한다(동등한 위치도 안된다). 즉, 각 leading entry를 기준으로 column 기준 아래의 값들은 모두 0이어야 한다.

 

* echelon form의 경우 leading entry에는 어떤 값이 와도 상관 없다.

 

Reduced Echelon Form

* reduced echelon form의 조건은 echelon form의 조건에 다음 2가지가 추가된다.

1. 모든 nonzero row의 leading entry는 1이다. 

2. 1의 값을 가지는 각 leading entry는 entry가 속한 column의 유일한 nonzero값이다.

 

* 1의 값을 가지는 leading entry를 pivot position이라고 한다.

Therom1. Uniqueness of the Reduced Echelon Form
- row reduction을 통해 도출된 echelon form은 유일하다. 다른 echelon form은 존재할 수 없다.

 

Row Reduction Algorithm

* Row reduction을 통해 echelon form을 만드는 방법은 forward phase, backward phase가 존재한다.

 

1) Forward Phase

* 위와 같은 augmented matrix가 주어졌다고 해보자.

* 첫 번째 row의 첫 번째 entry가 0인 반면 4번째 row의 첫 번째 entry는 3이다. 위치를 바꿔서(Interchange) pivot column의 nonzero entry가 pivot이 되도록 한다.

* pivot이 속한 column의 pivot아래 값들을 모두 0으로 만들어준다.

* 이러한 과정을 반복하면 위와 같은 echelon form이 생성된다.

2) Backward Phase

* pivot position에 있는 값들을 모두 1로 만들고 pivot을 column의 유일한 nonzero entry가 되도록 조정한다. 이를 통해 reduced echelon form을 생성한다.

 

 

Solution of linear systems(no solution case, infinitely many solutions)

* General solution : linear system이 무수히 많은 해를 가질 때 이를 free variable과 basic variable로 표현한 것.

 

* 위와 같은 linear system이 있다고 해보자(row reduction을 거쳐 reduced echelon form으로 변환된 linear system이다). 변수의 개수보다 equation의 개수가 적기 때문에 무수히 많은 해가 존재하게 된다.

* general solution을 표현하는 방법은 다음과 같다. 

1) pivot position에 있는 변수들을 basic variable로 설정한다.

2) pivot poistion에 있지 않은 변수들을 free variable로 설정한다.

3) basic variable들을 free variable로 표현한다.

 

Theorem 2. Existence and Uniqueness Theorem
- linear system이 consistent하다면, row reduction을 통해 echelon form을 도출했을 때 0=x와 같은 형태의 row가 존재하지 않는다.
- 또한 linear system이 consistent하다면 solution set은 다음 두 가지 경우이다. 
1) Unique solution : free variable이 없다.
2) Infinitely many solutions : 최소 1개의 free variable이 있다.

 

 

정리

Leading Entry
* column 제일 좌측 nonzero인 element

Echelon form 조건
1) all zero는 무조건 nonzero 밑에
2) 각 row의 leading entry 밑의 원소는 모두 zero
3) 각 row의 leading entry 위치는 바로 위 row의 leading entry보다 더 오른쪽(동등위치 x)

Reduced Echelon form 조건
* 각 row의 leading entry = 1
* leading entry기준 해당 column의 다른 원소는 모두 zero

Row Reduction Algorithm
1) Forward phase
* Echelon form 만들기
2) Backward phase
* Reduced Echelon form 만들기

Echelon form
* echelon form이 존재하고 0=x 꼴의 equation이 존재하지 않으면 해가 1개 이상 존재한다. 즉 consistent하다.
* Echelon form은 unique하지 않다.

Reduced Echelon form
* Reduced Echelon form은 unique하다.

Solution of linear systems
* infinitely many solution일 경우 general solution으로 표현
* general solution은 free variable, basic variable로 표현
* free variable = pivot에 위치하지 않은 변수
* basic variable = pivot에 위치한 변수

Free variable in consistent linear system
* linear system이 consistent할 때 
* infinitely many solutions

No Free variable in inconsistent linear system
* linear system이 consistent할 때 
* solution이 unique하다.