16
$\begingroup$

How would you go about proving that for any system of linear equations (whether all are homogenous or not) can only have either (if this is true):

  • One solution
  • Infinitely many solutions
  • No solutions

I found this a bit difficult to prove (even though its a very fundamental thing about any linear equation). The intuitive geometric explanation is that a line can only intersect at one point, and if it intersects at a later point, it can't be a linear equation, but I don't think this is a convincing proof.

I thought of if you assume that there are two (or more, but I picked two) solutions for some linear system, then for the points in between

Solution Set 1: X1, X2....., Xn
Solution Set 2: X1, X2....., Xn

Then (I think), the points between S1 and S2, must be infinitely many points (and thus infinitely many solutions) such that these points can also satisfy the linear system, which would mean the system has 2 infinite solutions.

However, I don't think this is rigorous enough and nor do I understand completely why its true. Can anyone help in explaining (correcting) and elaborating on the intuition and proof of this?

$\endgroup$
  • 6
    $\begingroup$ "Infinite solutions" is quite incorrect. It can have infinitely many solutions. But in correct use of mathematical terminology, "infinite solutions" means solutions, each one of which is infinite. If you have six solutions, and each is infinite, then those are infinite solutions but not infinitely many solutions. ${}\qquad{}$ $\endgroup$ – Michael Hardy Sep 16 '15 at 22:09
  • 1
    $\begingroup$ Why do you find the visual proof not convincing? $\endgroup$ – corsiKa Sep 16 '15 at 22:53
  • 4
    $\begingroup$ It's worth pointing out that this question has an implicit assumption that the underlying field is infinite. Over a finite field, the assertion is not necessarily true (and we cannot have infinitely many solutions). E.g. over $GF(2)$, the equation $\pmatrix{1&1\\ 0&0}x=0$ has exactly two solutions $x=\pmatrix{0\\ 0}$ and $x=\pmatrix{1\\ 1}$. See also 6005's answer below. $\endgroup$ – user1551 Sep 17 '15 at 11:35
16
$\begingroup$

Suppose that $\vec v$ and $\vec w$ are distinct solutions for the system $A\vec x = \vec b$ so that $A \vec v = A \vec w = \vec b$. Then $\frac{1}{2}(\vec v + \vec w)$ must be distinct from both $\vec v$ and $\vec w$ and must also solve the system since: $$ A(\tfrac{1}{2}(\vec v + \vec w)) = \tfrac{1}{2}(A\vec v + A\vec w) = \tfrac{1}{2}(\vec b + \vec b) = \vec b $$ We can then apply the same argument to $\vec v$ and $\frac{1}{2}(\vec v + \vec w)$ in order to get infinitely many distinct solutions.

$\endgroup$
  • 5
    $\begingroup$ Or pick any $\lambda \in (0,1)$ and consider $\lambda \vec{v} + (1 - \lambda) \vec{w}$. Then you get continuum-many solutions right off the bat. $\endgroup$ – 6005 Sep 16 '15 at 22:10
  • 1
    $\begingroup$ You can even choose any real number for $\lambda$. $\endgroup$ – Aurey Sep 16 '15 at 23:30
  • $\begingroup$ Looking over this again, great way of explaining your argument (deriving infinitely many solutions) $\endgroup$ – q.Then Sep 17 '15 at 22:29
14
$\begingroup$

Your second proof sounds fine. Let's imagine that the system of equations is written as $Ax = b$, where $A$ is the matrix of coefficients, $x$ is the vector of variables we are solving for, and $b$ are the constants. Now assume we have two distinct solutions $x_1$ and $x_2$. Then $rx_1+sx_2$ is also a solution, if $r+s=1$ - just plug it in and use linearity of matrix multiplication.

$$A(rx_1+sx_2) = A(rx_1)+A(sx_2) = rA(x_1)+sA(x_2) = (r+s)b = b$$

We thus have an infinite number of solutions. If you don't like matrices, you can easily just write out each term in the system of equations.

If you want to get some intuition for what is happening, the linear combination $rx_1+sx_2$, where $r+s=1$, is a line that connects the two points. When $r$ is 1 and $s$ is 0, we get point $x_1$. When $s$ is 1 and $r$ is 0, we get point $x_2$. Other combinations of $r$ and $s$ give other points.

You need to be more careful with your first argument, though. In general, when graphing systems of $n$ equations in $n$ unknowns, the equations are not lines, but $(n-1)$-dimensional planes in $n$-dimensional space. So for a system of three equations and three unknowns, for example, we have three planes in three dimensional space. Unless the planes are parallel, the intersection of two planes is a line, and the intersection of a line with a plane is a point. That's the one solution case. If two planes are parallel, they never intersect - no solutions. And finally, if the line/plane overlaps with another line/plane, we get an infinite number of solutions. That's the intuition behind this theorem.

$\endgroup$
  • $\begingroup$ Thanks for the answer, I'm sure other answers were great as well, but I think you explained it the best (at least the best for me) $\endgroup$ – q.Then Sep 17 '15 at 2:55
12
$\begingroup$

We can represent a linear system in matrix notation as:$A\vec x=\vec v$. Now suppose that we have $A\vec x=\vec v$ and $A\vec y=\vec v$ with $\vec x \ne \vec y$, for $a,b$ with $a+b=1$ we have, by linearity: $A(a\vec x + b\vec y)=aA\vec x +b A \vec y=\vec v$, so we have infinitely many solutions.

$\endgroup$
7
$\begingroup$

In general, in a vector space over a general field $F$, the number of solutions $\vec{x}$ to the system $$ A \vec{x} = \vec{w} $$ is either $0$ or $|\ker A|$. (Because if $\vec{x}_0$ satisfies the equation, then the set of solutions is $\vec{x}_0 + \ker A$.) And $|\ker A| = |F|^k$ for some $k \ge 0$.

Assuming the base field $F$ has infinite cardinality $\alpha$ and the vector space is finite-dimensional, it follows that the number of solutions is $0, 1,$ or $\alpha$ (since $|F|^0 = 1$ and $|F|^k = \alpha$ for $k \ge 1$).

$\endgroup$
  • $\begingroup$ @user1551 yes, thank you. I corrected that and two other minor typos. $\endgroup$ – 6005 Sep 17 '15 at 15:20

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.