Talk:Row echelon form

Goto??

Looking at the second pseudo code module, what is with the goto statement. My IQ >> 160 (talk) 22:16, 20 December 2010 (UTC)

What's wrong with it? It provides a simple way of simultaneously exiting the while loop and skipping the for loop. Rgrant222 (talk) 05:57, 26 January 2011 (UTC)

Ambiguity in algorithm

the link to pseudocode does not define how "stop" should work. Does it stop the current loop? Does it stop the whole function? Is it like a "return" in C, or like a "break"?

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
        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
                end if
            end if
        end while

Pseudocode algorithm fails

For this matrix:

{{0 0 0 0} {0 -1 2 -5} {1 2 -4 8} {5 0 -3 2}}

The first pseudocode algorithm failed for several matrices for me me as well. I suggest removing the code entirely.

Right, the code is bad. For example there is no clear exit condition for the first while loop if it only sees zeros, unless stop function means something non-obvious. We can't accept stop function anyway since it is not a standard pseudocode component. What about this, does it work? McKay (talk) 23:53, 29 March 2011 (UTC)

McKay - I haven't had a chance to check the Gaussian elimination pseudocode myself, however, I do have a working implementation that I made based upon my the aforementioned erroneous algorithm (which has since been removed from the page). Although it is a C implementation, I suppose that it would suffice as an example if I remove some of the particularly C specific parts of the code. In my opinion, even the current pseudocode for row echelon form looks C-like due to the starting at zero for each of the matrix indices, so I am strongly considering including C based pseudocode if there is any interest from the community. I am still relatively new to the editing guidelines on pseudocode, so please advise. KlappCK (talk) 14:09, 13 May 2011 (UTC)

---

—Preceding unsigned comment added by 190.152.74.4 (talk) 01:00, 3 June 2009 (UTC)

My Precalculus book reports that Row-Echelon form contains the requirement:

"A matrix in row-echelon form has the following properties ... 2. For each row that does not consist entirely of zeros, the first nonzero entry is 1 (Called a leading 1) ..." - PRECALCULUS 7th Edition, Larson & Hostetler

Which is contrary to what is reported in the article.

Which form is correct? Serialized 00:23, 2 December 2006 (UTC)

Apparently, there isn't universal agreement about this. Some books include that requirement and others don't. A book I have also says this, but someone else here has a book that doesn't say it. See Talk:Gaussian elimination#REF and RREF requirements. Eric119 02:52, 2 December 2006 (UTC)

I added a note; I think that the article should mention that there are two slightly differing definitions. -- Jitse Niesen (talk) 13:52, 2 December 2006 (UTC)

This requirement is congruent with what is currently given. KlappCK (talk) 14:10, 13 May 2011 (UTC)

TI-89 Example

Does anyone else think that having the example of "doing" REF on a TI-89 is not appropriate here? There are many different models of calculator and there is no need to single this one out. Such information is more appropriate for the calculator's manual. If we did include it, it would belong in Gaussian elimination, not here. Eric119 05:42, 19 December 2006 (UTC)

I agree. Besides many calculators, there are also numerical libtaries and computer algebra systems. It makes little sense to explain how to find the REF in all these environments. Hence, I removed the section. -- Jitse Niesen (talk) 11:36, 19 December 2006 (UTC)

I imagine that the push for TI-89 implementations is due to prevalence TI-83 and TI-89 in many American mathematics class rooms. Furthermore, TI-8* code looks a lot like pseudocode. That said, I am certainly stating my own opinion here, not that of Wikipedians as whole. Klappck (talk) 17:38, 12 April 2011 (UTC)

Excess requirement

The article read as follows before I edited it (requirements for RREF):

• All nonzero rows are above any rows of all zeroes.
• The leading coefficient of a row is always to the right of the leading coefficient of the row above it.
• All entries below a leading coefficient, if any, are zeroes.

However, this last requirement is redundant. Take the leading coefficient of any non-zero row. The elements directly below this are either:

