# RowReduce on overdetermined system containing symbols

Consider this simple, overdetermined system of linear equations:

\begin{align*} 3x + y &= a\\\\ 2x + y &= b\\\\ x + y&= c \end{align*}

where $$a, b, c$$ are arbitrary constants.

On Mathematica 13.2, if I run RowReduce[{{3, 1, a}, {2, 1, b}, {1, 1, c}}]

I get the output {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}.

Now I'm the first to admit that my linear algebra is not up to par (so maybe I'm making a blunder somewhere) but it seems Mathematica thinks the system is inconsistent, without taking into account that $$a, b, c$$ might be related in a way to keep the system consistent. i.e. I would have expected an output like:

{{1, 0, a - b}, {0, 1, 3b-2a}, {0, 0, a-2b+c}}

meaning that the system does have a solution when $$a - 2b + c = 0$$.

So what's going on here?

• Similar topic on Wolfram Community Commented Jan 4, 2023 at 20:33

This is may be a duplicate of How can I prevent simplification?, but I had to adapt @CarlWoll's answer to this particular problem:

RowReduce[{{3, 1, a}, {2, 1, b}, {1, 1, c}},
ZeroTest -> (ListQ[#] && Length[#] > 0 &@Solve[# == 0] &)] //
Simplify

• Well, that solves the problem! Would you mind explaining the function you used in the zero test itself, it's been some years since I used mathematica and my brain is having trouble parsing it.
– Aky
Commented Jan 5, 2023 at 6:54
• Solve returns a solution, in the form { {VAR -> value}, ...} if a solution is possible. It returns {{}} if a full-dimensional solution set exists. It returns {} if no solution is possible. It return itself (Solve[..], not a list) if there's an error. In the first two cases, we have a List (ListQ[#] returns True) and a length > 0. In the last two cases we either don't get a List or we have a list of length 0. -- In terms of the code ListQ[#] && Length[#] > 0 & is applied to the result of Solve[..] and makes the test explained above (# = result of Solve[] here).... Commented Jan 5, 2023 at 16:36
• @Aky The # in Solve[# == 0] is the expression RowReduce[] is testing for zero. The @ between them is composition. Commented Jan 5, 2023 at 16:39

There are two cases to consider, 1) a non-zero determinant and 2) a zero determinant.

If we assume a non-zero determinant, we do

  RowReduce[{{3, 1, a},  {2, 1, b}, {1, 1, c}}] // MatrixForm


Notes: This correctly produces the identity matrix. The reason for this is that, by default, RowReduce, treats symbolic expressions as nonzero.

If we assume a zero-determinant, we do

  RowReduce[{{3, 1, a},  {2, 1, b}, {1, 1, c}} /.c -> 2 b - a] // MatrixForm


This produces what you were expecting, because we are assuming the last value in your expected result is zero.

I figured out the determinant relation from setting the determinant equal to zero from

  Det[{{3, 1, a}, {2, 1, b}, {1, 1, c}}]


To use "RowReduce" to solve linear equations you must append the RHS as an additional column to your matrix. The solution is then the rightmost column of the matrix in reduced row echelon form.

Here is an example:

Given the system of 3 linear equations:

a = {{2, 3, 5}, {-3, 4, -1}, {4, 1, -6}};
b = {-2, 7, 3};
Thread[a . {x, y, z} == b] // MatrixForm


We must append the RHS as column to the right side of a:

MatrixForm[m = Join[a, Transpose[{b}], 2]]


The rightmost column of the row reduced matrix is now the solution:

(m1 = RowReduce[m]) // MatrixForm


We can test this:

m1[[All, 4]] == {x, y, z} /. Solve[a . {x, y, z} == b]
(* True *)


Now what happens if the row are not linearly independent or if the system is over determined?

For the case where the rows are linearly depended, We replace the third row by the sum of the first and twice the second row:

m2 = m; m2[3] = m[1] + 2 m[2]; (m3 = RowReduce[m2]) // MatrixForm

The last row is all zeros. Telling us that there is no unique solution. The first 2 rows give 2 equations for 3 variable, leaving one variable free.

For an over determined system, it may have a solution or not. For the case that there exists a solution {-10,40}, consider:

m = {{3, 1, -b1}, {2, 1, -b2}, {1, 1, -b3}};
(m1 = m /. {b1 -> 10, b2 -> 20, b3 -> 30}) // MatrixForm
(m2 = RowReduce[m1]) // MatrixForm


There is no problem, we get the correct solution.

But what if the system is inconsistent? For this we change b3 from 30 to 40:

(m1 = m /. {b1 -> 10, b2 -> 20, b3 -> 40}) // MatrixForm
(m2 = RowReduce[m1]) // MatrixForm


What does this tell us? Remember that the rightmost columns are the RHS of our equation And this is means:

m2.{x,y,1}== {0,0,0}


Therefore the last row tells us 1 == 0, a contradiction. This indicates that the system has no solution.

Now hat happens if b is symbolic? Let see:

m // MatrixForm
RowReduce[m] // MatrixForm


Obviously MMA assumes that the system is inconsistent.

• I have a feeling you may have misread my question; the last column in my matrix are in fact the system constants. The reason the size of my matrix is 3x3 is because the system is overdetermined (3 equations in 2 variables)
– Aky
Commented Jan 5, 2023 at 6:51
• I added the problematic cases, Inconsistent or over determined systems Commented Jan 5, 2023 at 10:49
• I didn't really have any problem with the mathematical concept of overdetermination/inconsistency, just how to get mma not to assume it when symbols are used in the linear system. But in any case, I think your response lays out the issue clearly so might be useful to others!
– Aky
Commented Jan 5, 2023 at 11:22

We now have UpperTriangularDecomposition in the Wolfram Function Repository. It returns an upper-triangularized form and the corresponding conversion matrix. Also it attempts to avoid creating fractions.

mat = {{3, 1, a}, {2, 1, b}, {1, 1, c}};
{uu, conv} = ResourceFunction["UpperTriangularDecomposition"][mat]

(* Out[142]= {{{1, 1, c}, {0, -1, b - 2 c}, {0, 0, -a + 2 b - c}},
{{0, 0, 1}, {0, 1, -2}, {-1, 2, -1}}} *)


Check:

conv . mat == uu

(* Out[143]= True *)