10
$\begingroup$

I've studied linear algebra before, however, I wanted to come back to the foundations and understand it again from the beginning.

I was looking the following inoffensive linear equations:

$$ x - 2y = 1 $$ $$ 3x + 2y = 11 $$

and after elimination one has:

$$ x - 2y = 1 $$ $$ 8y = 8 $$

the claim is that both systems of equations have the same solution. Geometrically:

enter image description here

if you've never seen this before it nearly seems like magic! We managed to combine different equations and still retain that the solutions is preserved. The new equations seems to be completely different and the lines that we care about don't even have same gradients. Basically, at first glance, the problem seems like it dramatically changed!

So even though, the system seems to have changed a lot, in reality, it didn't change that much since they still intersect at the same point.

My question is, what is the intuition to why manipulating system of equations in this way and combining them retains the original solution.

The intuition/justification that I used to think of was that, if we combine equations, in principal, the "total" information that we had at the beginning of the system is preserved as long we are combining different equations and we don't discard one any of them. Basically, combining two equations implicitly retains the information that we had about the old equation. However, we can "forget" about the old form of the new equation because that information is preserved even though the equation changed. i.e. its ok to combine equation 1 and 2 to form 2' and discard 2, since 2' AND 1 contains all the information of the original system.

This is sort of the intuition that I use but I wasn't sure if that was a good way to think about it or if people maybe had better intuitions or justification to why elimination worked.

$\endgroup$
  • 3
    $\begingroup$ I think a basic principle at work here is adding/subtracting the same thing from both sides of the equation preserves equality $\endgroup$ – yoyostein Nov 7 '15 at 3:41
  • 2
    $\begingroup$ Your intuition that no information is lost can be made precise. The first system implies the second for the reason in yoyostein's comment. But the second system also implies the first, and for the same reason: multiplying both sides of equation 1 of the second system by 3 and adding to equation 2 of the second system gives equation 2 of the first system. $\endgroup$ – Will Orrick Nov 7 '15 at 11:26
5
$\begingroup$

I will likely be proven wrong by another answer, but I don't think that you can get a geometrical explanation. Algebraically, the situation is very clear: you have a system $Ax=b$, and when you perform row reduction, you are multiplying on the left by an invertible (elementary) matrix. So the system becomes $EAx=Eb$, with the same solution. Multiplying by an invertible matrix does not have an easy geometrical interpretation, as far as I can tell.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yup, I thought of that explanation too, but that sort of assumes I know about a more complicated system of things like matrices and linear algebra (which I do, but wanted sort of an answer independent of that, something more basic). Nevertheless, if you've never seen this point of view its still useful. Thanks for your contribution. $\endgroup$ – Pinocchio Nov 7 '15 at 16:25
  • $\begingroup$ Not sure if this takes us closer to a geometric interpretation, but I thought all matrix multiplications corresponded to a linear transformation, which on itself is a way to manipulate vectors. I would have expected that E somehow has the geometric property that even though the geometry of the problem changes since $EA$ spans a different column space, the set of solutions $x$ remains intact though. $\endgroup$ – Pinocchio Nov 2 '16 at 15:38
  • $\begingroup$ @Pinocchio It does. Invertible matrices are automorphisms of a vector space. Multiplying by a singular matrices causes you to lose information, because you lose a dimension. $\endgroup$ – Abhimanyu Pallavi Sudhir Apr 21 '19 at 12:05
3
$\begingroup$

There is only one elimination rule: if I perform an operation on two copies of the same number, both copies change in the same way.

If $x-2y=1$ then $3x-6y=3$. I have changed nothing. I have merely noticed that if I multiply $1$ by $3$ I get $3$.

If I now subtract $3x-6y=3$ from $3x+2y=11$ I am just subtracting $3$ from $11$ which gives me $8y=8$. If I now divide $8$ by $8$ I get $y=1$.

