# b such that Ax = b has no solution having found column space

$A:=\begin{bmatrix} 2 & 6 & 0 \\ 3 & 1 & 3 \\ 1 & 0 & 0 \\ 4 & 8 & 1 \end{bmatrix}$

I've found the basis for the column space by doing row reduction (i.e. basis is just the columns vectors of A in this case), and the null space only has the trivial solution.

Question

Find a basis for $B = \{b \in R^4 \ | \ Ax = b \ has \ no\ solution\}$.

Is there a quick way of doing this? I know I can augment A with $b = (b_1, b_2, b_3, b_4)^T$, do row reduction, and then look at the row of zeros, but that seems quite laborious?

• the system will have no solution precisely when $b$ is not in the column space of $A$. (and be careful with your terminology: the set of such $b$ is not a vector space; it does not contain the zero vector. so it makes no sense to ask for a "basis" of that set.) – symplectomorphic May 17 '14 at 11:04
• That doesn't seem immediately obvious to me, can you explain further? – Brian May 17 '14 at 11:05

Denote $A\in\mathbb{F}^{m\times n}$ by $$A=\begin{bmatrix}a_{11} & a_{12} & . & . & . & & & a_{1n}\\ a_{21} & & & & & & & a_{2n}\\ . & & . & & & & & .\\ . & & & . & & & & .\\ . & & & & . & & & .\\ \\ \\ a_{m1} & a_{m2} & . & . & . & & & a_{mn} \end{bmatrix}$$

and $$x=\begin{bmatrix}x_{1}\\ x_{2}\\ .\\ .\\ .\\ \\ \\ x_{n} \end{bmatrix}$$

then $$Ax=\begin{bmatrix}a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}\\ a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}\\ .\\ .\\ .\\ \\ \\ a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n} \end{bmatrix}=\begin{bmatrix}a_{11}\\ a_{21}\\ .\\ .\\ .\\ \\ \\ a_{m1} \end{bmatrix}x_{1}+\begin{bmatrix}a_{12}\\ a_{22}\\ .\\ .\\ .\\ \\ \\ a_{m2} \end{bmatrix}x_{2}+...+\begin{bmatrix}a_{1n}\\ a_{2n}\\ .\\ .\\ .\\ \\ \\ a_{mn} \end{bmatrix}x_{n}$$

Note that column matrices that are multiplied by the $x_{i}$ are the columns of $A$ hence any vector $b$ of the form $b=Ax$ is a linear combination of the columns of $A$ and thus in the span of the columns of $A$.

On the other hand, denote the columns of $A$ as $C_{1},C_{2},...,C_{n}$. If $b$ is a linear combination of the columns of $A$ this precisely means that there are scalars $\alpha_{1},\alpha_{2},...\alpha_{n}$ s.t $$b=\alpha_{1}C_{1}+\alpha_{2}C_{2}+...+\alpha_{n}C_{n}$$

and we see (using the above about $Ax$) that choosing $x_{i}=\alpha_{i}$ would give us $Ax=b$.

We conclude that the span of the columns of $A$ is precisely the set of solutions $Ax=b$, thus you are looking for all the vectors in the space that are not in that spanned subspace

Note: Since $0\not\in B$ (since $Ax=0$ have a solution, $x=0$) then $B$ is not a subspace and thefore we can't talk about a basis for this space.

• No, adding the zero vector does not (in the general case) produce a subspace. Consider, for simplicity $A=\begin{pmatrix}1&0\\0&1\\0&0\end{pmatrix}$. Then $B$ comtains both $(1,0,1)^{\sf t}$ and $(1,0,-1)^{\sf t}$, but their sum is $(2,0,0)^{\sf t}$ which is not in $B\cup\{0\}$. – hmakholm left over Monica May 17 '14 at 12:05
• @HenningMakholm - I agree. But I do believe that in this case it does – Belgi May 17 '14 at 12:14
• The only cases in which $W$ is a subspace and $(V\setminus W)\cup\{0\}$ is also subspace is if $W=V$ or $W=\{0\}$. Since $A$ in this question has rank 3, we're not in one of those cases. – hmakholm left over Monica May 18 '14 at 11:08
• @HenningMakholm what about $\mathbb{R}^2$ and $W=sp\{(1,0)\}$? – Belgi May 18 '14 at 15:37
• $(1,1)+(1,-1)=(2,0)\in W$. – hmakholm left over Monica May 18 '14 at 23:11

When you multiply a matrix by a (column) vector, you get a vector that is a linear combination of the columns of the matrix, where the coefficients/weights come from the components of the column vector. I'm too lazy to illustrate with a $4\times 3$ example, so here's a $2\times 2$ example: $$Ax=\begin{pmatrix} \mathbf{A_1} & \mathbf{A_2}\end{pmatrix}\begin{pmatrix}x_1 \\ x_2\end{pmatrix}=x_1\mathbf{A_1}+x_2\mathbf{A_2}$$ where $\mathbf{A_1}$ is the first column of the matrix $A$ and $\mathbf{A_2}$ is the second column.

In other words, $Ax$ is a linear combination of the columns of $A$. But the column space of $A$, i.e. the image of $A$, is just the span of the columns of $A$. So the equation $Ax=b$, which says that $b$ is a linear combination of the columns of $A$, will have a solution if and only if $b$ is in the column space of $A$.