• In a zero row, in which case the element is zero, or
• In a nonzero row, in which case that row's leading element is to the right and so the element directly below is also zero.

Thus the third requirement of the above is redundant; it results from the first two.

Unless I've screwed up.

Rawling4851 22:31, 20 January 2007 (UTC)

Triangle Matrix

What is the relationship between upper triangular matrices and matrices in row echelon form? For example, is the upper triangular matrix a special case of row echelon form? It would seem that the only requirement for a upper triangular matrix above that of row echelon form is that it be square. Is it accurate to say that all upper triangular matrices are in row echelon form? Jebix 22:01, 29 July 2007 (UTC)

Yes (Michael Kemp)

Leading coefficent

The article on "leading coefficient" is not completely clear : it should be precised that the leading coefficent is only defined for non-zero rows. Striclty speaking, this precision should also appear in your first definition :

• either the matrix is the null matrix
• or the non-zero rows are all above the (eventual) zero rows, and the leading coefficient of a non-zero row which is not the first one is stricly to the right of the leading coefficent of the row above it.

--Zebulon64 (talk) 14:29, 7 March 2008 (UTC)

A separate issue:

In the current version, leading coefficients have to be 1.

This need not be the case (eg see planet math). I realise that some authors (eg Anton) give the definition as currently given in this article. However, by relaxing the condition backwards substitution is still straight forward which is the point of this form anyway. —Preceding unsigned comment added by 137.166.4.130 (talk) 04:25, 4 June 2010 (UTC)

--Michael Kemp

I apologize if this was too much, but I added that some sources require leading coefficients to be 1 for row echelon form. You make a good point, but I still think it is important to note that some sources differ on the definition of row echelon form. I added this, along with a citation. This should hopefully clarify things to a reader who learned differently (or saw differently at another source, such as Wikibooks), and at the least hopefully prevent any edit warring between people only familiar with altering definitions. I apologize also if the way I've presented it isn't perfectly clear or seems a bit awkward, but it's a start. – 98.235.185.74 (talk) 07:34, 18 January 2013 (UTC)

I have reverted your edit for several reasons:

• Your citation is unreliable as unpublished
• It is silly and confusing to begin an item in a definition by "Some authors"
• As reduced form requires the leading coefficients to be 1 it is unnecessary and confusing to introduce a third definition. How the authors requiring leading ones call the form without leading ones?
• The form without leading ones is easier to compute, as not needing any operation on the pivot line. Therefore it is produced by many implemented algorithms. On the other hand, I do not known any published algorithm producing unreduced form with leading 1.

D.Lazard (talk) 09:22, 18 January 2013 (UTC)

I see your point, but this discrepancy has existed since 2006 (see the discussion above). There are more reliable sources verifying this. In the interest of full coverage, I think it should be included and noted. This has been edited in and out of the article for six years now, mostly from good faith edits due to confusion, it seems. I still think it should be noted. I like this way of presenting the definitions: [1] (which also includes another source for my definition). Please reconsider this. There seems to have been an edit war for six years now due to people changing back and forth between the two definitions. This version I think was the most clear, as it provided both definitions, but assumed one for examples in the interest of clarity. However, this version did not stop the edits, as someone edited that version, apparently missing that the "above three conditions" included that leading coefficients must be 1, and this led to more editing back and forth. I think this needs more discussion, and your revert, while in good faith, may have been a bit premature. This issue should be discussed, and a consensus reached, to clearly establish an acceptable way to present the information and prevent further confusion/editing. – 98.235.185.74 (talk) 09:35, 18 January 2013 (UTC)

I would not oppose to add, in footnote or between the definitions of echelon form and reduced echelon form, something like that: "Some texts add the condition that the leading coefficient of each nonzero row is one. This more constrained definition must not be confused with that of the reduced echelon form, which follows." D.Lazard (talk) 12:00, 18 January 2013 (UTC)