In all cases I am just doing the same thing to the same number written in two different ways.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Just to add: it is important to know that all our row operations are invertible. Performing the same operation to two copies of the same number always turns true statements to true statements, but in general it could also turn false statements into true statements, and thus non-solutions into solutions. If we multiplied both of the original equations by 0, then the original solution would still be a solution, but not every solution to the new system ($0 = 0, 0 = 0$) would be a solution to the old system. $\endgroup$ – Ravi Fernando Nov 7 '15 at 2:42
  • 1
    $\begingroup$ The usual row operations we do don't have this problem: any time you switch two equations, add a multiple of one equation to another, or scale an equation by a nonzero constant, you can undo the process and recover the original equations. So the original solution set is a subset of the new solution set and vice versa. $\endgroup$ – Ravi Fernando Nov 7 '15 at 2:42
  • $\begingroup$ @RaviFernando I think that is part of the inquisitor's confusion. I don't look at $x-2y=1$ as the set of $(x,y)$ such that the equation is true. These are just two expressions that evaluate to $1$. Therefore, anything you do to the number $1$ you are just doing to two different representations of it. Of course you choose your operations to help you solve the equation so you wouldn't multiply by $0$. $\endgroup$ – John Douma Nov 7 '15 at 2:49
3
$\begingroup$

Suppose someone gives you a pair of distinct lines in the plane, neither horizontal nor vertical, and intersecting at a point $O$. To find the Cartesian coordinates of $O$, you could rotate one line until it was horizontal, then rotate the other line until it was vertical. You could then read off the coordinates by checking where the rotated lines hit the coordinate axes.

Rotating a line to be horizontal means you've eliminated $x$ from its equation; rotating a line to be vertical means you've eliminated $y$. Perhaps the surprising thing is that elementary row operations effectively rotate lines.

To make this algebra-to-geometry dictionary more precise, write the original lines as \begin{align*} a_{1}x + b_{1}y + c_{1} &= 0, \\ a_{2}x + b_{2}y + c_{2} &= 0. \\ \end{align*} View each left-hand side as the value of a function of two variables whose graph is a plane.

Multiplying an equation by a non-zero scalar "rotates" the corresponding plane in space about its zero set, but doesn't change the zero set.

Fixing one equation and subtracting a non-zero scalar multiple of the other amounts to intersecting planes, then projecting the line of intersection to the $(x, y)$-plane; as the scalar multiple changes, (the shadow of) the line of intersection rotates about $O$. If you tilt the planes just right, the projected line of intersection is parallel to a coordinate axis.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hello there, I've been pondering your explanations a lot; but I'm still wondering why elementary row operations amount to rotating a plane; don't the points of the plane stay the same when I multiply the equations by a non-zero scalar? Thanks for sharing your intuitions :) $\endgroup$ – Mitch Baker Sep 2 '16 at 14:21
  • 1
    $\begingroup$ @MitchBaker: The idea is to think of the line $\ell$ in the plane with equation $ax + by + c = 0$ as the intersection of the planes $ax + by + c = z$ and $z = 0$ in space; multiplying the left-hand side by $k \neq 0$ gives the plane $kax + kby + kc = z$ (or $ax + by + c = z/k$), whose graph is another plane containing $\ell$, but rotated about the axis $\ell$ relative to the original plane. $\endgroup$ – Andrew D. Hwang Sep 2 '16 at 19:07
3
$\begingroup$

So even though, the system seems to have changed a lot, in reality, it didn't change that much since they still intersect at the same point.

My question is, what is the intuition to why manipulating system of equations in this way and combining them retains the original solution.

The reason that the solution space stays the same is algebraic in nature:

As shown by your images, each row defines an affine hyperplane (an affine plane of dimension $n-1$): $$ a_i^\top x = \beta_i $$ where the vector $a_i$ is a normal vector to the hyperplane.

The elementary scalings of a row does not change the points $x$ of the hyperplane, only (the length) of its normal vector, which stays normal, and the inhomogenity to compensate: \begin{align} a_i^\top x = \beta_i \iff \\ s a_i^\top x = s \beta \iff \\ {a'}_i^\top x = {\beta'}_i \end{align} Adding a multiple of a hyperplane to another gives $$ \beta_i = \alpha_i^\top x \to \quad (*) \\ \beta_i + s \beta_j = \alpha_i^\top x + s \alpha_j^\top x = (\alpha_i + s \alpha_j)^\top x \iff \\ (\beta')_i = (\alpha')_j^\top x \quad (**) $$ Stand alone this can be a new hyperplane, with a new set of points $x$. However for a $x$ of the common intersection, this means that still $\alpha_j^\top x = \beta_j$ holds, so we can again revert to the equation $(*)$ from $(**)$. So $$ \alpha_i^\top x = \beta_i \wedge \alpha_j^\top x = \beta_j $$ has the same solutions as $$ \alpha_i^\top x + s \alpha_j^\top =\beta_i + s \beta_j \wedge \alpha_j^\top x = \beta_j $$ The geometric consequence is that the hyperplanes $(*)$ and $(**)$ have the points $x$ in common, for which $\alpha_j^\top x = \beta_j$, which are at least a $n-2$ dimensional affine subspace. For $n=2$ this means staying the same or rotating around the intersection point. For $n=3$ this means staying the same or rotating around the intersection line.

