Row echelon form: Difference between revisions

Revision as of 23:56, 7 November 2023

Latest revision as of 16:21, 17 August 2025

(46 intermediate revisions by 22 users not shown)

Line 1:

{{short description|Possible form of a matrix}}

In [[linear algebra]], a [[Matrix (mathematics)|matrix]] is in '''row echelon form''' if it can be obtained as the result of [[Gaussian elimination]]. Every matrix can be put in row echelon form by applying a sequence of [[elementary row operation]]s. The term ''echelon'' comes from the French ''"échelon"'' ("level" or step of a ladder), and refers to the fact that the nonzero entries of a matrix in row echelon form look like an inverted staircase.{{cn|date=October 2023}}

[[File:Row echelon form.png|thumb|right|Example of a rectangular matrix in row echelon form]]

For [[square matrices]], an [[upper triangular matrix]] with nonzero entries on the diagonal is in row echelon form, and a matrix in row echelon form is (weakly) upper triangular. Thus, the row echelon form can be viewed as a generalization of upper triangular form for rectangular matrices.

A matrix is in '''reduced row echelon form''' if it is in row echelon form, with the additional property that the first nonzero entry of each row is equal to <math>1</math> and is the onesonly abovenonzero itentry withinof the sameits column equal <math>0</math>. The reduced row echelon form of a matrix is unique and does not depend on the sequence of elementary row operations used to obtain it. The variantspecific type of [[Gaussian elimination]] that transforms a matrix to reduced row echelon form is sometimes called [[Gauss–Jordan elimination]].

A matrix is in '''column echelon form''' if its [[transpose]] is in row echelon form. So,Since all properties of column echelon forms can betherefore easilyimmediately be deduced from the corresponding properties of row echelon forms. Therefore, ''only row echelon forms are considered in the remainder of the article.''

==(General) rowRow echelon form==

{{anchor|rref}}

A matrix is in '''row echelon form''' if

* All rows having only zero entries are at the bottom.<ref>Phrased in terms of each individual zero row in {{harvtxt|Leon|2010|p=13}}:"A matrix is said to be in <strong>row echelon form</strong> ... (iii) If there are rows whose entries are all zero, they are below the rows having nonzero entries."</ref>

* The [[leading entry]] (that is, the leftleftmost non-most nonzerozero entry) of every nonzeronon-zero row, called the '''pivot''', is onto the right of the leading entry of every row above.<ref>{{harvtxt|Leon|2010|p=13}}:"A matrix is said to be in <strong>row echelon form</strong> ... (ii) If row {{mvar|k}} does not consist entirely of zeros, the number of leading zero entries in row <math>k + 1</math> is greater than the number of leading zero entries in row {{mvar|k}}."</ref>

