I'm trying to describe an algorithm for solving solvable linear systems. The Gaussian elimination is pretty straightforward in terms of adding multiples of rows. However, consider the following example:
$$\left\{ \begin{array}{rcl} 2x-3y+4z-5t = 1 \\ 4x-6y+5z+1t = 3 \\ 1x+3y-2z+2t = 2 \\ 7x-1y+3z-5t = 10 \end{array} \right.$$
The straightforward algorithm will transform the second row into:
$$ 0x-0y-3z-9t = 1 $$
which will mislead the rest of the execution.
A simple swap between the second and third rows would solve that. That happens because $ 4/2 = -6/-3 $, thus the second row is not well placed. In algorithmic terms, the first solution that crossed my mind was:
Let $A[i][j]$ denote the coefficient at the ith row, jth column.
- The pivot of the ith row is $A[i][i]$
- The element $A[j][i], j > i,$ will be turned into zero based on the $A[j][i]/A[i][i]$ ratio
- This will lead to a correct result if, and only if, the ratio $A[j][i+1] / A[i][i+1] $ is different from the previous ratio
- Therefore, for each row j and each column k, I must check if $A[j][k] / A[k][k] = A[j][k+1] / A[k][k+1] $ and, then, swap rows properly
It looks bad and expensive. Is there a smarter way of doing it?
Thanks in advance
----- EDIT
I'm not sure if the check can be done on-the-fly. Consider a matrix, that in the last step, looks like:
$$\left\{ \begin{array}{rcl} ... \\ 0x + 0y + 0z + 0a + 0b + 1c + 4d = 3 \\ 0x + 0y + 0z + 0a + 0b + 2c + 8d = 5 \end{array} \right.$$...
The last variable will not produce the correct result. I may be saying something inaccurate though