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