Some texts add the condition that the leading coefficient must be 1<ref>See, for instance, the first clause of the definition of row echelon form in {{harvtxt|Leon|2010|p=13}}: "A matrix is said to be in <strong>row echelon form</strong> (i) If the first nonzero entry in each nonzero row is 1."</ref> while others require this only in [[#Reduced row echelon form|reduced row echelon form]].

These two conditions imply that all entries in a column below a leading coefficient are zeros.<ref>{{harvnb|Meyer|2000|p=44}}</ref>

The following is an example of a <math>4\times 5</math> matrix in row echelon form, but not in reduced row echelon form (see below):

: <math>

\left[ \begin{array}{ccccc}

Line 37:

* Each column containing a leading {{math|1}} has zeros in all its other entries.

ForIf athe matrixfirst intwo rowconditions echelonare formverified, the last condition is equivalent to:

* Each column containing a leading {{math|1}} has zeros in all entries above the leading {{math|1}}.

While a matrix may have several echelon forms, its reduced echelon form is unique.

Given a matrix in reduced row echelon form, if one permutes the columns in order to have the leading {{math|1}} of the {{mvar|i}}th row in the {{mvar|i}}th column, one gets a matrix of the form

Line 46:

I & X\\ 0&0

\end{pmatrix},</math>

where {{mvar|I}} is anthe [[identity matrix]] of dimension <math>j</math> equal to the rank of the entire matrix, {{mvar|X}} is a matrix with the same number of<math>j</math> rows asand {{<math|I}}>n-j</math> columns, and the two {{math|0}}'s are [[zero matrix|zero matrices]] of appropriate size. However, sinceSince a permutation of columns is not a row operation, the resulting matrix is inequivalent under elementary row operations. In the Gaussian elimination method, this corresponds to a permutation of the unknowns in the original linear system that allows a linear parametrization of the row space, in which the first <math>j</math> coefficients are unconstrained, and the remaining <math>n-j</math> are determined as linear combinations of these.

== Systems of linear equations ==

Line 52:

A [[system of linear equations]] is said to be in ''row echelon form'' if its [[augmented matrix]] is in row echelon form. Similarly, a system of linear equations is said to be in ''reduced row echelon form'' or in ''canonical form'' if its augmented matrix is in reduced row echelon form.

The canonical form may be viewed as an explicit solution of the linear system. In fact, the system is [[System of linear equations#Consistency|inconsistent]] if and only if one of the equations of the canonical form is reduced to 0 = 1; that is if there is a leading {{mvar|1}} in the column of the constant terms.<ref>{{Cite book|url=https://books.google.com/books?id=S0imN2tl1qwC|title=Linear Algebra: Theory and Applications|lastlast1=Cheney|firstfirst1=Ward|last2=Kincaid|first2=David R.|date=2010-12-29|publisher=Jones & Bartlett Publishers|isbn=9781449613525|pages=47–50|language=en}}</ref> Otherwise, regrouping in the right hand side all the terms of the equations but the leading ones, expresses the variables corresponding to the pivots as constants or linear functions of the other variables, if any.

== Transformation to row echelon form ==

{{main|Gaussian elimination}}

Gaussian elimination is the main algorithm for transforming every matrix into a matrix in row echelon form. A variant, sometimes called [[Gauss–Jordan elimination]] produces a reduced row echelon form. Both consist of a finite sequence of [[elementary row operation]]s; the number of required elementary row operations is at most {{mvar|mn}} for an {{mvar|m}}-by-{{mvar|n}} matrix.<ref name=":0">{{Cite book|url=https://books.google.com/books?id=loRbAgAAQBAJ|title=Elementary Linear Algebra: Applications Version, 11th Edition|lastlast1=Anton|firstfirst1=Howard|last2=Rorres|first2=Chris|date=2013-10-23|publisher=Wiley Global Education |isbn=9781118879160|page=21|language=en}}</ref>

For a given matrix, despite the row echelon form not being unique, all row echelon forms, including the reduced row echelon form, have the same number of zero rows and the pivots are located in the same positions.<ref name=":0" />

Line 68:

\end{array} \right]</math>

For a matrix with [[integer]] coefficients, the [[Hermite normal form]] is a row echelon form that can be calculated without introducing any denominator, by using [[Euclidean division]] or [[Bézout's identity]]. The reduced echelon form of a matrix with integer coefficientsentries generally contains non-integer coefficientsentries, because of the need ofto dividingdivide by its leading coefficient each row of arow the echelon form.

The non-uniqueness of the row echelon form of a matrix follows from the fact that some elementary row operations transform a matrix in row echelon form into another ([[row equivalence|equivalent]]) matrix that is also in row echelon form. These elementary row operations include the multiplication of a row by a nonzero scalar and the addition of a scalar multiple of a row to one of the rows above rowsit. For example:

: <math> \begin{bmatrix} 1 & 3 & -1 \\ 0 & 1 & 7 \\ \end{bmatrix}

\xrightarrow{\text{add row 2 to row 1}}

Line 81:

== Affine spaces of reduced echelon forms ==

In this section and the following one, weNow denote the ___location of the columns containing the leading entries of the successive rows of a <math>k\times n</math> matrix <math>A</math> in reduced row echelon form (the pivots) as <math>(L_1, \dots, L_j)</math>, with

:<math> 0< L_1 \cdots < L_j \le n, </math>

where <math>j \le k</math> is the dimension of the [[row space]] of the matrix. The data <math>(k, n, L_1, \ldots, L_j)</math> will be called the ''shape'' of <math>A</math>, which has leading non-zero entries

Line 91:

\end{align}.</math>

Since all other entries are arbitrary elements of the base field <math>K</math>, the set <math>A(k, n, L_1, \ldots, L_j)</math> of all reduced echelon form matrices with shape <math>(k, n, L_1, \ldots, L_j)</math> is a {{mvar|K}}-affine space of dimension<ref name="Fu">{{cite book | last=Fulton | first= William | title= Young Tableaux. With Applications to Representation Theory and Geometry, Chapt. 9.4 | year=1997 | series =London Mathematical Society Student Texts | volume = 35 |publisher=Cambridge University Press | ___location = Cambridge, U.K.| isbn= 9780521567244 | doi=10.1017/CBO9780511626241 }} </ref><ref name="KL">{{cite journal | last1=Kleiman | first1=S.L.| last2=Laksov | first2=Dan |title= Schubert Calculus | publisher=American Mathematical Society|journal = American Mathematical Monthly | volume=79| issue=10 | year=1972 | issn=0377-9017 | doi=10.1080/00029890.1972.11993188 | pages=1061-10821061–1082 }}</ref>

:<math>\text{dim}(A(k,n, L_1, \dots, L_j))=nj -\frac{1}{2}j(j-1)- \sum_{i=1}^j L_i.</math>

Line 101:

= nj - \frac{1}{2}j(j-1)- \sum_{i=1}^j L_i. </math>

== Maximal rank: Schubert cells ==

The row echelon form can be used to give a concrete description of the [[Schubert cell]]s associated with the [[Grassmannian]] of <math>k</math>-dimensional subspaces of a [[vector space]].

If <math>j=k \le n</math>, the matrices <math>A </math> in<math> A(k, n, L_1, \dots, L_k)</math> are of maximal rank <math>k</math>, and determine <math>k</math>-dimensional subspaces <math>w \subset V</math> of the free <math>K</math>-module <math> V:=K^n</math>, as the span

:: <math> w= \text{span}\{W_1, \dots, W_k\} </math>

of linear combinations

:: <math>W_i := \sum_{l=1}^k A_{il} e_l, \quad i=1, \dots , k </math>

of the elementary basis vectors <math>(e_1, \dots, e_n)</math>,

with coefficients equal to the row vectors. In this case, the affine space <math>A(k, n, L_1, \dots, L_k)</math> is the [[Schubert calculus|Schubert cell]]<ref name="Fu"/><ref name="KL"/>

<math>X_\lambda(\mathcal{V})</math> of the [[Grassmannian]] <math> \mathbf{Gr}_k(V)</math>, consisting of <math>k</math>-dimensional subspaces of <math>V</math> corresponding to the [[integer partition]]

:<math>\lambda = (\lambda_1 \ge \cdots \ge \lambda_k \ge 0) </math>

with parts equal to

:<math>\lambda_i := n-k - L_i +i, \quad 1\le j \le k, </math>

relative to the [[flag manifold |complete flag]]

:<math> \mathcal{V}= (V_1 \subset V_2 \cdots \subset V_n = V),</math>

where

:<math> V_i = \text{span}\{e_1, \dots, e_i\}, \quad i =1, \dots n. </math>

This means that <math>X_\lambda(\mathcal{V}) \subset \mathbf{Gr}_k(V) </math> consists of those <math>k</math>-dimensional subspaces <math>w \subset V</math> whose intersections with the subspaces <math>\{V_j\}_{j=1, \dots, n}</math> have dimensions

::<math> \text{dim}(w \cap V_{j}) = i, \ \text{for } n-k -\lambda_i +i \le j\le n-k -\lambda_{i+1} +i, \quad i=1, \dots , k. </math>

Its dimension is then equal to the weight <math> |\lambda| = \sum_{i=1}^k \lambda_i </math> of the partition<ref name="Fu"/>

:<math>\dim({X_\lambda(\mathcal{V})}) = |\lambda|. </math>

An equivalent, simpler characterization of the Schubert cell <math>X_\lambda(\mathcal{V})</math> may be given in terms of the [[flag manifold | dual complete flag]]

:<math> \tilde{\mathcal{V}}= (\tilde{V}_1 \subset \tilde{V}_2 \cdots \subset \tilde{V}_n = V),</math>

where

:<math> \tilde{V}_i = \text{span}\{e_n, \dots, e_{n-i+1}\}, \quad i =1, \dots n. </math>

Then <math>X_\lambda(\mathcal{V}) \subset \mathbf{Gr}_k(V) </math> consists of those <math>k</math>-dimensional subspaces <math>w \subset V</math> that have a basis <math>(\tilde{W}_1, \dots, \tilde{W}_k)</math>

consisting of elements

:: <math>\tilde{W}_i \in \tilde{V}_{n- L_i +1}=\tilde{V}_{k+\lambda_i -i +1 }, \quad i=1, \dots, k </math>

of the subspaces <math>\{\tilde{V}_{k+\lambda_i -i +1}\}_{i=1, \dots, k} </math> (which, relative to the standard basis, are the row vectors <math>(W_k, \dots, W_1)</math> of the row echelon form, written in reverse order.)

==Notes==

Line 151 ⟶ 111:

| title = Linear Algebra with Applications

| isbn=978-0-13-600929-0

| edition = 8th8

| year = 2010

| publisher = Pearson

Line 166 ⟶ 126:

{{wikibooks|Linear Algebra|Row Reduction and Echelon Forms}}

*[httphttps://people.revoledu.com/kardi/tutorial/LinearAlgebra/RREF.html Interactive Row Echelon Form withTutorial] rationalby output]Kardi Teknomo, PhD

{{Matrix classes}}

[[Category:Numerical linear algebra]]

[[Category:ArticlesMatrix withnormal example pseudocodeforms]]

[[de:Lineares Gleichungssystem#Stufenform, Treppenform]]