Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When someone wants to solve this system of linear equations...

$$\begin{cases} 2x+y=0 \\ 3x+y=4 \end{cases}$$

...they might use this logic:

$\begin{cases} 2x+y=0 \\ 3x+y=4 \end{cases} \iff \begin{cases} -2x-y=0 \\ 3x+y=4 \end{cases} \implies \begin{cases} -2x-y=0\\ x=4 \end{cases} \iff \begin{cases} -2(4)-y=0\\ x=4 \end{cases} \iff \begin{cases} y=-8\\ x=4 \end{cases}$

Then they might conclude that (x, y) = (4, -8) is a solution to the system.

This turns out to be correct, but the logic seems flawed to me. As I see it, all this proves is that $\forall{x,y\in\mathbb{R}}\left(\begin{cases} 2x+y=0 \\ 3x+y=4 \end{cases} \implies \begin{cases} y=-8\\ x=4 \end{cases}\right)$.

But this statement leaves open the possibility that there's no (x, y) pair in $\mathbb{R}$ that satisfies $\begin{cases} 2x+y=0 \\ 3x+y=4 \end{cases}$. What if $\begin{cases} 2x+y=0 \\ 3x+y=4 \end{cases}$ is just always false?

It seems to me that to really be sure we've solved the equation, we have to plug back in for $x$ and $y$. I'm not talking about checking our work for simple mistakes. This seems like a matter of logical necessity.

But of course, most people don't bother to plug back in, and it never seems to backfire on them. So why does no one plug back in?

P.S. It would be great if I could understand this for systems of 2 variables, but I would be deeply thrilled to understand it for systems of $n$ variables. I'm starting to use Gaussian elimination on big systems in my linear algebra class, where intuition is weaker and calculations are more complex, and still no one feels the need to plug back in.

share|cite|improve this question
1  
something that may be interesting to note is that, when solving large systems of linear equations on a computer (with finite precision), you may get the case that $A.\vec{x}-\vec{b} \neq \vec{0}$ – costrom 16 hours ago
3  
When solving if the system of equations doesn't have a simultaneous solution you'll get a contradictory statement. You'll end up with something like 0=1. – Dason 15 hours ago
1  
I've re-read this question 10 times trying to understand what this question means and why is it that reputed users have taken this question seriously and provided serious answers. I give up. – Sridhar 12 hours ago
1  
@Sridhar one possibility is that the questioner remembers from an earlier class that certain mathematical processes introduce extraneous solutions that must be tested. For example, solving sqrt(x + 1) + 3 = 2x by squaring both sides. It is easy for someone to just get into their head "you have to check your solutions, because your method, even though correctly applied, may give extraneous ones". (See the discussion of that equation here: mathforum.org/library/drmath/view/74783.html ) – msouth 9 hours ago
up vote 47 down vote accepted

You wrote this step as an implication:

$$\begin{cases} -2x-y=0 \\ 3x+y=4 \end{cases} \implies \begin{cases} -2x-y=0\\ x=4 \end{cases}$$

But it is in fact an equivalence:

$$\begin{cases} -2x-y=0 \\ 3x+y=4 \end{cases} \iff \begin{cases} -2x-y=0\\ x=4 \end{cases}$$

Then you have equivalences end-to-end and, as long as all steps are equivalences, you proved that the initial equations are equivalent to the end solutions, so you don't need to "plug back" and verify. Of course, carefulness is required to ensure that every step is in fact reversible.

share|cite|improve this answer

The key is that in solving this system of equations (or with row-reduction in general), every step is reversible. Following the steps forward, we see that if $x$ and $y$ satisfy the equations, then $x = 4$ and $y = -8$. That is, we conclude that $(4,-8)$ is the only possible solution, assuming a solution exists. Conversely, we can follow the arrows in the other direction to find that if $x = 4$ and $y = -8$, then the equations hold.

Take a second to confirm that those $\iff$'s aren't really $\implies$'s.

Compare this to a situation where the steps aren't reversible. For example: $$ \sqrt{x^2 - 3} = -1 \implies x^2 -3 = 1 \iff x^2 = 4 \iff x = \pm 2 $$ You'll notice that "squaring both sides" isn't reversible, so we can't automatically deduce that $\pm 2$ solve the orginal equation (and in fact, there is no solution).

