Is there any sufficient or necessary conditions for a matrix to do Gaussian Elimination?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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$.