Gaussian Elimination

Inconsistent System

Gaussian elimination on a system where the equations contradict each other. Forward elimination reduces one row to all zeros on the left but a nonzero constant on the right (0 = c). This is a contradiction: no assignment of variables satisfies it.

Example

Row-reduce until a contradiction row shows that no solution exists.

highlighted = computed this step

Step 1 — Set up

Start with the augmented matrix.

[111222251237]\left[\begin{array}{ccc|c}1&1&1&2\\2&2&2&5\\1&2&3&7\end{array}\right]

Step 2 — Update row 2

Update row 2 using row 1: r2 <- r2 - 2*r1.

[111200011237]\left[\begin{array}{ccc|c}1&1&1&2\\\hl{0}&\hl{0}&\hl{0}&\hl{1}\\1&2&3&7\end{array}\right]

Step 3 — Update row 3

Update row 3 using row 1: r3 <- r3 - r1.

[111200010125]\left[\begin{array}{ccc|c}1&1&1&2\\0&0&0&1\\\hl{0}&\hl{1}&\hl{2}&\hl{5}\end{array}\right]

Step 4 — Swap rows

Swap rows 2 and 3: r2 <-> r3.

[111201250001]\left[\begin{array}{ccc|c}1&1&1&2\\\hl{0}&\hl{1}&\hl{2}&\hl{5}\\\hl{0}&\hl{0}&\hl{0}&\hl{1}\end{array}\right]

Step 5 — Result

State the contradiction: 0 = 1, so no solution.

[111201250001],contradiction: 0=1, no solution\left[\begin{array}{ccc|c}1&1&1&2\\0&1&2&5\\0&0&0&1\end{array}\right],\quad \text{contradiction: }0=1,\ \text{no solution}
inconsistency A linear system is inconsistent if forward elimination produces a row of the form [0 0 ... 0 | c] with c nonzero. This means 0 = c, which is impossible — the system has no solution.
no-solution When a contradiction row appears, Gaussian elimination halts. There is no point continuing because no values of the variables can satisfy the contradictory equation.