1
$\begingroup$

$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?

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – symplectomorphic May 17 '14 at 11:04
  • $\begingroup$ That doesn't seem immediately obvious to me, can you explain further? $\endgroup$ – Brian May 17 '14 at 11:05
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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\}$. $\endgroup$ – hmakholm left over Monica May 17 '14 at 12:05
  • $\begingroup$ @HenningMakholm - I agree. But I do believe that in this case it does $\endgroup$ – Belgi May 17 '14 at 12:14
  • $\begingroup$ 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. $\endgroup$ – hmakholm left over Monica May 18 '14 at 11:08
  • $\begingroup$ @HenningMakholm what about $\mathbb{R}^2 $ and $W=sp\{(1,0)\} $? $\endgroup$ – Belgi May 18 '14 at 15:37
  • $\begingroup$ $(1,1)+(1,-1)=(2,0)\in W$. $\endgroup$ – hmakholm left over Monica May 18 '14 at 23:11
2
$\begingroup$

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$.

$\endgroup$

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.