Talk:Gaussian elimination

Picture of Blackboard

Who put up the goofy picture of a black (actually, green) board and why? I is hard to read and does not add much. Jfgrcar (talk) 09:11, 5 December 2011 (UTC)

Algorithm

Can somebody clean up the algorithm, its poorly done as is. That and maybe a version in C and FORTRAN which are formal languages. That way clarity is enhanced.

Ideally the algorithm should be able to deal with m by n matrices, so that some who have a square matrix and others with a column augmented matrix can all be accommodated.

I also suggest some links to open textbooks that have details on the topic.

—Preceding unsigned comment added by Veganfanatic (talk • contribs) 01:22, 21 June 2010 (UTC)

An over-determined system; that is, m≥n, need not be considered, for an over-determined system may not have a solution. Treatment of an m≤n system is the same as that of an m×m system. One can move n−m variables into the augmented term. The elimination algorithm can be made more systematic by: (a) Normalizing the leading element in each row to unity; (b) Subtracting the first row from every other row to eliminate the leading element in every other row; (c) Repeating the above two steps by moving down to the second row, and then to the third row, etc., one row at a time, until an echelon form is reached. 70.31.163.151 (talk) 15:11, 3 August 2015 (UTC)

Mathematical error

Under the section "General algorithm to compute ranks and bases" the article states:

This echelon matrix T contains a wealth of information about A: ... the vector space spanned  by the columns of A
has as basis the first, third, fourth, seventh and ninth column of A (the columns of the ones in T),
and the *'s tell you how the other columns of A can be written as linear combinations of the basis columns.

This must be an error. The operations in the algorithm preserve the row space, not the column space of A. The column space of T is always spanned by a standard base, and this is not true for an arbitrary matrix A.SanderEvers 08:25, 29 June 2007 (UTC)

Who or what is or was Jordan?

The page Gauss-Jordan elimination currently redirects here, with many backlinks, but this article makes no mention of this name except to use it with no explanation about half way down. Does anyone know anything about this term - is it a synonym, an extension, a misnomer? And, as my subject heading says, where does the Jordan bit come from? - IMSoP 13:35, 19 Apr 2004 (UTC)

A Google search reveals that it refers to the geodesist Wilhelm Jordan (1842 - 1899), "who applied the method to finding squared errors to work on surveying". Not to be confused with either Marie Ennemond Camille Jordan or Pascual Jordan. -- Dissident 13:58, 19 Apr 2004 (UTC)

Gauss-Jordan elimination computes a diagonal matrix, rather than the triangular matrices usually found in Gaussian elimination. G-J elimination should probably be a separate page, with a mention/comparison here. —The preceding unsigned comment was added by 24.236.179.177 (talk) 17:31, 8 April 2007 (UTC).

Row echelon form

This article currently mentions reduced row echelon form, but not row echelon form, which it should because the two are not the same thing and because row echelon form redirects to this article. —Lowellian (talk)[[]] 21:36, Oct 8, 2004 (UTC)

It should also be noted that when I learned this, they said proper row echelon form was in the form:

1 n₁ n₂ | n₃

0 1 n₄ | n₅

0 0 1 | n₆

In other words, it is the same as the row echelon form currently used, but it is reduced so that the first non-zero number in each row is a 1. However, the numbers to the right of the 1s are not reduced, as they would be in reduced row echelon form. —Preceding unsigned comment added by 99.153.132.151 (talk) 03:19, 12 February 2009 (UTC)

Instability

As far as I know (but I'm not an expert on numerical analysis), one major reason why Gaussian elimination is never used for solving large systems in floating-point arithmetic is that it is quite unstable. Any error you commit at any point gets propagated. Iterative method, working on attractive fixed points, are much better in that respect. David.Monniaux 20:37, 15 Dec 2004 (UTC)

Gaussian elimination can indeed be unstable, even when using pivoting. Theoretical studies shows that it can be very unstable, but it is generally not a problem in practice. This discrepancy is not well understood. Gaussian elimination is not used for large systems because of its n^3 price tag; the instability may also be a reason but it is not often mentioned. A lot can (and should) be written in the current article about stability problems. Unfortunately, numerical linear algebra is not quite my speciality and I have no time at the moment, so somebody else has to do this. -- Jitse Niesen 21:32, 15 Dec 2004 (UTC)

All major FEM codes use Gauss or a variant thereof for very large (elastic-linear) systems with more than 100,000 Variables... above comment is no more relevant HH Dec 2011

I would assume that the Gaussian elimination uses partial pivoting for FEM (Finite Element Method?) codes, since that's the standard way of doing things. Many large systems are sparse, which is why iterative methods (which exploit the sparseness) can be cheaper.Eweinber (talk) 06:59, 14 April 2012 (UTC)

Fuziness as to what is the T matrix

In the section titled "The general algorithm to compute ranks and bases", it is stated that "This echelon matrix T contains a ..."

The implication is that the example matrix is the T matrix, but this is never explicitly stated. Wouldn't it be clearer if the matrix was preceded by "T = ..." ?

Two suggestions to simplify the three rules

First, this isn't really a bug and most other books/articles publish the three rules for equivalent transformations nearly the same way:

1) Multiply or divide a row by a non-zero value.
2) Switch two rows.
3) Add or subtract a (not necessarily integer) multiple of one row to another row.

1st suggestion for the 1st rule: remove "or divide" and add "real" before "value" (reason: dividing by value 'x' is equivalent to multiplying by value '1/x')

2nd suggestion for the 3rd rule: replace the whole rule by

3) Add one row to another row.

(reason: old rule 3 is a concatenation of rule 1 and new rule 3, or in other words: the old rule 3 contains rule 1)

[In case you want to contact me, send a mail to ibbis at gmx dot de.]

