Linear Algebra - 1.2 Row Reduction and Echelon Forms

용어 정리

• A nonzero row or column (0이 아닌 행과 열)
• A leading entry of row (행의 선행 성분)
• Echelon form (사다리꼴)
• Reduced echelon form (기약 사다리꼴)
• Uniqueness of the Reduced Echelon Form (기약 사다리꼴의 유일성)
• Row reduction algorithm (행 줄임 알고리즘)
• Solution of linear systems (소거법)
• general solution (일반 해)
• basic variables (기본 변수)
• free variables (자유 변수)
• Existence and Uniqueness Theorem (유일성과 존재)

A nonzero row or column - 0 이 아닌 행렬

• 매트릭스에서 특정 row와 특정 column을 뽑아서 봤을 때 최소한 하나라도 0이 아니면 -> nonzero row, nonzero column 이라고 부른다.

A leading entry of row - 행의 선행성분

• the leftmost nonzero entry
• 0이 아닌 것 중에 제일 왼쪽에 있는 것이 leading entry에 해당됨

Echelon form - 사다리 꼴

1. All nonzero rows are above any rows of all zeros.

   모든 nonzero rows는 all zeros row 보다 위에 있다.

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

   행의 leading entry는 위에 있는 leading entry보다 오른쪽 열에 있다.

   

• 빨간 점이 leading entry 이다.
• 1 row 의 leading entry 보다 2 row 의 leading entry 가 오른쪽에 있으니 Echelon Form 이 맞다.

Reduced echelon form - 기약 사다리 꼴

• 1강에서 했던 내용임
  1. The leading entry in each nonzero row is 1.

     nonzero 행에 있는 leading entry는 1이다.

  2. Each leading entry is the only nonzero entry in its column.

     leading entry 가 1이어야하고, leading entry column은 leading entry 를 제외하곤 전부 0이되어야한다.

  

• pivot position : leading entry 1의 위치. pivot position은 reduced echelon form이 아니라 echelon form만으로도 확인할 수 있다.

Theorem1. Uniqueness of the Reduced Echelon Form

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

• Theorem1. Uniqueness of the Reduced Echelon Form
• Each matrix is row equivalent to one and only one reduced echelon matrix.
• 각 매트릭스는 Reduced Echelon Form 이 딱 하나 밖에 없다. row reduction을 통해 row equivalent 를 얻을 수 있음

Row reduction algorithm - 행 줄임 알고리즘

Step1. begin with the leftmost nonzero column

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

• pivot position 이 0이 되면 안되므로 interchange를 통해 row 를 바꿔주자.

Step3 row replacement to create zeros in all positions below the pivot

• pivot position을 제외한 pivot column에 있는 나머지들을 전부 0으로 만들어주기

Step4 apply steps 1-3 to the submatrix that remain

• 남은것에 대해 step 1-3 반복 수행

  

• ~ 표시는 row equivalent 하다는 뜻, 즉 row reduction을 통해서 얻을 수 있다.

• The combination of steps 1-4 is called forward phase
• 이 결과물이 -> echelon form! 이다
• 이 echelon form을 reduced echelon form 으로 만드는 것은

Step5 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.

• 맨 오른쪽에 있는 pivot 부터 이번에는 위에 있는 것들을 전부 0으로 만들어준다.

  

  

• Step 5 is called backward phase
• 이렇게 backward phase 까지 진행했으면 reduced echelon form 이 나온거고 이를 통해 솔루션을 얻을 수 있다.

Solution of linear systems - 선형 시스템의 해

• augmented matrix 를 row reduction 알고리즘으로 reduced echelon form을 만들면 선형방정식의 해를 쉽게 구할 수 있다.

• row reduction 으로 구한 reduced echelon form 형태의 augmented matrix

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

• 이를 linear equation 으로 표현해보자.

\[\begin{aligned} x_1 \quad -5x_3 = 1 \\ \quad x_2 + x_3 = 4 \\ \quad \quad 0 = 0 \end{aligned}\]

• 위 linear equation의 해를 구하면 다음과 같다.

\[\begin{cases} x_1 = 1 + 5x_3 \\ x_2 = 4 - x_3 \\ x_3 \; is \; free \end{cases}\]

