3

For now I know that we can do Gaussian elimination to $ m\times n $ matrices. But is there any restrictions?

ASB
  • 3,999
Malith
  • 305
  • 3
    Gaussian elimination is something you can do to any matrix of real (or complex) entries. – Ben Grossmann Mar 09 '15 at 23:00
  • There's something analogous to Guassian elimination for matrices over any PID: http://en.wikipedia.org/wiki/Smith_normal_form – Qudit Mar 09 '15 at 23:25

3 Answers3

5

For a square matrix, Gaussian elimination will fail if the determinant is zero. For an arbitrary matrix, it will fail if any row is a linear combination of the remaining rows, although you can change the problem by eliminating such rows and do the row reduction on the remaining matrix.

Gaussian elimination with full pivoting (siwtching rows or columns so as to have the largest possible absolute value of each "pivot" element) will fail only in those circumstances. However, naive Gaussian elimination with no pivoting will sometimes fail (divide by zero)on a perfectly well-conditioned matrix.

Mark Fischler
  • 41,743
  • “Fail” in what sense? – egreg Mar 09 '15 at 23:16
  • 1
    Under these conditions, it "fails" in the sense that a computer doing it would get to a step it can't complete, but it doesn't fail in the sense that gaussian elimination will still give you all the information about the system. For example, if you have a square matrix with determinant zero, it will "fail" to give you a unique solution(because there isn't one!) Instead, it will tell you if there are infinitely many solutions or no solutions, and in the case of infinitely many solutions, it will tell you exactly how many free variables there are. – SE318 Mar 10 '15 at 13:05
1

Considering the question, it sounds like you're in an undergraduate linear algebra course, so this might go over your head a little bit, but Gaussian elimination requires multiplicative inverses, so it would not always work if the coefficients were from a ring that is not a field. Since the matrices you are probably dealing with have coefficients from $\Bbb{R}$ (or maybe $\Bbb{C}$), and $\Bbb{R}$ is a field($\Bbb{C}$ as well), it will work for all of them.

SE318
  • 503
1

Gaussian elimination with partial pivoting on a square matrix will produce a lower triangular $L$, an upper triangular $U$ and a permutation $P$ such that $PA = LU$. $A$ is singular iff $[U]_{kk} = 0$ for some $k$.

copper.hat
  • 172,524