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
    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

1

One method would be to keep track of every division, and then check the final result to see if any of those "special cases" can be subsumed in the final form. Here, you would make a note that the first step requires $a\neq 0$; the second step further requires $ad\neq bc$. Then check that the final step still requires $ad\neq bc$, but the condition $a\neq 0$ is no longer required (in that the formula gives the correct answer in that situation, provided $bc\neq 0$).

(Something similar happens when you do differential equations; in solving y'=y, one method is to divide by $y$ to separate and then integrate; this can only be done if $y\neq 0$. Then you obtain the general solution $y=Ae^x$, $A\neq 0$, and then note that the case $y=0$ can be subsumed by dropping the requirement that $A\neq 0$.)

  • 1
    @mlvljr: First, keep track of your assumptions in the division. Then, check which ones can be subsumed in the general solution. *Finally*, deal with the cases that are left. In this case, you should re-start with the assumption that $ad=bc$, and see what can be said in that case. (HINT: there *will* be solutions, *sometimes*, in that situation; specifically, there will be a solution if and only if one equation is proportional to the other, in which case there will be infinitely many solutions).2012-02-14