I would like to second the simpler rule 3, "Add one row to another row." — Preceding unsigned comment added by Tom-oconnell (talk • contribs) 00:36, 28 May 2017 (UTC)

For the first rule, "real" cannot be added, as Gaussian elimination can be done over non-real fields (complexes, finite fields, ...). "Divide" could be removed, but keeping it may be clearer for people for which it is not immediate that dividing is equivalent with multiplying by the multiplicative inverse.

The third rule can be deduced from the simpler rule and rule 1 by combining rule 1, new rule 3 and the reverse of rule 1 (for putting back the multiplied row to its initial value; keep in mind that only one row is modified by rule 3). Thus the suggested rule 3 is simpler to state and less simple to use. If you want simple rules that are difficult to apply, you could also suppress rule 2, as it may be realised by applying tree times new rule 3 followed by changing a row of sign.

Other reasons for keeping the rules as they are 1/ Rule 3 does not change the determinant of the matrix (this is used in many applications) 2/ computer implementations use these rules, and replacement of rule 3 would product programs that would be more difficult to write, and less efficient. D.Lazard (talk) 09:35, 28 May 2017 (UTC)

I also think that rule 3 is not elementary, since as is pointed out in the first comment, and two options are tractable : i) discard "elementary" from the sentence, or ii) state simply "Add one row to another row." 130.190.20.157 (talk) 06:14, 9 October 2023 (UTC)

In "elementary row operation", "elementary" does not mean that the operations are easy to understand, but means that these operations are done by multiplying with an elementary matrix. This is a traditional terminology, and, so, cannot be changed in Wikipedia. D.Lazard (talk) 11:56, 9 October 2023 (UTC)

Also, the elementary row operations are very elementary when looking on corresponding matrices: the matrix of operation 1 is an identity matrix with one diagonal element changed; the matrix of operation 3 is an identity matrix with one zero entry changed to a nonzero value; the matrix of operation 2 consists of exchanging, in an identity matrix, $a_{i,i}$ with $a_{i,j}$ and $a_{j,j}$ with $a_{j,i},$ So, the matrices of elementary operations are very elementary matrices. D.Lazard (talk) 13:21, 9 October 2023 (UTC)

Formatting

The matrices should really be in []s, not ()s. 129.44.216.105 02:24, 9 March 2006 (UTC)

REF and RREF requirements

I've edited the rules that determine whether a matrix is in REF/RREF, as they were wrong. Specifically, the article (before my edit) stated that every leading coefficient must be 1 for a matrix to be in REF; This is actually a requirement for RREF. I've also cleaned up the formatting in that area to make the rules clearer. My source for the rules is:

Lay, David C. "Linear Algebra And its Applications". Third Edition - Low Price Edition, Page 30.

If anyone finds a source to the contrary, I would be interested - I don't know where the original information on the page came from.

Braveorca 23:30, 24 May 2006 (UTC)

According to Talk:Row echelon form, Larson and Hostetler, Precalculus, 7th edition, states that the leading coefficients has to be one for row echelon form. -- Jitse Niesen (talk) 13:51, 2 December 2006 (UTC)

Rewritten

i've been working on a huge rewrite of this (and the split-offs it spawned, heh) for a couple of days, and it's now done. I think it's all consistent and correct, but I haven't checked the source code examples and proofread very thoroughly (because my head hurts from too much of this). Any changes to fix stuff would be greatly appreciated. I think the rewrite fixes some major problems of the old one (no offence :)), making it more modular and, most importantly, noting that gaussian elimination is not the same as gauss-jordan (though there are other "fixes" as well). -- Braveorca 02:01, 27 July 2006 (UTC)

Floating-point numbers to zero

I'm not a numerical specialist, but I do know that, although in general you shouldn't compare two floating-point numbers for equality, zero is a special case; it has an exact representation. Is there an algorithmic reason a small epsilon should be used instead of zero?

The problem is with the way in which numbers are stored and manipulated in a computer. Numbers are represented internally as binary numbers, and all mathematical operations are done in binary arithmetic, usually floating point. Internal numbers are limited in size, so rounding errors occur. Numbers are then displayed in decimal form. As an illustration, I just did the following calculation, using perl: (11/7)*(7/11)-(13/5)*(5/13) The result clearly should be zero, but in fact is 5.42101086242752217e-20 That is less than 0.000000000000000000006, obviously very small, but not zero, so comparing against zero would show inequality.

I usually compare against 1e-18, instead of zero, when using floating point numbers, however that is machine and platform dependent.

---

I think that some of the above statements and the remark in the article are the result of some misunderstanding or fuzzy thinking regarding how floating point works. There's some belief that floating point is a little random or uncertain or imprecise, but this isn't really any more true for floating point than fixed point, such as their special case, the integers. It is true that rounding errors and the lack of an exact representation for most real numbers often requires using a comparison band. However, it isn't true that floating point numbers will always be slightly off, or that they are incapable of exact representation of a particular number--and it isn't true that exact equality should never be used with floating point, which seems to be what is implied here.

I beleive the remark in the article is one of these misstakes, and should be removed. It is essential that the leading coefficient in each row be 1, not just something that is close to 1. And yes, in any sane non-broken fp implementation, dividing a number by itself will yield exactly 1. And yes, any sane non-broken fp implementation has an exact representation of 1. FP implementations don't just produce random imprecisions for no good reason, contrary to popular belief. Also, what specifically does testing for a narrow band around 1 instead of 1 itself add, even if this were a valid test? Dividing the row by a number very close to 1 is unlikely to have any significant negative effect on the result, unless the matrix is ill-conditioned, in which case other sources of error will probably be more significant anyway. Is this supposed to be some sort of ill-conceived performance optimisation suggestion, perhaps?