That sounds agreeable, though I wonder if also the reduced row echelon form should be restated with all of the conditions, listing (again) the same conditions for row echelon form, to avoid confusion. This, then, would have reduced row echelon form not defined in terms of "In addition to the conditions for row echelon form" or "is in row echelon form and satisfies the additional condition," but rather something like "satisfies these conditions: [nonzero rows first, leading coefficients to right of row above, leading coefficients 1, only nonzero entry in column]" (though, obviously, expanded and properly formatted as a list). Then, an additional statement could be added, such as: "Note that a matrix in reduced row echelon form satisfies all of the criteria for row echelon form, as well as additional conditions" (or some other statement that shows that rref is just row echelon form with additional constraints). The general outline would then be a statement of row echelon form (as it is currently), followed by a statement (outside the actual definition, as you said) which notes the occasional inclusion of the additional condition; then the definition of reduced row echelon form, listing all of the conditions (as opposed to "satisfies the above, plus [...]"); and finally a note on the relationship between the two.

This would make sure to mention both, but avoid the confusion that occurred here as to whether "leading coefficient must be 1" would be considered an additional condition, and still make sure to make the connection between row echelon and reduced row echelon forms clear. – 98.235.185.74 (talk) 13:15, 18 January 2013 (UTC)

It looks good. Are you willing to implement it? On the other hand, the article needs a complete rewriting to follow the manual of style (the lead is too long and too technical). Moreover the article is very incomplete, almost a stub: no mention of other algorithms than Gauss and Gauss-Jordan to compute it; until today, no link to Hermite normal form; no mention of Bareiss algorithm, which, over the integers, uses only exact divisions to produce a integer row echelon form in which the product of the first kth leading coefficient is the determinant of the submatrix of the original matrix whose diagonal is the places of the kth first pivots.D.Lazard (talk) 13:53, 18 January 2013 (UTC)

I can implement the changes discussed for the definitions, and probably tidy up the lead, but I'm not sure how much else I can contribute to expand the article. I can look for sources and try to at least get some new topics started, but I can't guarantee much. I'll start with the definitions, first.

This begs another question, though. The example for row echelon form, should it remain as is (with leading ones), or be altered to have other leading coefficients? That is, should the example adhere to the more constrained, or less constrained definition of row echelon form? Is it fine as is, or does having the leading coefficients as 1 and following values arbitrary lead to potential confusion if the article prefers the less constrained definition? Should there be an example for both? (In this case, the definition would be followed by a new example with arbitrary leading coefficients; then this example followed by the mention of the possible additional condition, and this followed by the current example with leading coefficients as 1s). – 98.235.185.74 (talk) 14:14, 18 January 2013 (UTC)

I would suggest to put the examples in a separate section and to organize this section as follows: Starting with an explicit matrix with integer coefficients, continue with "Gaussian elimination produces this echelon form" (an echelon form with pivots different of 1 and involving fractions) "An echelon form with one as leading coefficients may be deduced by dividing each row by its leading coefficient, giving this". "Multiplying each row by the GCD of the denominators of its entries gives this integer matrix". "The (unique) reduced row echelon for is that". Eventually, one could give the output for the same matrix of Bareiss algorithm and Hermite Normal form. This would have the advantage to well clarify the differences between all these definitions. D.Lazard (talk) 15:01, 18 January 2013 (UTC)

Alright, I updated the definitions for now, and I'm working on the examples and lead. Let me know if there's something wrong with my modified definitions or if something doesn't fit what was discussed. I'll also try to fix up the lead and move some of that clutter. 98.235.185.74 (talk) 15:48, 18 January 2013 (UTC)

The Hermite Matrix

