Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
I'm not sure if this answers your question : 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 en.wikipedia.org/wiki/Permutation_matrix –  Inquest Feb 14 '12 at 16:39
    
@Nuxonic, thanks, I know of the pivoting method(s?) existence, though have not yet looked at it. –  mlvljr Feb 14 '12 at 16:42
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) –  Inquest Feb 14 '12 at 16:47

1 Answer 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$.)

share|improve this answer
    
Ok, do we never loose solutions utilizing the divid-by-possibly-zero-and-check-later method? –  mlvljr Feb 14 '12 at 16:40
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). –  Arturo Magidin Feb 14 '12 at 16:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.