In fact, I think I'm going to remove the fp eps comment from the article. If you feel it needs to be re-added, please discuss it here. AaronWL 05:47, 10 November 2006 (UTC)

I'm sorry, but I've no idea what you're talking about. We're not talking about comparing to 1, but about comparing to 0. Surely, it can happen that a matrix which in exact arithmetic would give a zero pivot, gives a small but nonzero pivot in floating point. If not, why not? -- Jitse Niesen (talk) 06:38, 10 November 2006 (UTC)

You seem to have misunderstood the statement that floating point should not be thought of as random. Floating-point arithmetic is certainly not random, but it is not generally exact either. Floating-point arithmetic is exact only when the result of an operation can be exactly represented as a floating-point number, for example when both inputs are integer-valued and the result is integer value (for small integers), but this is not generally the case. It is definitely not the case for Gaussian elimination, even if the input matrix has small integer entries since Gaussian elimination relies heavily on division. Also, comparing against 1e-18 often doesn't make sense since it is smaller than the machine epsilon in double precision arithmetic. It may work with with 80-bit extended doubles, but they are not supported everywhere. Also be careful to distinguish between absolute and relative differences when comparing. Fredrik Johansson 11:24, 11 November 2006 (UTC)

Contradiction

Gauss–Jordan elimination article states:

In other words, Gauss-Jordan elimination brings a matrix to reduced row
echelon form, whereas Gaussian elimination takes it only as far as row
echelon form. It is considerably less efficient than the two-stage
Gaussian elimination algorithm.

Gaussian elimination article states:

Equivalently, the algorithm takes an arbitrary matrix and reduces it to
reduced row echelon form (also known as row canonical form).

Stated equivalently for matrices, the first part reduces a matrix to
row echelon form using elementary operations while the second
reduces it to reduced row echelon form, or row canonical form.

To me it sounds as if though Gaussian elimination is one stage and Gauss-Jordan is two stage. Yet they both contradict this aspect. --ANONYMOUS COWARD0xC0DE 05:36, 19 January 2007 (UTC)

I think the source of your confusion is that the two operations referred to in each article are different. In the Gauss-Jordan article, when it says "two-stage Gaussian elimination algorithm" it means: you first use Gaussian elimination, then find the solutions by back-substitution. It is this back substitution that is the stage 2. In Gauss-Jordan elimination, you have to work harder to get the reduced row echelon form, but then no back substitution is necessary.

A previous edit mentioned Lay's Linear Algebra and Its Applications as a source; nothing wrong with that but for a deeper treatment with more references, a very readable text is Carl Meyer's Matrix Analysis and Applied Linear Algebra. For more on the stability of Gaussian elimination, I would recommend Trefethen and Bau's Numerical Linear Algebra.

So they both give the same results, just a different way of doing it. Therefore Gauss–Jordan elimination article should be changed like this:

 In other words, Gauss-Jordan elimination brings a matrix to reduced row
 echelon form., whereas Gaussian elimination takes it only as far as row
 echelon form. It is considerably less efficient than the two-stage
 Gaussian elimination algorithm.

? --ANONYMOUS COWARD0xC0DE 23:10, 23 January 2007 (UTC)

Why? They both give the same results in that they both solve Ax = b, but Gaussian elimination does not reduce the matrix to reduced row echelon form. Putting it otherwise:

• Gauss-Jordan elimination brings a matrix to reduced row echelon form, after which solving the system is trivial
• Gaussian elimination brings a matrix to row echelon form and uses backsubstitution to solve the system

So I don't agree with your proposed change. -- Jitse Niesen (talk) 01:36, 24 January 2007 (UTC)

I'll restate my problem as I now see it; Either Gaussian elimination reduces to reduced row echelon form or just row echelon form. You can't say both!

Therefore if you deem my first proposed change to be unnecessary then the change would have to be

Gaussian elimination article states:

  Equivalently, the algorithm takes an arbitrary matrix and reduces it to
  reduced row echelon formrow echelon form(also known as row canonical form).

  Stated equivalently for matrices, the first part reduces a matrix to
  row echelon form using elementary operations while the second
  reduces it to reduced row echelon form, or row canonical form.

--ANONYMOUS COWARD0xC0DE 05:39, 5 February 2007 (UTC)

Or are you saying that back-substitution should not be a part of the Gaussian elimination algorithm? It seems like an important aspect, therefore I doubt this interpretation. I hypothesise this from the "first use Gaussian elimination, then find the solutions by back-substitution" statement, which seems to reinforce a separation of back-substitution from the Gaussian elimination algorithm. Or is there a difference between Gaussian elimination and Gaussian elimination algorithm. --ANONYMOUS COWARD0xC0DE 05:39, 5 February 2007 (UTC)

"The Gauss-Jordan (GJ) method is a variant of Gaussian elimination (GE). It differs in eliminating the unknown equations above the main diagonal as well as below the main diagonal. The Gauss-Jordan method is equivalent to the use of reduced row echelon form of linear algebra texts. GJ requires 50% more multiplication and division operation than regular elimination. However, it can be used to produce a matrix inversion program that uses a minimum of storage. Solving $AX=I$ using GJ gives $X=A^{-1}$." — Atkinson, Kendall E., An Introduction to Numerical Analysis, 2e., pp. 522-523. Another point to note is that the pseudocode given in the Gaussian elimination article implements Gauss-Jordan elimination, not Gaussian elimination. Bekant 23:52, 5 February 2007 (UTC)

Thanks, but the problem is whether or not Gaussian elimination reduces to reduced row echelon form, not Gauss-Jordan. The problem with the Gauss–Jordan elimination article is that it says Gaussian elimination does not bring a matrix to reduced row echelon form, but the Gaussian elimination article says it does. Jitse Niesen says that Gaussian elimination does not bring a matrix to reduced row echelon form, but did not comment further on the contradiction present in the artical. --ANONYMOUS COWARD0xC0DE 02:40, 18 February 2007 (UTC)

