3
$\begingroup$

Suppose I would like to use Gauss-Jordan method to develop (in matrix form) Cramer's rule for two equations in two unknows:

\begin{pmatrix}a & b & e\cr c & d & f\end{pmatrix}

\begin{pmatrix}1 & \frac{b}{a} & \frac{e}{a}\cr 0 & 1 & \frac{f-\frac{ce}{a}}{d-\frac{bc}{a}}\end{pmatrix}

\begin{pmatrix}1 & 0 & \frac{e}{a}-\frac{b\left( f-\frac{ce}{a}\right) }{a\left( d-\frac{bc}{a}\right) }\cr 0 & 1 & \frac{f-\frac{ce}{a}}{d-\frac{bc}{a}}\end{pmatrix}

\begin{pmatrix}1 & 0 & -\frac{bf-de}{ad-bc}\cr 0 & 1 & \frac{af-ce}{ad-bc}\end{pmatrix}

(In this example) How do I prove that the final matrix represents the correct solution when a is zero regardless of division by a in the first transformation?

I.e. (and this is the more general question):

  • how do I keep track of equations ~poisoned by possible zero division (for example, the first row of the second matrix represents an equation which clearly consitst of undefined components when a is zero)?

(Please excuse my frivolous language :)

  • 1
    I'm not sure if this answers your question : http://en.wikipedia.org/wiki/Partial_pivoting. Basically, you swap the first row with a row below the current row containing a non-zero element in the same column. (Such an element exists, else A is non-invertible). Do the same for the RHS. Keep track of this using Permutation Matrices http://en.wikipedia.org/wiki/Permutation_matrix2012-02-14
  • 0
    @Nuxonic, thanks, I know of the pivoting method(s?) existence, though have not yet looked at it.2012-02-14
  • 1
    At run time, when you realize that what you are dividing by is 0, you would try to do the swapping exercise and keep track of it (For PA=LU, if you are solving Ax=b, there is no need to keep track if you do the same operations on b). This would certainly ensure a solution. Whether you pivot for extremely small elements is a question (of coding, not of math). `Note: All of this is on the assumption that Ax=b has a unique solution.` Else, elimination CAN fail and you may end up with 0 of $\infty$ solutions. For instance [1 2;2 4] x = [3;6]. Elimination fails but there are solutions like (1,1)2012-02-14

1 Answers 1