The definition of row-reduced form is a bit confusing. Here I address the comments of both Rawling and Zebulong64 above, suggest criteria to use in defining a row-reduced matrix, and correct the definition of an Hermite matrix. It would be nice, in applied mathematics, to motivate calculating the Hermite matrix H by noting that non-zero columns of I-H form a basic, independent, solution set of Ax=0. The algorithm chosen, such as Gauss-Jordan, would determine the definition of a row-reduced matrix R. The construction of H, matrix R appended with zero rows to make a square matrix, should illustrate three things: (1) From its construction, it is row-equivalent to A, so it has the same solution set. (2) From its construction, H is idempotent; that is, HH = H. Consequently, A(I-H) = H(1-H) = H - HH = H - H = 0 Consequently, a (basis for the) solution set is I-H. (3) From its construction, each non-zero column has at most c 1 non-zero elements, making the solution 'basic'. This, for example, is an interpretation of the balancing of chemical reactions by constructing an Hermite matrix, each column of A being a chemical species, each row of A being a compositional component. 'Basic' solutions have the advantage here of satisfying Gibbs's phase rule, which guarantees their interpretation as chemical reactions. The details depend upon the choice of algorithm (described in pseudocode). Geologist (talk) 01:34, 15 March 2008 (UTC)

New Algorithm for Obtaining Row-Echelon Form (Not Reduced)

I've posted a psuedocode algorithm for converting a matrix to it's row-echelon form. Hopefully the algorithm stands the test of time better than the first (for reduced row-echelon form). I've left the first in place in the hopes that someone is clever enough to alter it, rather than completely rewrite it, so that it works. Hope this helps.

Rgrant222 (talk) 04:50, 13 September 2010 (UTC)

Rgrant222 - I think that all that needs to be done to turn the current pseudocode algorithm for row echelon form to the reduced variety is to add a division of the pivot row by the pivot element before that rows values are subtracted from the others to make all other elements in the current pivot column equal to zero. In theory, that means that one properly placed for loop should do the trick.KlappCK (talk) 14:13, 13 May 2011 (UTC)

Why is "echelon form" a wikipedia subject?

I do not understand why wikipedia should elevate the terminology "echelon form" to such importance that it is a separate page. No links are given to other subjects that use the terminology except Gaussian elimination. It suffices for the Gaussian elimination pages to point out that a triangular matrix is sometimes described as being in "echelon form." In fact, the echelon terminology is not used in numerical analysis, which is the principal field that studies Gaussian elimination. Jfgrcar (talk) 17:07, 2 October 2010 (UTC)

Equal Sign and Assignment Sign ambiguity

In programming there are two types or equal signs: one indicating assignment, for example assign a value to a variable (i:=i 1) and other verifying equality, for example used in conditional sentences (if a=b then a:=2*b). In the pseudo code there is inconsistence between these differences. — Preceding unsigned comment added by Zeusescudero (talk • contribs) 01:45, 9 March 2011 (UTC)

First nonzero entry in each row = 1 (left to right)

I have a linear algebra textbook (Linear Algebra with applications, 8 ed. by Steven J Leon, ISBN-13: 987-0-13-600929-0) that lists that a matrix is considered in row echelon form only if "the first nonzero entry in each nonzero row is 1". (page 13) The other requirements it lists are consistent with this article, and it gives examples (with answers) that confirm its definition and contradict this article's definition.

Is the textbook's interpretation invalid (and if so, what information and sources could I send the publisher to rectify this in subsequent editions), or does it represent a valid alternate interpretation? Is this alternate interpretation notable enough to justify mentioning in the article? (It's certainly the one I must use to pass MATH 301 at Boise State University, and any other institution that uses this book.) — Preceding unsigned comment added by 75.174.125.203 (talk) 23:42, 5 September 2013 (UTC)

EDIT: I see the addition on the main page now. — Preceding unsigned comment added by 75.174.125.203 (talk) 23:54, 5 September 2013 (UTC)

Additional topics that could be added to this article

- The relationship between row echelon form and upper triangular matrices.

As an example: ${\begin{pmatrix}0&1&1\\0&1&2\\0&0&0\end{pmatrix}}$ is an upper triangular matrix that is not in row echelon form.