Let me restate this once again: if back-substitution is part of the Gaussian Elimination algorithm then Gaussian Elimination does bring a matrix to reduced row echelon form and the Gauss-Jordan article must be changed. Otherwise if back-substitution is not part of the Gaussian Elimination algorithm then Gaussian Elimination brings a matrix to JUST row echelon form and the Gaussian Elimination article needs to make explicit that back-substitution is NOT part of the algorithm. --ANONYMOUS COWARD0xC0DE 02:40, 18 February 2007 (UTC)

As of 2007-05-17

Gaussian Elimination article:

Equivalently, the algorithm takes an arbitrary matrix and reduces it to
row echelon form.

A related but less-efficient algorithm, Gauss–Jordan elimination,
brings a matrix to reduced row echelon form, whereas Gaussian elimination takes
it only as far as row echelon form.

Stated equivalently for matrices, the first part reduces a matrix to
row echelon form using elementary operations while the second reduces
it to reduced row echelon form, or row canonical form.

At the end of the algorithm, we are left with
${\begin{bmatrix}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{bmatrix}}$

That is, it is in reduced row echelon form, or row canonical form.

Gauss-Jordan elimination article:

In other words, Gauss-Jordan elimination brings a matrix to
reduced row echelon form, whereas Gaussian elimination takes it only as far
as row echelon form.

---

Sorry guys you haven't convinced me that these contradictions are non-existent. I am getting tired of people ignoring blatant contradictions. Please open your eyes and fix it or I will (someday). --ANONYMOUS COWARD0xC0DE 02:10, 18 May 2007 (UTC)

What makes you think that we disagree? If you think you can improve the article, go ahead and fix it. We're all volunteers with limited time, so it won't help to get frustrated about it. -- Jitse Niesen (talk) 12:56, 19 May 2007 (UTC)

I think the reality is that the article describes Gaussian Elimination with Backsubstitution, but mistakenly refers to this whole process as Gaussian Elimination (GE). GE is the process of reducing a matrix to upper-triangular form (see section 2.2, Press, Teukolsky, Vetterling, and Flannery, Numerical Recipes in C++, 2nd edition). Following GE, backsubstitution may be used in order to solve for the unknowns in a system of linear equations.Bekant 20:31, 17 August 2007 (UTC)

