6

I have a question and a proposed solution - Please tell me if I'm correct.

Problem: Prove that if $A$ and $B$ are real matrices and the system of equations $AX=B$ has more than one solution, then it has infinitely many.

Solution: Assume that the system of equations $AX=B$ has more than one solution. This means that the reduced row echelon matrix form of the solution to the equation $AX=B$ has at least one free variable, because if all of the variables were pivot variables, then we would be left with a set of unique values for the variables and hence one solution. Therefore, with at least one free variable, we have that the variable(s) can vary over the real numbers. Hence, there are infinitely many solutions.

Thank you!

Seirios
  • 33,157
  • Your argument is correct, but out of curiosity, do you know the general form of an arbitrary solution of $AX = B$, given a known solution $X_0$? Because that formula will give you a much more transparent proof of this fact. – Branimir Ćaćić Jul 19 '13 at 12:18
  • I don't think so, but is it that a linear equation can have either no solution, one solution, or infinitely many solutions? –  Jul 19 '13 at 12:20
  • 8
    The nicer way is that if $u$ and $v$ are solutions then so is $u+t(u-v)$ for any real $t$. – Gerry Myerson Jul 19 '13 at 12:23

2 Answers2

3

Another, more abstract way, to see it is this: suppose the system has at least two distinct solutions. Then there exist $X_1$ and $X_2$ such that $AX_1 = AX_2 = B$ with $X_1 \ne X_2$. Thus $A(X_1 - X_2) = 0$, while $X_1 - X_2 \ne 0$. Let $C$ be the set of non-vanishing columns of $X_1 - X_2$. $C \ne \phi$ since $X_1 - X_2 \ne 0$. Let $D$ be any matrix formed by selecting its columns from $span(C)$. Then $AD = 0$, so $A(X_1 + D) = AX_1 + AD = AX_1 = B$; but clearly the number of such matrices $D$ is infinite, whence the number of matrices $X_1 + D$ is infinite as well. QED and Cheers.

Robert Lewis
  • 71,180
2

The "infinitely many" comes from the fact that there are infinitely many scalars (presumably, as you are probably working over the real or complex numbers; if you consider the possibility of working over a finite field, then the result is obviously not true). You can see this without playing with columns and echelon forms, as follows.

Let $x_0,x_1$ be two different solutions: $Ax_0=B=Ax_1$. Then putting $x_\lambda=\lambda x_1+(1-\lambda)x_0$ one has by linearity $Ax_\lambda=\lambda Ax_1+(1-\lambda)Ax_0=\lambda B+(1-\lambda)B=B$, so $x_\lambda$ is a solution as well, and there are infinitely many choices for $\lambda$. And these are all different, since $x_\lambda=x_\mu$ implies $0=x_\lambda-x_\mu=(\lambda-\mu)(x_1-x_0)$, which given that $x_0\neq x_1$ can only hold if $\lambda-\mu$.

Marc van Leeuwen
  • 115,048