- Most matrix decomposition algorithms produce an $R$ that is in row echelon form.

Most matrix decomposition algorithms $A\mapsto M\cdot R\quad {\text{so that}}\quad A=MR$ where $R$ is an upper triangular matrix actually output an $R$ that is in row echelon form (most notably this is the case for LR-decomposition). This is especially important for forward/backward substitution (e.g. for above example triangular matrix, forward substitution could not be applied). In the current form, forward/backward substitution is expanded upon on the site for triangular matrices, where it neglects the case that $l_{i,i}$ is zero.

- Forward/backward substitution should be on this site, not on the site for triangular matrices

- Reduced row echelon form gives an easy method to describe the vector space spanned by an linear equation system $Ax=b$.

As an example, take $\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]\cdot \left[{\begin{array}{c}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{array}}\right]=\left[{\begin{array}{c}y_{1}\\y_{2}\\y_{3}\end{array}}\right]$. Then we can solve the first row for $x_{1}$, the second for $x_{2}$ and the third for $x_{4}$, and take the remaining variables as free variables. We therefore arrive at the solution set $\left\{\left[{\begin{array}{c}y_{1}-a_{1}x_{3}-b_{1}x_{5}\\y_{2}-a_{2}x_{3}-b_{2}x_{5}\\x_{3}\\y_{3}-b_{3}x_{5}\\x_{5}\end{array}}\right]\mid x_{3},x_{5}\in \mathbb {R} \right\}$

This method is described e.g. in the German book "Lineare Algebra by Jörg Liesen" in Chapter 6, "Lineare Gleichungssysteme"

(This method basically is a generalized backward substitution that works for underdetermined systems and returns all solutions instead of one) Sanitiy (talk) 17:31, 21 December 2019 (UTC)

Improper pivot definition

In adding citations to the article, I noticed that “pivot” is given as a synonym of “leading coefficient.” But I have been unable to find this sense of “pivot,” instead only finding the sense I am more familiar with—i.e. a leading element selected during Gaussian elimination (or perhaps some other algorithm) (See Pivot element). So the term is meaningless when not referring to a specific algorithm and even then not every leading coefficient would be a pivot. Of course, I have limited time and textbooks to look through and I wouldn't be astonished if pivot had taken on the meaning given in the main article. But I think it is more likely that it was mistakenly added and overlooked by other editors. Bhbuehler (talk) 00:31, 17 December 2022 (UTC)

I agree. Moreover, even if some authors have used "pivot" in this sense, this adds nothing to the article to mention this here, as this meaning belongs to Pivot element, and more sepcifically the its section Pivot position. So, I have rewritten the sentence, and removed also "leading coefficient" (the use of "coefficient" instead of "entry" seems uncommon for native English speakers, and its use in English seems result from mimicking non-English languages such as French, where the equivalent of "entry" is not used) D.Lazard (talk) 09:24, 17 December 2022 (UTC)

Row echelon form (not reduced) algorithm fails if the first two rows are linearly dependent.

Examples:

3x3 matrix [1, 2, 3; 2, 4, 6; 1, 0, 1]

4x2 matrix [1, 1; 2, 2; 0, 1; 1, 0] 75.188.103.113 (talk) 00:02, 16 May 2023 (UTC)

True, this algorithm does not take into account the case where pivoting introduces new zero rows. Also, as all pivots are taken on the main diagonal, the pseudocode cannot produces a correct result when the echelon form has pivots that are not on the main diagonal, such as, with your notation, [1, 0, 0, 2; 0, 0, 1, 3]. So, I have removed this code.

I will also remove the other pseudo code, per as WP:verifiability: the code is not sourced, and the lack of comments makes difficult to relate the steps of the code with the description of the algorithm given in the preceding sections; so only experts can verify that the algorithm is the same as the one that has been described before. D.Lazard (talk) 09:40, 16 May 2023 (UTC)

New section on Schubert cells