Too many END_IF statements in the pseudocode! 1 more than there are IF statements... (#)

See headline —The preceding unsigned comment was added by 63.243.91.254 (talk) 18:36, 9 February 2007 (UTC).

Thanks. -- Jitse Niesen (talk) 08:37, 11 February 2007 (UTC)

Citecheck tag

Why is the citecheck tag on this article? Which citations need support? What citations would you like added? Would you like to see a reference to a layman (undergrad) introduction to Gaussian elimination or to some more advanced material in numerical linear algebra? I could not find any information about it in the talk page. Maybe I could help. Fph 13:31, 19 March 2007 (UTC)

It's about the difference between reduced row echelon form and row echelon form, see the Section "contradiction" above. Actually, I think the article needs a complete overhaul (addressing the pivoting issue you mention below), so I don't feel like doing all sorts of small corrections. -- Jitse Niesen (talk) 00:23, 20 March 2007 (UTC)

Pivoting

I think more information about partial pivoting should be added. As the page is now, pivoting is only explained through a pseudo-code algorithm, and is never properly introduced. I suggest adding an appropriate section. Fph 13:36, 19 March 2007 (UTC)

Intro cleanup

Reading over the intro paragraph to this article, it struck me as taking a long time to get around to revealing exactly what Gaussian elimination is, so I fixed it. Now, I'm an English person, not a math person, so please check over it and fix any factual errors I may have inserted. I just felt the textual style could be cleaned up a bit. Thanks, Applejuicefool 14:24, 10 May 2007 (UTC)

Is this article confusing?

I would like to post comments on this article. In general, I have found Wiki to be exceptional and outstanding in its content. However, this particular article has left me quite perplexed. Please take my comments with a grain of salt, I do not know everything about matrix algebra. The first source of confusion is that in textbooks, online course notes (from professors), and hundreds of online references, most people today think of Gaussian elimination as an algorithm that, essentially, computes PA = LU. While this is mentioned in the article, the article seems to actively support the notion that the correct way of thinking about Gaussian elimination is as a factorization into ST. This is perplexing given that the three textbooks I have describe GE as a factorization into P, L, and U. As I mentioned, searching online provides the same discussion, be it class notes, theses, etc. Further, the general GE algorithm most practitioners are familiar with is only one "part", not two parts as the article claims. This one part computes the familiar LU decomposition that we would all find in textbooks, online pseudo-code, etc. It struck me that perhaps the author found the one textbook that truthfully proved that Gauss actually thought of both parts. All the textbooks I have describe only the first part. Considering the algorithm as a two-part entity thus seems to me to be highly likely to cause confusion for many other individuals besides myself.

(You are correct. The article uses nonstandard notation. The proper notation is LU. Jfgrcar (talk) 06:34, 18 February 2012 (UTC))

Then the article claims that Gauss Elimination converts a matrix to row echelon form. The article also points out that a less efficient algorithm, Gauss-Jordan Elimination, converts a matrix to reduced row echelon form. I agree with these statements completely, as my understanding is the same. This distinction is made in the introductory section, before the table of contents for the article. Unfortunately, in the Example section, the article clearly states that at the completion of the Gaussian Elimination algorithm (after the second part), the resulting matrix is in reduced row echelon form. At the very least, this is confusing. It seems like the author(s) were, in some cases, familiar with the well-known GE algorithm, which always leaves matrices in row echelon form, regardless of whether they are augmented or not. If the discussed two-part algorithm always leaves matrices in reduced row echelon form, then at least the last sentence of the introduction must be changed. But I am suspicious of the authorship; It seems like half of the article was written with the commonplace understanding of the GE algorithm, while the last section of the example was written with the unexplained ST factorization. You will note in the Example section of the article, we move from row echelon form to reduced row echelon form with no explanation at all. Naturally, we may all be sufficiently familiar with matrix algebra to perform this missing step without concern, at least on paper. This missing transformation method has caused me quite a ruckus, as I am a numerical matrix library fellow. The article assumes I can correctly derive the algorithm needed to perform the last step myself (as if, to someone who is implementing a matrix library, this would be obvious in the general case). I beg to disagree.

Another problem is that the article states that the rank of a matrix can be trivially computed by counting the non-zero rows after the GE algorithm. Again, this would be true if GE computed the reduced row echelon form. However, this is almost never true if GE, as most textbooks describe it, only produces row echelon form. Given the confusion stated above, this is even more confusing. This might sound like a trivial objection. In fact, this fact is the only reason I am writing this post. I implemented the commonplace GE some time ago, and was baffled as to how it could be stated that rank only needs to count the non-zero rows. In practice, most matrices that are factored into LUP using the commonly-thought-of GE algorithm never have zero rows.

Lastly, the pseudo-code listing really hits me as unnecessarily obfuscated. I cannot even divine where the so-called "first part" is, let alone the "second part". Also, I believe pseudo-code should be so simple we can almost immediately implement and, to at least some degree, understand what is going on. The provided pseudo-code is opaque to me. The usual GE pseudo-code listed in textbooks is 8 lines, each of which can be trivially understood. The provided pseudo-code is 23 lines, almost triple the size. I cannot understand the intent of it at all. Therefore, as pseudo-code, can it be said, without a doubt, that it is an absolutely useful contribution to the article?

In light of these observations, I urge that the article be modified to provide the well-known and commonly accepted GE algorithm, along with its pseudo-code. If the purpose of the article was to demonstrate that the well-known GE algorithm can be expanded to include a post-processing algorithm to produce reduced row echelon form, this should be clearly stated and explored as a sub-topic of the article, and, in particular, it should be very clearly discussed how the post-processing algorithm of the commonplace GE algorithm is more efficient than the mentioned (but less efficient) alternative, Gauss-Jordan elimination. 67.164.52.124 07:59, 12 May 2007 (UTC)

Possible redirect

I was looking for this page for a class I'm taking and had trouble finding it because I was typing "Gausian" instead of "Gaussian". This seems like a fairly common misspelling; shouldn't there be a redirect for this spelling? 207.233.124.3 21:19, 15 May 2007 (UTC)

Yes, there probably should. I added a redirect. Thanks. -- Jitse Niesen (talk) 01:08, 16 May 2007 (UTC)

I made that same booboo I made last time, and noticed the redirect. Thank you, Mr. Niesen. 71.137.6.98 23:34, 17 May 2007 (UTC)

Complexity?

In the Analysis section, the article notes that the complexity of Gaussian Elimination on an nxn matrix is O(n^3). What is the complexity on an nxm matrix? —Preceding unsigned comment added by 68.106.184.113 (talk) 19:53, 19 December 2007 (UTC)

I'm not aware of any source offhand that explicitly mentions the complexity in this case. However, I would say that it is ${\mathcal {O}}(nm^{2})\,$. From an algorithm analysis perspective, eliminating the first variable is n(m-1) operations (n entries need to be multiplied and subtracted, and this needs to be done m-1 times). The second would require (n-1)(m-2) operations. This process has to be repeated m-1 times.

I found a congruent result for Gauss-Jordan elimination here so I'm fairly confident of this analysis, but remember that what I've written here is all original research. If we can find a citable source for this then perhaps we should add it. WDavis1911 (talk) 21:05, 18 April 2008 (UTC)

comment: If the matrix is not square, it is likely that there is either no solution, or an infinite number of solutions. Thus, gaussian elimination does not usually lead to a unique solution. In these cases, the algorithm is usually modified to return some "common-sense" equivalent of an answer, and these algorithms may have different run-times than the standard gaussian-elimination procedure. —Preceding unsigned comment added by 146.186.131.40 (talk) 17:01, 14 April 2010 (UTC)

Matrix inversion

This article sais that in practice, matrix inversion is rarely used since we really want to solve the system of linear equations. But this is exactly it!! Solving a system of linear equations is nothing but inverting its matrix... —Preceding unsigned comment added by 89.3.223.27 (talk) 21:54, 16 April 2008 (UTC)

For the most part, although technically it is $x=A^{-1}b$, with the system of equations being $Ax=b$. Computationally, the difference is slight, but the inversion method will require about $n^{3}$ multiplications and divisions, whereas the Gaussian elimination method will require about $n^{3}/3$ (the actual equations are more intricate but this is the essence). Both are complexity ${\mathcal {O}}(n^{3})\,$, so on a grand scale it may not matter (is it going to take one century or three centuries to finish calculating...?). However, what you are looking at essentially is 3 times the operations being required for taking the inversion route. This, I believe, is why people usually avoid trying to solve $x=A^{-1}b$ by calculating the inverse. WDavis1911 (talk) 20:11, 18 April 2008 (UTC)

"In practice, inverting a matrix is rarely required. Most of the time, one is really after the solution of a particular system of linear equations"

Despite the citations I don't believe the second part of this statement is true. The second part of the statement may be true for students in an introductory linear algebra class, however, at least in applications of process control the inverse matrix is often of greater interest than a single solution. Any application where you are solving Ax=b repeatedly in real time with a new b vector at each time instance, calculating A inverse ONCE and calculating x=A^-1 b (which is order 2 if you already have A^-1) over and over is more economical than solving Ax=b by Gaussian elimination over and over at order 3... The "rarely" and "most of the time" weasel words weaken this statement enough that even if the statement were true it fails notability.86.169.24.214 (talk) 20:11, 22 April 2009 (UTC)

In your application, you should compute and store the LU decomposition of A. Solving LUx=b takes as many operations as calculating x=A^-1 b if you already have A^-1, but it's more stable. Nevertheless, there are some situations in which the matrix inverse is required (e.g., the Denman–Beavers square root iteration for computing the square root of a matrix). I think the statement plays an important role in warning readers against a mistake often made. The statement is sufficiently notable that it's in many (if not all) textbooks on numerical analysis that mention the matrix inverse. -- Jitse Niesen (talk) 17:46, 23 April 2009 (UTC)

Too technical?

I didn't really understand this article. I'm not a math genius or anything, but isn't that the point of Wikipedia, to make information accessible to laypeople? I mean we've got textbooks to teach the technical details to math students and so on. --98.214.255.102 (talk) 05:51, 1 July 2008 (UTC)

What does "works" mean???

The article, in the Example section, states:

"This algorithm works for any system of linear equations."

I think it needs to be made clear what "works" means. For example, consider the equations

x - y = 1

y - z = 1

z - x = 1

and attempt to apply the algorithm of the example: a contradiction is reached.Daqu (talk) 00:59, 24 February 2009 (UTC)

So if you start with 0 = 1 (sum of your equations / 3), you reach a contradiction? Well, yes. If you start with a contradiction, you end with a contradiction. It's generally understood that "works" means "works when fed input that isn't self-contradictory". -- simxp (talk) 17:52, 30 March 2009 (UTC)

Nice try, but no cigar. The article states "This algorithm works for any set of linear equations." In mathematics, "any" means "any". The statement means it is true without exception. That statement is FALSE.

Given an arbitrary set of linear equations, there is no reason someone would know in advance that they are contradictory.

And by the way, a set of equations is supposed to define a solution set, so NO set of equations is "flawed"; it's simply that for some equation sets, their solution set is empty.

"Works" is NOT a technical term and -- contrary to your claim -- there is no consensus as to what it might mean in questionable cases. So the article needs to be corrected so that it is clear just what one might expect. I recommend allowing *all* sets of equations, with the statement that certain outcomes of the procedure (that should be specified) mean that the solution set is empty.Daqu (talk) 02:33, 31 March 2009 (UTC)

If you really feel that it needs to be explicitly specified that if you start from a self-contradictory set of equations, you get a contradiction, then feel free to be bold and make the relevent change yourself; I'm not going to revert you (I'm not actively opposed to spelling out the obvious, I just don't think it's necessary). -- simxp (talk) 15:48, 31 March 2009 (UTC)

