Talk:Row echelon form

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Importance
 Field: Algebra

Goto??[edit]

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[edit]

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 columnCountlead 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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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)[edit]

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?[edit]

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[edit]

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 (talkcontribs) 01:45, 9 March 2011 (UTC)

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

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)