Row echelon form

선형 대수(linear algebra)에서, 행렬(matrix)은 만약 그것이 가우스 소거법(Gaussian elimination)의 결과로부터 모양을 가지면, 사다리꼴 형식(echelon form)에 있습니다.

행렬이 행 사다리꼴 형식(row echelon form)에 있다는 것은 가우스 소거법이 행에 동작했음을 의미하고, 열 사다리꼴(column echelon form)에 있다는 것은 가우스 소거법이 열에 동작했음을 의미합니다. 다른 말로, 행렬은 만약 그것의 전치(transpose)가 행 사다리꼴 형식에 있으면 열 사다리꼴 형식에 있습니다. 그러므로, 이 기사의 나머지 부분에서는 오직 행 사다리꼴 형식만 고려됩니다. 행 사다리꼴 형식의 유사한 속성은 모든 행렬을 전치함으로써 쉽게 추론됩니다.

구체적으로, 행렬이 다음이면 행 사다리꼴 형식에 있습니다:

오직 영으로 구성되는 모든 행은 바닥에 있습니다.^[1]
모든 각 비-영 행의 선행 엔트리 (즉, 가장-왼쪽 비-영 엔트리)는 위의 모든 각 행의 선행 엔트리의 오른쪽에 있습니다.^[2]

일부 텍스트는 선행 계수가 1이어야 한다는 조건을 추가하고,^[3] 반면에 다른 텍스트는 이것을 감소된(reduced) 행 사다리꼴 형식으로 여깁니다.

이들 두 조건은 선행 계수 아래의 열에 있는 모든 엔트리가 영임을 의미합니다.^[4]

다음은 행 사다리꼴 형식의 4x5 행렬의 예제이며, 감소된(reduced) 행 사다리꼴 형식은 아닙니다 (아래를 참조하십시오):

\left[{\begin{array}{ccccc}1&a_{0}&a_{1}&a_{2}&a_{3}\\0&0&2&a_{4}&a_{5}\\0&0&0&1&a_{6}\\0&0&0&0&0\end{array}}\right]

행렬의 많은 속성은 랭크(rank)와 kernel(커널)과 같은 그것들의 행 사다리꼴 형식으로부터 쉽게 추론될 수 있습니다.

Reduced row echelon form

행렬은 만약 그것이 다음 조건을 만족시키면 감소된 행 사다리꼴 형식(reduced row echelon form, 역시 행 정식의 형식(row canonical form)이라고 불림)에 있습니다:^[5]

그것은 행 사다리꼴 형식에 있습니다.
각 비-영 행에서 선행 엔트리는 1입니다 (선행 1이라고 불립니다).
선행 1을 포함하는 각 열은 모든 그것의 다른 엔트리에서 영을 가집니다.

행렬의 감소된 행 사다리꼴 형식은 가우스-조단 소거법(Gauss–Jordan elimination)에 의해 계산될 수 있습니다. 행 사다리꼴 형식과 달리, 행렬의 감소된 행 사다리꼴 형식은 고유하고 그것을 계산하기 위해 사용되는 알고리듬에 의존하지 않습니다.^[6] 주어진 행렬에 대해, 행 사다리꼴 형식이 고유하지 않더라도, 모든 행 사다리꼴 형식과 감소된 행 사다리꼴 형식은 같은 숫자의 영 행을 가지고 피벗은 같은 인덱스에 위치됩니다.^[6]

이것은 행렬의 왼쪽 부분이 항상 항등 행렬(identity matrix)은 아님을 보여주는 감소된 행 사다리꼴 형식에서 행렬의 예제입니다:

\left[{\begin{array}{ccccc}1&0&a_{1}&0&b_{1}\\0&1&a_{2}&0&b_{2}\\0&0&0&1&b_{3}\end{array}}\right]

정수(integer) 계수를 갖는 행렬에 대해, 에르미트 정규 형식(Hermite normal form)은 유클리드 나눗셈(Euclidean division)을 사용하고 임의의 유리수(rational number) 또는 분모를 도입 없이 계산될 수 있는 행 사다리꼴 형식입니다. 다른 한편으로, 정수 계수를 갖는 행렬의 감소된 사다리꼴 형식은 일반적으로 비-정수 계수를 포함합니다.

Transformation to row echelon form

가우스 소거법(Gaussian eliminatio)이라고 불리는, 기본 행 연산(elementary row operations)의 유한 순서-열을 수단으로, 임의의 행렬은 행 사다리꼴 형식으로 변환될 수 있습니다. 기본 행 연산은 행렬의 행 공간(row space)을 보존하기 때문에, 행 사다리꼴 형식의 행 공간은 원래 행렬의 행 공간과 같습니다.

결과 사다리꼴 형식은 고유하지 않습니다; 사다리꼴 형식에 있는 임의의 행렬은 위의 행 중 하나에 행의 스칼라 배수를 더함으로써 (동등한) 사다리꼴 형식으로 넣을 수 있습니다. 예를 들어:

{\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}\xrightarrow {\text{add row 2 to row 1}} {\begin{bmatrix}1&4&6\\0&1&7\\\end{bmatrix}}.

어쨌든, 모든 각 행렬은 고유한 감소된 행 사다리꼴 형식을 가집니다. 위의 예제에서, 감소된 행 사다리꼴 형식은 다음과 같이 찾을 수 있습니다:

{\begin{bmatrix}1&3&-1\\0&1&7\\\end{bmatrix}}\xrightarrow {{\text{subtract 3}}\times {\text{(row 2) from row 1}}} {\begin{bmatrix}1&0&-22\\0&1&7\\\end{bmatrix}}.

이것은 감소된 행 사다리꼴의 비-영 행이 원래 행렬의 행 공간에 대해 고유한 감소된 행 사다리꼴 생성하는 집합임을 의미합니다.

