Seemingly simple linear algebra

[phasic]

Why is it that for arbitrary z, A$^{T}$z = 0 and b$^{T}$z ≠ 0 when there does not exist an x such that Ax = b, i.e. that b is not in the range space of A, where A is an n x m matrix?

 

[Skins]

"Range space" ?? Do you mean "row space" ??

 

[phasic]

Actually, it means column space. This means that there is no linear combination of A's columns that gives b. This must mean that there is no x for which Ax = b, right?

 

[Ray Vickson]

Why is it that for arbitrary z, A$^{T}$z = 0 and b$^{T}$z ≠ 0 when b is not in the range space of A when Ax = b, where A is an n x m matrix?

Huh? How can 'b' not be in the range space of A when AX=b? That is contradictory!

 

[phasic]

Edited the post so that it makes more sense. Does it now?

 

[Ray Vickson]

Edited the post so that it makes more sense. Does it now?

Yes.

 

[Skins]

Actually, it means column space. This means that there is no linear combination of A's columns that gives b. This must mean that there is no x for which Ax = b, right?

Okay, sorry. I am just not used to using that term. I usually use the following for the 4 fundamental spaces

C(A) - column space (of A)
$C(A^T)$ - row space (of A)
N(A) - null space (of A)
$C(A^T)$ - left handed nullspace of A (i.e nullspace of A transpose)

 

[phasic]

So the column space of A transpose is the null space of A?

 

[Ray Vickson]

Why is it that for arbitrary z, A$^{T}$z = 0 and b$^{T}$z ≠ 0 when there does not exist an x such that Ax = b, i.e. that b is not in the range space of A, where A is an n x m matrix?

What have you tried so far? Show your work.

 

[Skins]

So the column space of A transpose is the null space of A?

Whoops... My error. No it is not. The nullspace of A transpose is NOT the column space of A transpose I meant to write

$$N(A^T)$$

The null space of A transpose is of course the set of all vectors y such that

$$A^T y \, = \, 0$$

We sometimes call it the "left null space" because is we take the transpose of both sides of the above equation.

$$(A^Ty)^T \, = \, 0^T$$

we get

$$y^T A \, = \, 0^T$$

Sorry for my mistake. I'm going to try to edit it and correct my typo before it causes confusion. Unfortunately I don't see an edit function available :(

 

[phasic]

This statement came from the book Convex Optimization by Boyd and Vandenberghe. I forget which page now, but the idea has come up again in Farkas' lemma, but in a different form.

http://en.wikipedia.org/wiki/Farkas'_lemma

Let A be an n × m matrix and b an n-dimensional vector. Then, exactly one of the following two statements is true:

(1) There exists an x ∈ Rm such that Ax = b and x ≥ 0.
(2) There exists a y ∈ Rn such that A$^{T}$y ≥ 0 and b$^{T}$y < 0.

This is close but the original statement involves equalities similar to (2).