What needs to be done is simply to make sure that all statements in the article are true, since that is the point of an encyclopedia.Daqu (talk) 07:42, 1 April 2009 (UTC)

Wikipedia is an encyclopedia anyone can edit. If you think something "needs to be done", Be Bold and do it. -- simxp (talk) 14:28, 1 April 2009 (UTC)

Then again, it would be nicer if I didn't need to fix errors made by other people. A responsible editor will fix their own error once it's pointed out to them.Daqu (talk) 23:35, 2 April 2009 (UTC)

A quick check shows the offending sentiment was added back in 2002. If you care about the issue enough to have a protracted discussion about it on the talk page, but only enough that you'd rather wait for the (extremely small) chance that the original editor might wander by this page again at some point in the next decade, than actually do it yourself, then good luck to you. If you really wanted, you could locate the original added and badger them about it on their talk page. The reponse you get, though, is likely to be the same as mine: "Wikipedia works on a system of gradual improvement and building on other people's work. If you care about the distinction that much, do it yourself". If you don't care enough to do it yourself, you'll likely not get a very good response by badgering other people to do it. -- simxp (talk) 16:19, 3 April 2009 (UTC)

Why, thank you for the lecture. That was an excellent use of your time. I infer that the x in your username is silent.Daqu (talk) 09:58, 4 April 2009 (UTC)

I removed the sentence. I hope that ends this discussion, or at least makes it more productive. -- Jitse Niesen (talk) 02:55, 7 April 2009 (UTC)

Row echelon form

According to the article about row echelon form, rows should begin with 1. The example from this article contradicts that.

Parallel psuedocode

The parallel psuedocode section actually just contains C code that's not exactly newbie friendly. I think this section is too complex to be "obviously correct," therefore needs to be cited. There's an implementation that we could link to on google code that makes a bit more sense to my mind [although in pivot column selection, abs isn't used, and it's not really commented any better].

At first glance, the issues with the code that's there now are that curly braces are missing (as written, k = matrix_demention will be used for the main body of gauss, although it appears the body was intended to be contained within the if (thread_id== body) and that dimension is misspelled as demention. There are also more minor errors (barrier_t not described, no mention of pthread_attr_init, the barrier is hit twice without explanation, and I don't see the pivot column selection so I'm not sure if the algorithm described actually is Gaussian).

Can someone with more math knowledge review this section? Does it even belong here? rev where it was added

Thatch (talk) 22:39, 11 October 2009 (UTC)

Non-Parallel Pseudocode

This code is barely readable and should be corrected.

1. The comment at the top explains what the text following it does, while the rest of the comments explain what code should be implemented in that spot (but the code itself is neglected). This is inconsistent and confusing.

2. We shouldn't have words explaining what the code does (that is what the rest of the article is for!). We should have an implementation of the code instead. It would be ideal if the words in the code only served to describe what the code is doing, instead of replacing the code.