Systems of linear equations

선형 방정식의 시스템은 만약 그것의 증가된 행렬(augmented matrix)이 행 사다리꼴 형식에 있으면, 행 사다리꼴 형식(row echelon form)이라고 말합니다. 유사하게, 선형 방정식의 시스템은 만약 그것의 증가된 행렬이 감소된 행 사다리꼴 형식에 있으면 감소된 행 사다리꼴 형식(reduced row echelon form) 또는 정식의 형식(canonical form)이라고 말합니다.

정식의 형식은 선형 시스템의 명시적 해로 볼 수 있습니다. 사실, 그 시스템이 불일치(inconsistent)인 것과 정식의 형식의 방정식 중 하나가 0 = 1로 감소되는 것은 필요충분 조건입니다.^[7] 그렇지 않으면, 선행 방정식을 제외한 방정식의 모든 항을 오른쪽 편에서 다시 그룹화하여, 피벗에 해당하는 변수를, 어떤 것이라도 있다면, 다른 변수의 상수 또는 선형 함수로 표현합니다.

Pseudocode for reduced row echelon form

다음 유사-코드(pseudocode)는 행렬을 감소된 행 사다리꼴 형식으로 변환합니다:

function ToReducedRowEchelonForm(Matrix M) is
    lead := 0
    rowCount := the number of rows in M
    columnCount := the number of columns in M
    for 0 ≤ r < rowCount do
        if columnCount ≤ lead then
            stop function
        end if
        i = r
        while M[i, lead] = 0 do
            i = i + 1
            if rowCount = i then
                i = r
                lead = lead + 1
                if columnCount = lead then
                    stop function
                end if
            end if
        end while
        if i ≠ r then Swap rows i and r
        Divide row r by M[r, lead]
        for 0 ≤ j < rowCount do
            if j ≠ r do
                Subtract M[j, lead] multiplied by row r from row j
            end if
        end for
        lead = lead + 1
    end for
end function

다음 유사-코드는 행렬을 행 사다리꼴 형식 (감소된 형식 아님)으로 변환합니다:

function ToRowEchelonForm(Matrix M) is
    nr := number of rows in M
    nc := number of columns in M
    
    for 0 ≤ r < nr do
        allZeros := true
        for 0 ≤ c < nc do
            if M[r, c] != 0 then
                allZeros := false
                exit for
            end if
        end for
        if allZeros = true then
            In M, swap row r with row nr
            nr := nr - 1
        end if
    end for
    
    p := 0
    while p < nr and p < nc do
        label nextPivot:
            r := 1
            while M[p, p] = 0 do 
                if (p + r) <= nr then
                    p := p + 1
                    goto nextPivot
                end if
                In M, swap row p with row (p + r)
                r := r + 1
            end while
            for 1 ≤ r < (nr - p) do 
                if M[p + r, p] != 0 then
                    x := -M[p + r, p] / M[p, p]
                    for p ≤ c < nc do
                        M[p + r, c] := M[p , c] * x + M[p + r, c]
                    end for
                end if
            end for
            p := p + 1
    end while
end function

Notes

^ Phrased in terms of each individual zero row in Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries."
^ Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (ii) If row $k$ does not consist entirely of zeros, the number of leading zero entries in row $k+1$ is greater than the number of leading zero entries in row $k$ ."
^ See, for instance, the first clause of the definition of row echelon form in Leon (2010, p. 13): "A matrix is said to be in row echelon form (i) If the first nonzero entry in each nonzero row is 1."
^ Meyer 2000, p. 44
^ Meyer 2000, p. 48
^ ^a ^b Anton, Howard; Rorres, Chris (2013-10-23). Elementary Linear Algebra: Applications Version, 11th Edition. Wiley Global Education. p. 21. ISBN 9781118879160.
^ Cheney, Ward; Kincaid, David R. (2010-12-29). Linear Algebra: Theory and Applications. Jones & Bartlett Publishers. pp. 47–50. ISBN 9781449613525.

References

Leon, Steven J. (2010), Lynch, Deirdre; Hoffman, William; Celano, Caroline (eds.), Linear Algebra with Applications (8th ed.), Pearson, ISBN 978-0-13-600929-0, A matrix is said to be in row echelon form (i) If the first nonzero entry in each nonzero row is 1. (ii) If row $k$ does not consist entirely of zeros, the number of leading zero entries in row $k+1$ is greater than the number of leading zero entries in row $k$ . (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries..
Meyer, Carl D. (2000), Matrix Analysis and Applied Linear Algebra, SIAM, ISBN 978-0-89871-454-8.

External links

Interactive Row Echelon Form with rational output

[1] Phrased in terms of each individual zero row in Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries."

[2] Leon (2010, p. 13):"A matrix is said to be in row echelon form ... (ii) If row $k$ does not consist entirely of zeros, the number of leading zero entries in row $k+1$ is greater than the number of leading zero entries in row $k$ ."

[3] See, for instance, the first clause of the definition of row echelon form in Leon (2010, p. 13): "A matrix is said to be in row echelon form (i) If the first nonzero entry in each nonzero row is 1."

[4] Meyer 2000, p. 44

[5] Meyer 2000, p. 48

[:0-6] Anton, Howard; Rorres, Chris (2013-10-23). Elementary Linear Algebra: Applications Version, 11th Edition. Wiley Global Education. p. 21. ISBN 9781118879160.

[7] Cheney, Ward; Kincaid, David R. (2010-12-29). Linear Algebra: Theory and Applications. Jones & Bartlett Publishers. pp. 47–50. ISBN 9781449613525.

[1]

[2]

[3]

[4]

[5]

[6]

[7]