I have renamed § Affine spaces of echelon forms and Schubert cells a new section. For trying to understand the content of the beginning of the section, I cleaned up the beginning of the section, which is essentially a duplication of the beginning of the article, except for the dimension of the affine space of the reduced row echelon forms of a given shape, which is not sourced and to which WP:CALC does not apply.

The second part can be understood only by specialists of Schubert calculus. It is so vague that I am unable to understand what is intended here: This may be to provide an example of Shubert calculus, in which case this should be in Schubert calculus, since readers of this article are not supposed to know Shubert calculus, while readers of Schubert calculus know certainly linear algebra and thus roe reduction. The aim may be also to provide some properties of row echelon forms, no such property is properly stated, and no source is provided for verifying the assertions.

In summary this new section is a mess, and seems WP:OR. I am inclined to remove it, but, before, I'll wait for some inputs by KarlJacobi‎ and other editors. D.Lazard (talk) 11:50, 18 October 2023 (UTC)

I have noted the corrections you made, and added some more of my own.

The section header change is fine, and so is the formula correction you made.

The purpose of the added section is to provide more explicit information on the location of 0's and 1's in reduced echelon matrices, and on the dimensions of the affine spaces of matrices with the same structure (which you called "shape").

The added material mainly requires a knowledge of linear algebra at the same level as the rest of the article, except for the example of Schubert cells for Grassmannians, which is the most important application of row echelon form in enumerative geometry. There are links provided to the articles on Grassmannians and Schubert varieties. I have added a citation for the dimension formula, but also explained why it holds, which only takes a couple of lines to do.

The new version is now split into two smaller sections, which are more clearly written, and fully referenced. These add pertinent information, both on the dimension of the space of parameters and on the main enumerative geometrical application of row echelon form.

The two smaller sections are, first, on the dimension of the space of reduced echelon forms and, second, on the maximal rank case (Schubert cells of Grassmannians).

I have added the citations requested (the textbook "Young Tableaux With Applications to Representation Theory and Geometry", Chapt. 9.4. by W. Fulton (Cambridge Univ. Press, 1997) and the article "Schubert Calculus" (American Mathematical Monthly, 1972), by S.L. Kleiman & D. Laksov), as well as further links to related Wikipedia articles. Since this provides the reference citations requested, I have removed the tag asking for these to be added.

KarlJacobi (talk) 20:44, 18 October 2023 (UTC)

Please, do not change your posts except immediately after having posted them. It is not to people who have read the first version to check the difference between versions. Here, please, restore the first version of the post, and explain the changes in a new post. D.Lazard (talk) 08:52, 20 October 2023 (UTC)

Sorry, I am not accustomed to using the "talk" page for making such comments and replies. I think it would be superfluous to now go back and re-edit the exchanges in my reply to your comment, just to have the sequence recalled. I believe the current reply covers all the points you raised, including the provision of citations, the correction of the dimension formula and the subdivision of the material into smaller sections. Thank you for your suggestions.

I have made some further edits meanwhile, mainly to improve the English usage. I would be interested to know if you agree with my comment (in the revision of the paragraph referring to permuting the columns) that this is actually out of place in a discussion of row echelon form, since such transformations alter the row echelon form, and hence are not permitted in Gauss-Jordan elimination. KarlJacobi (talk) 17:17, 21 October 2023 (UTC)

I have fixed the indentation of this thread per WP:TPHELP#Indentation, and I hope that the paragraph breaks that I had to insert in your posts are correct. I have made further minor copy-edits.

The section on Schubert cell is definitively not understandable for people who do not know Shubert theory. It is possible that this theory belong to linear algebra (I am not sure), but many experts in linear algebra do not know it, and certainly most people that are possibly interested in this article never heard of Schubert theory. So, this section is not relevant for this article unless you are able to edit the section on Shubert cells for making clear its relevance to this article, and making it accessible to a wide audience. D.Lazard (talk) 18:23, 21 October 2023 (UTC)