• 여기서 중요한 것은 general solution (일반 해), basic variable (기본 변수), free variable (자유 변수) 가 무엇인지 확실하게 짚고 넘어가야 한다.

(1) free variable - 자유 변수

\[x_3 \; is \; free\]

• $ x_3 $ 을 free variable 이라고 한다.
• $ x_3 $ 을 어떤 값으로 두어도 0 = 0 을 만족한다.

(2) basic variable - 기본 변수

• basic variable 은 free variable 로 표현한 것을 의미

\[\begin{cases} x_1 = 1 + 5x_3 \\ x_2 = 4 - x_3 \end{cases}\]

(3) general solution - 일반 해

\[\begin{cases} x_1 = 1 + 5x_3 \\ x_2 = 4 - x_3 \\ x_3 \; is \; free \end{cases}\]

• general solution 은 basic variable 과 free variable 로 표현된 해를 의미한다.

• 해가 무한대로 존재한다. 이럴 때는 $x_3$라는 것을 free variable 으로 둔다.
• $x_1, x_2, x_3$ 이 중 어떤것이든 free variable 로 하지 않고 $x_1, x_2$ 같이 leading variables 에 포함되는 변수들을 basic variables로 잡고
• $x_3$를 free variable 로 정하기로 약속.
• 이런식으로 표현된 솔루션을 -> general solution

find the general solution of the following augmented matrix - augmented matrix 에서 general solution 찾기

\[\begin{bmatrix} \phantom{-}1 & \phantom{-}6 & \phantom{-}2 & -5 & -2 & -4 \quad \\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}2 & -8 & -1 & \phantom{-}3 \quad \\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}7 \quad \end{bmatrix}\]

• augmented matrix 를 row reduce

\[\begin{bmatrix} \phantom{-}1 & \phantom{-}6 & \phantom{-}0 & \phantom{-}3 & \phantom{-}0 & \phantom{-}0 \quad \\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & -4 & \phantom{-}0 & \phantom{-}5 \quad \\\ \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}0 & \phantom{-}1 & \phantom{-}7 \quad \end{bmatrix}\]

• backward phase 를 통해 0으로 만들고 row reduction 진행
• 여기서 leading variable에 해당되는것은 $x_1, x_3, x_5$ 이고 free variable은 $x_2, x_4$이다.

\[\begin{aligned} x_1 + 6x_2 \quad +3x_4 \quad = 0 \\ \quad \quad x_3 - 4x_4 = 5 \\ \quad \quad \quad \quad x_5 = 7 \end{aligned}\]

• reduced echelon form 을 linear equation 으로 표현한다.

• general solution 을 다음과 같이 표현할 수 있다.

\[\begin{cases} x_1 = -6x_2 - 3x_4 \\ x_2 \; is \; free \\ x_3 = 5 + 4x_4 \\ x_4 \; is \; free \\ x_5 = 7 \end{cases}\]

• 만약 augmented matrix의 마지막 행이 $ [0 \quad 0 \quad 0 \quad 0 \quad 0 \quad

  \quad b] $ (b ≠ 0) 형태였다면 $ 0 = b $ 라는 모순이 발생하여 inconsistent, 즉 no solution이 된다.

Theorem2. 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 forms.

• \(\begin{bmatrix} 0 & \cdots & 0 & b \end{bmatrix} \quad\) 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.

• 이를 정리하자면 다음과 같다.
• linear equation 이 consistent 하면 augmented matrix에서 b가 pivot position이 아니다.
• 즉, b를 제외하고 0인 행렬이 있으면 안된다.

• 반대로, 0 & \cdots & 0 & b 인 row 가 있으면 -> no solution 이다.

• linear system 이 consistent 하면, (i) free variable 이 없다면 exactly one solution (unique solution) 이다.
• (ii) 1개 이상의 free variable 이 있다면 infinitely many solutions 이다.
• 즉, 해가 1개 -> free variable 이 존재하지 않고 해가 무수히 많다면 -> at least one free variable 이 존재한다.

예제 더 풀어보기

• a. 는 $ x_3 $ 가 free variable 이므로 consistent, many solutions 이다.
• b. 는 첫번째 column 이 전부 0 이므로 $ x_1 $ 이 free variable 이 되므로 consistent, many solutions 이다.