Seemingly simple linear algebra

1. May 24, 2013

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?

Last edited: May 24, 2013
2. May 24, 2013

Skins

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

3. May 24, 2013

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?

4. May 24, 2013

Ray Vickson

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

5. May 24, 2013

phasic

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

6. May 24, 2013

Ray Vickson

Yes.

7. May 24, 2013

Skins

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)

Last edited: May 24, 2013
8. May 25, 2013

phasic

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

9. May 25, 2013

Ray Vickson

What have you tried so far? Show your work.

10. May 25, 2013

Skins

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 :(

11. May 26, 2013

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