# Gaussian Elimination

Does a simple Gaussian elimination works on all matrices? Or is there cases where it doesn't work?

My guess is yes, it works on all kinds of matrices, but somehow I remember my teacher points out that it doesn't works on all matrices. But I'm not sure, because I have been given alot of methods, and maybe I have mixed it all up.

-
I'm not sure what counts as Gaussian elimination proper to you, but: if you don't allow swapping (a.k.a. pivoting), then yes, there are matrices on which it fails. If you do, then as long as the matrix isn't singular... –  Ｊ. Ｍ. Sep 30 '11 at 0:35
Maybe he meant that Gaussian elimination fails over arbitrary commutative rings (like the integers) instead of a field. –  darij grinberg Sep 30 '11 at 2:56

When I hear the phrase 'Gaussian Elimination,' I think of elementary row operations to solve some sort of linear system of equations. And when I think of when it 'does' or 'doesn't' work, two things come to mind. You either mean that the resulting system is solveable, or you mean that somehow the row operations will somehow ruin the system.

So I answer both. Gaussian elimination will never turn a solveable system into something unsolveable. It will also not change the solutions to any system. That's pretty magnificent, and not immediately obvious (at least, it wasn't to me when I first learned it - it was a bit like magic).

But some systems are underdetermined, unsolveable, or uniquely solveable. And Gaussian elimination doesn't change those, either. So there are systems where Gaussian elimination will not produce a unique answer. And in general, one must be a bit witty to classify an infinitude (which my spell-checker thinks is a real word - cool) of answers (usually involving kernels or images or parameterization or something along those lines).

So really, the only great thing about Gaussian Elimination is that it is highly algorithmic and doesn't really change anything about the system itself.

-

Gaussian elimination without pivoting works only for matrices all whose leading principal minors are non-zero. See http://en.wikipedia.org/wiki/LU_decomposition#Existence_and_uniqueness.

-
I'd change "positive" to nonsingular myself; take a gander at $$\begin{pmatrix}-1&0&-1\\0&1&2\\-1&2&-1\end{pmatrix}=\begin{pmatrix}1&0&0\\0&1&0\\1‌​&2&1\end{pmatrix}\cdot\begin{pmatrix}-1&0&-1\\0&1&2\\0&0&-4\end{pmatrix}$$ –  Ｊ. Ｍ. Sep 30 '11 at 7:52
@J.M., thanks. I've changed it to non-zero to conform with Wikipedia, which defines minors as determinants. –  lhf Sep 30 '11 at 10:25