3. In most languages, you start counting at zero, not one, yet this convention is broken here. I think it would be best if we tried to make it as close to real-world code as possible.

4. I think the code would be easier to read if it was constructed in for loops like the parallel code below it. This way, the two can be more easily compared. They should also use the same variable names where applicable, and access the contents of a 2D array the same as well i.e. use this notation matrix[a][b] not A[i,j]. I think the problem lies primarily with the first code while the second is a lot easier to read.

Well, I guess if you are used to code written in Fortran, this might be more tolerable to you. However, I think that most people don't know Fortran and thus aren't used to its weird conventions AND of those who do know it, they tend to agree that it is difficult code to read and maintain in the first place. So, why don't we try moving this code into something a little more user-friendly?

159.242.229.96 (talk) 19:02, 16 December 2009 (UTC)

Math-rating

May I change it from "Top priority" (seems not appropriate to me) to "High priority" and from "Start class" to "C"? Franp9am (talk) 21:16, 28 August 2011 (UTC)

Seconded; I'm going to go ahead and update the quality rating to C-class; I support lowering its priority to High, but I'll leave that step to someone else. -Bryanrutherford0 (talk) 03:38, 18 July 2013 (UTC)

Shouldn't the article emphasize the name 'Row Reduction' not Gaussian Elimination?

The History section clearly indicates that the method of Row Reduction had little to do with Gauss. Why should we continue to emphasize this historical misunderstanding (the Chinese discovered the method more than 2000 years ago!!!)? Shouldn't we reduce the role of the name 'Gaussian Elimination' to a synonym that is in common usage? The name 'Row Reduction' is also more descriptive of the process and is in common usage as well. Therefore, I recommend changing almost all occurrences of the name 'Gaussian Elimination' with the name 'Row Reducation' while adding appropriate text to indicate that the name 'Gaussian Elimination' is a common synonym that is historically false and inaccurate. Cjfsyntropy (talk) 22:32, 15 November 2011 (UTC)

Nobody calls it "row reduction". It is not the purpose of Wiki to rewrite the subject. Jfgrcar (talk) 06:30, 18 February 2012 (UTC)

Well, I call it "row reduction". In fact, I find the distinction between "Gaussian elimination" and "Gauss-Jordan elimination" quite superficial, since the process really is the same (row operations on matrices). I would suggest merging these two articles to clarify the situation. I would also favour renaming a merged article to "Row reduction". Mark M (talk) 08:56, 25 December 2012 (UTC)

I would suggest to merge also these two articles with Row echelon form. In fact, row echelon forms are defined independently of any algorithm and Gaussian and Gauss-Jordan eliminations are the most natural algorithms to compute them. Without such a merge, I do not see how to explain that "the result of Gauss-Jordan elimination is independent of the way of doing Gauss-Jordan elimination". By the way, properly speaking, Gauss-Jordan elimination is not Gaussian elimination followed by a further reduction; this "further reduction" is mixed with Gaussian reduction. It is only the unicity of the result that allows to call Gauss-Jordan elimination these two different algorithms. D.Lazard (talk) 10:27, 9 February 2013 (UTC)

I would like to keep the articles separate. Under echelon form it is already a hyperlink to the article about row echelon form and the reduced echelon form. The linked article ( Row echelon form ) supplements this article by providing an example that would be redundant in this article, but is in my opinion more easy to read and understand quickly ( see figure ). The Row echelon form article is more a description of how to do the reduction by hand, and the practical maths of it, while this article is more about the algorithm-based approach. Merging would make this article more cluttered, and less readable. This, in my view, makes the two articles incompatible for merging without a major re-write. --Magnus0re (talk) 12:06, 14 July 2015 (UTC)

Gauss-Jordan elimination now merged