OK, so we can do affine rotations without changing the solution space. However we do not do this at random, but have a strategy which allows to read the solutions from the parameters $\alpha$ and $\beta$:

The goal of elimination is to get a row echelon form. Row per row more dependencies of variables are removed.

elimination (Large Version)

In your image the $x$-dependency of your second line has been removed, it just depends on $y$, which because it is the last variable, turns out constant. It is an affine rotation.

As we now have the $y$-dependency in the second row, we could remove it from the first row, keeping only the $x$-dependency there: $$ \left[ \begin{array}{rr|r} 1 & -2 & 1 \\ 0 & 8 & 8 \end{array} \right] \to \left[ \begin{array}{rr|r} 1 & -2 & 1 \\ 0 & 1 & 1 \end{array} \right] \to \left[ \begin{array}{rr|r} 1 & 0 & 3 \\ 0 & 1 & 1 \end{array} \right] $$ The matrix is now in reduced row echelon form.

elimination2 (Large version)

We have aligned each line parallel to one of the coordinate axes. In higher dimensions similiar alignment happens. We can directly read fixed coordinates of the solutions from this form.

Further we can make statements about the dimension of the solution space:

If the row echelon form has $k$ empty rows, it is clear that the intersection of $n-k$ hyperplanes turns out not to be zero dimensional (a point, a unique solution) but is some at best only $k$ dimensional affine subspace, if all hyperplanes intersect not identical. If they do not have a common intersection, there is no solution.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I know this is an old post but I remember my excellent high school teacher giving the following intuitive explanation. $$ I $$ $$ x + y = k$$

$$ II $$ $$ x + q = p $$

$$ Combined $$ $$ x + y - ( x + q) = k -p $$

Simplifies to:

$$ y - q = k -p $$

$$ y = k - p + q $$

Insert y into the firs equation...

$$ x + (k - p + q) = k $$

...gives you the second

$$ x + q = p$$

The reasoning is as follows. If you combine two equations into one and solve for a variable which occurs in both equations and insert this in the first, you get the second. It basically states that the solution for your variable satisfies both equations...

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

A visual to supplement the answers of Andrew Hwang and mvw.

One can 'see' the transformation by subtracting the first equation 'slowly' over $0\le t\le 3$, $$\begin{matrix}3x+2y&=11\\\phantom{aaaaaaaaaaaaa} -t(x-2y)&\phantom{aaaaaa}{-t}\end{matrix}$$ $$(3-t)x+(2+2t)y=11-t$$

$\hspace{4cm}$enter image description here

The transformation is not a rotation but a shear along the other line. The point of intersection appears to act as the origin because if $\vec{x}_0$ ($=(3,1)$) is the solution of $A\vec{x}_0=\vec{b}$ then the intermediate lines satisfy $$(3-t)x+(2+2t)y=(-t,1)\begin{pmatrix}1&-2\\3&2\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}=(-t,1)\begin{pmatrix}1\\11\end{pmatrix}=11-t$$ That is, writing $v_t=(-t,1)$ and $\vec{b}=(1,11)$, $$v_t^\top A\vec{x}=v_t^\top\vec{b}\iff v_t^\top A(\vec{x}-\vec{x}_0)=0$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ why do we have $x-x_0$? I'm trying to understand your explanation of the why but can't make sense of it. $\endgroup$ – Pinocchio Aug 20 at 12:24
  • $\begingroup$ @Pinocchio $\vec{b}=A\vec{x}_0$ so if you take it to the other side, you get the last equation in which the vectors $\vec{x}=(x,y)$ are relative to $\vec{x_0}$. $\endgroup$ – Chrystomath Aug 20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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