# Why Gaussian Elimination only works over field?

When I was solving system of linear congruences (n variables, n equations), like this:

$AX \equiv b \pmod p$

I was told that ordinary Gaussian Elimination works if $p$ is prime. And I figured out that when $p$ is prime, integers $\pmod p$ form a field, otherwise it doesn't form a field, but a ring.

Here comes my problem, why Gaussian Elimination does not work over a ring? AFAIK, the difference between a ring and a field, is that elements in a field are multiplicatively invertible, but does it have something to do with the applicability of Gaussian Elimination? If yes, how?

You need to be able to invert the element on the main diagonal (as long as it is non-zero). If $p$ is not prime, you may not be able to do this. For example, let $p=6$, then $2,3$ have no inverse. So try $$\begin {pmatrix} 2&0\\0&3 \end {pmatrix}\begin {pmatrix} X_1 \\ X_2 \end {pmatrix}=\begin {pmatrix} 1 \\ 1 \end {pmatrix}\pmod 6$$
If you complain that the Gaussian elimination is done, change the $0$'s to $1$'s. If $p$ is prime you are guaranteed an inverse of any non-zero element and the equation will be soluble. Do it $\pmod 7$ and you will succeed.

• Upvoted for the concrete illustration, but what do you mean by change the 0's to 1's ? Commented Jun 8, 2013 at 3:24
• @loganecolss: I was worried you might complain about the zeros in the matrix, but the same problem occurs with $\begin {pmatrix} 2&1\\1&3 \end {pmatrix}$ unless you pivot. Commented Jun 8, 2013 at 3:29
• If $p$ is prime, then I can just simply apply row-operations to turn the matrix into upper-tri form, then solve it by finding out the inverse of non-zero element, right? Commented Jun 8, 2013 at 3:49
• @loganecolss: that is correct. The problem if $p$ is not prime is that there are elements of the ring that do not have inverses. The usual Gaussian elimination multiplies the row in question by the inverse of the diagonal element to make $1$. If there is no inverse, this fails. This is true in $\Bbb Z$ as well, and rings were motivated by the integers. There is no $\frac 12$ in the integers, so you can't solve my example in $\Bbb Z$. Commented Jun 8, 2013 at 4:18

To ensure that the solution set is preserved, the row operations should be reversible. In a ring, the following operations are reversible:

1. interchange two rows;
2. add a multiple of one row to another row;
3. multiply a row by a unit, that is, by an invertible element of the ring.

In a PID these suffice to put the matrix in row echelon form, but it is not always possible to put the matrix in reduced row echelon form since it is not always possible to obtain $1$ as a leading coefficient. In particular, if a leading coefficient is not invertible, then one cannot obtain $1$ as a leading coefficient. In a field, of course, all non-zero elements are invertible.

Example: Reduce the matrix $$\begin{bmatrix}6 & 3\\ 4 & 8\end{bmatrix}$$ modulo $10.$

We subtract row $2$ from row $1$ to obtain $$\begin{bmatrix}2 & 5\\ 4 & 2\end{bmatrix},$$ and then subtract twice row $1$ from row $2$ to obtain $$\begin{bmatrix}2 & 5\\ 0 & 2\end{bmatrix}.$$ In general, one may have to repeat several times, Euclidean-algorithm style, until all but one element in the first column is $0$. There's not much more we can do at this point. We can reduce the size of the element $5$ as much as possible by subtracting twice row $2$ from row $1$ to obtain $$\begin{bmatrix}2 & 1\\ 0 & 2\end{bmatrix}.$$

One also needs to worry about the right side of the equation. If the reduced equation is $$\begin{bmatrix}2 & 1\\ 0 & 2\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix}=\begin{bmatrix}a\\ b\end{bmatrix}$$ then there is no solution if $b$ is odd. If $b$ is even, then there are two solutions. For example, if $(a,b)=(5,6)$ then the solutions are $(x,y)\in\{(1,3),(6,3)\}.$

Another example: Reduce the matrix $$\left[\begin{array}{cc|c}5 & 3 & 8\\ 10 & 4 & 6\end{array}\right]$$ modulo $12.$ Subtract twice row $1$ from row $2:$ $$\left[\begin{array}{cc|c}5 & 3 & 8\\ 0 & 10 & 2\end{array}\right].$$ Multiply row $1$ by the multiplicative inverse of $5,$ which is $5:$ $$\left[\begin{array}{cc|c}1 & 3 & 4\\ 0 & 10 & 2\end{array}\right].$$ Again there's not a lot we can do from here. We are free to multiply row $2$ by an invertible element, such as $5,$ as well. This is useful since it reduces the size of the coefficient: $$\left[\begin{array}{cc|c}1 & 3 & 4\\ 0 & 2 & 10\end{array}\right].$$ We can now subtract row $2$ from row $1$ to reduce the size of the element $3:$ $$\left[\begin{array}{cc|c}1 & 1 & 6\\ 0 & 2 & 10\end{array}\right].$$ There are two solutions: $$\begin{bmatrix}1\\ 5\end{bmatrix},\quad\begin{bmatrix}7\\ 11\end{bmatrix}.$$

There is a form of Gaussian elimination which works over a PID which is described in this article. The normal form you get from this algorithm (Smith normal form) consists of only diagonal entries which divide successively and is useful for getting information about the structure of f.g. modules over a PID.

• It should be pointed out that to obtain the Smith normal form one must perform both row and column operations. Gaussian elimination involves row operations alone. Smith normal form is not used for solving linear systems. Commented Jun 8, 2013 at 3:20
• Right, the fact that there are non-units already prevents you from solving some linear systems in general rings, so I was just presenting this as a curiosity. Thanks for the clarification. Commented Jun 8, 2013 at 3:27
• Hermite normal form is probably closer to what one wants. The Wikipedia article describes the form that results from performing column operations. One can transpose the description to get the form that would be obtained using row operations. The resulting matrix is lower triangular, as opposed to row echelon form, which is upper triangular, but this difference is immaterial. Commented Jun 8, 2013 at 3:58