# Finding all solutions to Ax = b

Edit: I've rewritten this whole question because it was unclear. I'm not sure if this is any better. This is a multi-step problem using MATLAB, so I've tried to whittle it down a bit without losing anything.

Let $A$ be a random 6x6 matrix, and $b$ be a random 6x1 matrix. Since $A$ was generated randomly, we would expect it to be nonsingular. The system $Ax = b$ should have a unique solution.

Now let's change $A$ so that it is singular. Replace the third column of $A$ with a linear combination of its first two columns, namely $a_3 = 4*a_1 + 3*a_2$, where $a_1, a_2,$ and $a_3$ are first, second and third columns of $A$.

Now let $y$ be a random 6x1 matrix and let $c = Ay$.

Compute the reduced row echelon form $U$ of $[A$ $c]$.

The free variable determined by the echelon form should be $x_3$. By examining the system corresponding to the matrix $U$, you should be able to determine the solution corresponding to $x_3 = 0$. Let the column vector $w$ be this solution.

Now set the last column of $U$ to zeros. So $U$ should now correspond to the reduced row echelon form of $(A | 0)$. Use $U$ to determine the solution to the homogeneous system when the free variable $x_3 = 1$ and enter your result as vector $z$.

Set $v = w + 3 * z$. The vector $v$ should be a solution to the system $Ax = c$. Why? Explain. . . . What is the value of the free variable $x_3$ for this solution?

Here is the part I'm stuck on:

How could we determine all possible solutions to the system in terms of the vectors $w$ and $z$? Explain.

-
Not sure whether the question is complete or well expressed, since whether all solutions to $Ax=b$ are found will depend on dimensional considerations. But as a hint, you can use linearity - and so if $Ay$ also $=b$ then ... –  Mark Bennet Mar 24 '12 at 20:08
Do you know rank+nullity and nullspace basis concepts? –  user2468 Mar 24 '12 at 20:18
I've rewritten the question as it wasn't clear enough. I hope it's better. No, I'm just starting and haven't covered vector spaces yet. –  Matt Gregory Mar 24 '12 at 21:02
Since $w$ is a solution to $Ay = c,$ and $z$ is a solution to $Ax = 0,$ we have: $$\begin{eqnarray} Aw & = & c, \\ Az & = & 0 \end{eqnarray}$$ We can deduce that $$\begin{eqnarray} A(3z) & = & 0, \\ A(w + 3z) & = & c + 0, \\ A v & = & c \end{eqnarray}$$ –  user2468 Mar 24 '12 at 21:16

Your reference to "the free variable" is unclear. Generally, if $A$ is a singular matrix, the solution space can have any number of dimensions. Even if it has one dimension, there is generally not one specific free variable; in the general case any variable can be regarded as "free" and the others expressed in terms of it. Thus, "with the free variable set to zero" is not a well-defined description of $w$.

For general singular $A$, it's not possible to express all solutions of the system in terms of only two vectors. However, you seem to be implicitly assuming that the solution space is one-dimensional. In that case, all solutions are of the form $w+\lambda z$ with arbitrary $\lambda$.

By the way, the fact that $v=w+3z$ is also a solution to $Ax=b$ follows from the other facts given and isn't required for the solution.

-
But how do you know that all solutions are of the form $w + \lambda z$ with arbitrary $\lambda$? That's what I want to know. What is the procedure for figuring out where the lambda goes and so forth? –  Matt Gregory Mar 24 '12 at 21:05
@Matt: See this Wikipedia section. –  joriki Mar 24 '12 at 21:28
Ok, thanks Joriki! –  Matt Gregory Mar 24 '12 at 21:38
@Matt: You're welcome! –  joriki Mar 24 '12 at 22:07

To fill out my comment above - the construction tells us that we are looking for a 1-dimensional subspace.

If $Aw=c$ and $Ay=c$ then, by linearity $A(w-y)=0$

and since we have a solution: $Az=0$, and we are dealing with a 1-dimensional subspace, $(w-y)$ must be a multiple of that solution, i.e.

$w-y=\lambda z$

As joriki has stated.

-
I guess my confusion lies in the fact that I'm trying to prove it in a more elementary manner. My book hasn't thus far mentioned the relationship between homogeneous and nonhomogeneous systems. All it has said about an m x n homogeneous system is that if n > m then at least one nontrivial solution exists, and that if A is a nonsingular matrix, then Ax = 0 has only the trivial solution. It hasn't discussed dimension or subspaces or anything. I can see that if Az = 0, then Aw + tAz = c for any constant t, but what if it were more complicated? What if we wanted some combination of 3 vectors –  Matt Gregory Mar 25 '12 at 0:06
w, x, z such that rAw + sAx + tAz = c. Then I would need some algorithm to figure out values r and s. I'm assuming x is some solution independent of w and z. I don't know, I guess I'm overthinking this. –  Matt Gregory Mar 25 '12 at 0:08