share|cite|improve this answer
3  
It would help if you clarified: which step feels "non-reversible", and why? – Omnomnomnom yesterday
1  
The one I wrote with the forward arrow instead of the double arrow, but now that you and @dxiv have called me on it, I see my mistake. – user404789 yesterday
1  
It had originally felt non-reversible to me because taking A=B and C=D and producing A+C = B+D is non-reversible, but I'm seeing that there's more to it. – user404789 yesterday
7  
To see that it is reversible: note that if we start from the right, we have $$ \begin{cases} A=B\\ C=D \end{cases} \implies \begin{cases} A=B\\ C-A=D-B \end{cases} $$ – Omnomnomnom yesterday
4  
I actually just wrote something almost identical on my notepad! Yes, I see it now. The key is that the A = B sticks around after A + C = B + D is produced, and you can use it to get back to C = D. – user404789 yesterday

Elementary row operations do preserve the solution set. We start with $2x+y=0$ and $3x+y=4$

enter image description here

Subtracting the 1st equation from the 2nd, and keeping the 1st equation in the system, we obtain

enter image description here

Thinking pictorially, we took the line defined by $3x+y=4$ and then sheared it until it was parallel to the $y$-axis. We conclude that $x = 4$. Subtracting $x = 4$ twice from the equation $2x+y=0$, we conclude that $y=-8$

enter image description here

We took the line defined by $2x+y=0$ and then sheared it until it was parallel to the $x$-axis. We conclude that $y=-8$. The solution has been found. Though the lines have been subjected to shearing, the point at which they intersect has been preserved.

share|cite|improve this answer
3  
It's not so simple as rotations because when you add a multiple of one equation to another you will never rotate the hyperplane described by the first such that it coincides with the hyperplane described by the second, unless they were already identical. I believe it's a shear but I didn't try to prove it. – user21820 yesterday
1  
I really like this visual approach. It helps to see what's going on behind the algebra. – Harnoor Lal 19 hours ago
    
@user21820 That is correct: shear matrix. I will update my answer. – Rodrigo de Azevedo 11 hours ago
    
@RodrigodeAzevedo: It's true that the elementary matrix is a shear matrix, but that does not obviously imply that the hyperplane defined by the equation that is being added to is sheared parallel to the hyperplane for the equation that is added. At least, I don't see an obvious link. Do you? – user21820 2 hours ago

dxiv has already answered your question for your specific example. But if you want to know the general case, when doing Gaussian elimination you have three kinds of basic steps:

  1. Rearrange equations: Clearly reversible.

  2. Multiply (both sides of) an equation by a non-zero constant: Clearly reversible because of "non-zero".

  3. Add any multiple of one equation to another: On a little reflection it is reversible too, since the operation can be easily undone by subtracting that same multiple of the first equation from the second.

This suffices to show that every step is reversible, and hence the system of equations has exactly the same solution-set after any sequence of basic steps. In fact, this is why you can sort of 'read off' the solution from the RREF of the original augmented matrix that represents the system of equations, because each basic step corresponds to left-multiplying the augmented matrix by an elementary matrix (which is invertible).

share|cite|improve this answer
    
Step 3 is only reversible if the resulting equation isn't a tautology. – Kyle Strand 12 hours ago
3  
@KyleStrand Step 3 is surely reversible: the key is using two different equations (by their position, not by their form). – egreg 11 hours ago
1  
@egreg I understood what user21820 meant, but I was thinking that if the original system of equations were not linearly independent, you'd lose information somehow. But of course you're right: since the addend is unchanged, it can simply be subtracted from the tautology. – Kyle Strand 11 hours ago
    
@KyleStrand: Indeed as egreg said. The key is that the information in the original system is equivalent to the information in the transformed system, and any dependence in the original will also be present in the final. The nature of the solution-set (no solution or unique solution or infinitely many solutions with $k$ independent parameters) can hence be read off the final RREF. – user21820 5 hours ago

All of the elementary/college textbooks I've seen do recommend checking solutions at the end by substitution. However, it's not strictly necessary because (as other answers point out) all of the steps involved are logical equivalences.

You should be aware of what the algebra looks like, for a system of two equations in two variables, when you're not in the situation of having exactly one solution to the system (i.e., an independent system). In these cases, when you add the equations together (your second step), both variables will be eliminated. In the case of a dependent system (infinite solutions), you will get an identity, e.g., 0 = 0. In the case of an inconsistent system (no solutions), you get a contradiction, e.g., 0 = 1.

For examples of this, consider OpenStax College Algebra Section 7.1.

share|cite|improve this answer
2  
Thanks for bringing this up! Each step being an equivalence, on top of answering my question, also explains why reaching "0=0" guarantees an infinite number of solutions. That was something that used to bother me as well. – user404789 16 hours ago
1  
@user404789: This post is seriously misleading if not wrong. Consider the system of equations $\{ x=0 ; -x=0 ; x+y=3; x-y=1 \}$. Adding the first two gives $0=0$ but there are no solutions. – user21820 5 hours ago
    