I've finished merging on Gauss-Jordan elimination. There were a few sourced claims that I haven't checked the sources for (because I don't have them), so I just copied them over directly.. hopefully in the process I didn't introduce too many mistakes. Mark M (talk) 09:44, 1 March 2013 (UTC)

Introduction Example

Could someone maybe change the matrix in the example to one that has a unique solution? It's been awhile since I've tried to solve a system of equations but since that's what this is used for most of the time (?) wouldn't it be useful to have an example people could work themselves? If the point of reducing the matrix to row echelon form is to make the system easier to solve it would be helpful for people to see that the system has a solution, or at least to point out that the system has no unique solution (and explain why given the form of the matrix). I'd do it myself but like I said, I'm a bit rusty. Lime in the Coconut 17:14, 14 June 2013 (UTC)

One of the main interest of Gaussian elimination is that it works well with non invertible matrices, contrarily to many other algorithms, like Cramer's rule or inverting the matrix. As it is, the example emphasizes this property. Changing the example to an example with a unique solution would thus decrease the amount of information provided to the reader. D.Lazard (talk) 18:29, 14 June 2013 (UTC)

Row echelon form (August 2013)

Row echelon form should never be merged with Gauss elimination as both are completely different ways.As Gauss elimination is the first step of Gauss Jordan method which is used to find system of equations.Row echelon is used only for finding Rank of a matrix.If any confusion then please consult me. — Preceding unsigned comment added by Praveen.ujjain (talk • contribs) 07:48, 25 August 2013 (UTC)

You are wrong when asserting that row echelon form is used only for rank computation. Row echelon form is the result of Gaussian elimination, and reduced echelon form is the result of Gauss-Jordan algorithm. Thus the merge is perfectly justified. D.Lazard (talk) 10:44, 25 August 2013 (UTC)

I know that it's result of Gauss Jordan algorithm but putting it under any topic make it loose it's independent identity.We got it as result but initials are different.As if i misinterpreted it for rank sorry for that. — Preceding unsigned comment added by Praveen.ujjain (talk • contribs) 15:22, 25 August 2013 (UTC)

Iterative methods

The article says: "This algorithm can be used on a computer for systems with thousands of equations and unknowns. However, the cost becomes prohibitive for systems with millions of equations. These large systems are generally solved using iterative methods." That link to iterative methods isn't very specific. Can we get a reference about using iterative methods (or a better link)? RJFJR (talk) 01:12, 11 February 2014 (UTC)

Link to Java Applet leads is dangerous

Plese, someone fix that — Preceding unsigned comment added by 200.129.202.130 (talk) 19:30, 10 April 2014 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Gaussian elimination/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

There needs to be an article somewhere that explores how influential the efficient solution of linear equations has been. This may be it. Geometry guy 19:51, 10 June 2007 (UTC)

Last edited at 19:51, 10 June 2007 (UTC). Substituted at 02:08, 5 May 2016 (UTC)

On the exponential bit string complexity?

The article states that the bit complexity is exponential, based on cited paper [9], i.e., "On the worst-case complexity of integer Gaussian elimination" by Fang and Havas (pdf). After looking over this paper, I realized their Gauss elimination pseudo-code is not very similar to the one provided in the article. Instead of multiplying the pivot row for iteration $k$ by $A[i,k]/A[k,k]$ like in the article, they use something like $A[i,k]$ DIV $A[k,k]$, using modulo arithmetics. After subtracting this multiplied by row $k$ from row $i$, the value $A[i,k]$ does not become zero but $A[i,k]$ MOD $A[k,k]$. Next, they can change the pivot for column $k$, by searching for the row $j$ with the lowest $A[j,k]$. This $j$ can be $i$, because $A[i,k]$ MOD $A[k,k]<A[k,k]$ (using the initial $A[i,k]$).

However, I wonder what is the bit complexity for the pseudo-code from the article. I heard it is $O(n^{4})$, because the Gauss elimination process can encounter numbers stored on $O(n)$ bits. Daniel.porumbel (talk) 18:50, 27 July 2017 (UTC)

The reference may be a wrong one. The idea is that at each step (each pivot), rational fraction are added, and this generally double the size of the integers. Thus, near the end of the algorithm one has integers of exponential size. As far as I remember, Hilbert matrix is an explicit case where this exponential complexity is reached. D.Lazard (talk) 08:55, 28 July 2017 (UTC)

Thanks for the idea with the Hilbert matrix; indeed, it seems very plausible that this matrix leads to fractions of exponential size. I let you see if the article needs modification.Daniel.porumbel (talk) 17:13, 29 August 2017 (UTC)

Pseudocode only handles invertible matrices

It's easy to modify to handle arbitrary matrices. If everything in col k below row k is 0, try the col to the right and continue pivoting. I haven't found a pseudo-code reference for this but I'm confident it's correct in theory. If anyone can find a reference and update the page I'd be grateful. Here is an example:

       1 0 0 0
row k  * * 1 0
       * * * 1
      col l^

Wqwt (talk) 18:48, 13 March 2018 (UTC)

You are right. But it is not so easy, because, in the case singular matrices you must have two different variables, one for the pivot row and the other for the pivot column (here, both are called k). Moreover, the stopping test is when one of these two variables reaches its maximum, that is, a "for" loop cannot be used; a "while" or "repeat" loop must be used instead. D.Lazard (talk) 20:54, 13 March 2018 (UTC)

 Fixed. I have fixed the code (and the surrounding text) D.Lazard (talk) 15:15, 14 March 2018 (UTC)

I appreciate the effort. I wish it could be cited authoritatively. (I wouldn't be surprised if it's in TAOCP) All I can find are papers that introduce more complex methods or slides from universities (potentially of interest: almost 700 slides? http://www.pitt.edu/~trenchea/MATH1080/MATH1080.pdf) Wqwt (talk) 05:21, 17 March 2018 (UTC)

Complexity of tensor rank

In the Generalizations sections, there is this quote: "Computing the rank of a tensor of order greater than 2 is NP-hard.[12] Therefore, there cannot be a polynomial time analog of Gaussian elimination for higher-order tensors (matrices are array representations of order-2 tensors). " The second sentence follows from the first only under the assumption P≠NP. Either that or the linked article proves something stronger than stated (i.e., proves that this problem is strictly harder than NP). The best ideals are radical (talk) 19:35, 5 November 2019 (UTC)

 Fixed. D.Lazard (talk) 20:54, 5 November 2019 (UTC)

Clarity

@D.Lazard: I know multiplying one row with -1 and then adding it to another is the same as subtraction. The objective is to make things as clear as possible to the novice. Hope you have no objection to including an explanation in brackets.--Sahir 15:08, 6 January 2022 (UTC)

Pseudocode is obscure

Pseudocode is very Python-ish and uses operator-soup Python-ish notation for ranges and loops, which makes it rather obscure. Would benefit from a more verbose and explicit version. 86.194.93.118 (talk) 21:46, 12 January 2023 (UTC)

Equations are not legible in dark or black mode in app.

Viewing this page in the iPad app with appearance set to dark or black causes the equations in the "Example of the algorithm" section to be white-on-white. SESteve (talk) 08:17, 23 March 2024 (UTC)

Linking to French Wikipedia

The French Wikipedia has an entry for fr:Élimination de Gauss-Jordan, which is linked to Gauss-Jordan elimination but not Gaussian elimination; however, the former redirects to an anchor within the latter, so AFAIK there is no way to discover the French entry without guessing that it is called Gauss-Jordan there.

I'm not sure how this should be solved, but maybe Gaussian elimination and Gauss-Jordan elimination should be unified in Wikidata, like they are unified in Wikipedia? — ncfavier 17:58, 17 April 2024 (UTC)