Added "for a system of two equations in two variables". – Daniel R. Collins 4 hours ago
    
@DanielR.Collins: Okay thanks for fixing! Personally I think one should focus on the structure of the RREF as the way to analyze solution-set types, since the behaviour is not so simple for systems of many equations. – user21820 3 hours ago

Another point of view. Gaussian elimination of a system of linear equations is equivalent to multiplication by certain types of elementary matrices. To avoid getting bogged down I will give specific examples and get you to look up more general cases if you find it of interest.

There are three basic types of row operation.

Add a multiple of an equation to another equation, say, $3$ times equation 1 to equation 2. For example $$\eqalign{x+2y&=3\cr4x-5y&=6\cr}\quad\longrightarrow\quad \eqalign{x+2y&=3\cr7x+\phantom{1}y&=15\cr}$$ This corresponds to multiplying the (augmented) coefficient by a certain matrix, $$\pmatrix{1&2&3\cr4&-5&6\cr}\quad\longrightarrow\quad \pmatrix{1&0\cr3&1\cr}\pmatrix{1&2&3\cr4&-5&6\cr} =\pmatrix{1&2&3\cr7&1&15\cr}$$


Multiply an equation by a non-zero constant, say, the first row by $-2$. For example, $$\eqalign{x+2y&=3\cr4x-5y&=6\cr}\quad\longrightarrow\quad \eqalign{-2x-4y&=-6\cr4x-5y&=6\cr}$$ corresponds to $$\pmatrix{1&2&3\cr4&-5&6\cr}\quad\longrightarrow\quad \pmatrix{-2&0\cr0&1\cr}\pmatrix{1&2&3\cr4&-5&6\cr} =\pmatrix{-2&-4&-6\cr4&-5&6\cr}$$
Finally, interchange two equations: $$\eqalign{x+2y&=3\cr4x-5y&=6\cr}\quad\longrightarrow\quad \eqalign{4x-5y&=6\cr x+2y&=3\cr}$$ which corresponds to $$\pmatrix{1&2&3\cr4&-5&6\cr}\quad\longrightarrow\quad \pmatrix{0&1\cr1&0\cr}\pmatrix{1&2&3\cr4&-5&6\cr} =\pmatrix{4&-5&6\cr1&2&3\cr}\ .$$

And now the point: all three classes of multiplying matrices are invertible, and their inverses are matrices of the same types. This means you can automatically get from your final equations back to the original, and checking solutions is not necessary.

However, while this works for linear equations, it does not in general work for other types of equations. Your practice of checking solutions is absolutely correct and very important - please don't stop doing it!!

share|cite|improve this answer
    
Thanks for writing out an example that illustrates the last paragraph of my answer, and for emphasizing that we cannot in general reverse algebraic manipulations! =) – user21820 4 hours ago

It's not hard to see that there is a solution; Notice that the equations are linearly independent. We only have three cases: either the lines are on top of each other, are parallel but a constant vertical distance apart, or cross each other at some point. Linear independence let's us know we are not dealing with case $1$ and we can just as easily plug in points to check case $2$, so only case $3$ is left. We could also just solve for $y$ and remember some basic algebra.

share|cite|improve this answer

In my research I work with very large systems of linear equations. On the rare occasions that I have to work out a small system of equations by hand, I absolutely plug them in to check their correctness. Mistakes by hand are easy. When I am using a computer to handle the matrices that represent these equations, I generally trust that the computer did it correctly. I have other checks on my answers other than plugging them back in.

The second part of your question was, how do we know that the solution is unique? How do we know that there aren't other correct answers? We know this because they are linear equations. Two non-parallel lines intersect at a point. A line and a parabola can intersect at a point, two points, or not at all. This isn't a formal proof, but it should give you an idea.

To generalize this to multiple dimensions, a single linear equation in n dimensions describes a sub-space with dimension n-1. For the 3-d case, this is a 2-d plane inside that 3-d space. The solution to that system is the space where every equation intersects. The intersection of 2 spaces that have dimension n-1, has dimension n-2. For our 3-d example the intersection of two planes is a line (dimension 1). If you have n unknowns, you know that you need n equations in order to have a unique solution. This can be explained by the fact that each equation reduces the dimension of the solution set (the number of variables), by one. When the dimension of the solution set is zero, the solution set is a point. Points are a unique solution.

I hope this helps, I have a odd way of thinking about linear algebra that confuses some of my colleagues.

share|cite|improve this answer
    
A little unrelated, but this is helpful I guess... – pie314271 17 hours ago

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.