# Homework Help: Least Squares Linear Algebra

1. Nov 9, 2012

### StandardBasis

1. The problem statement, all variables and given/known data
Hi there! First time user, so I hope I do this right. The question is: Let A be an 8x5 matrix of rank 3, and let b be a nonzero vector in N(AT). First, prove that the system Ax=b must be inconsistent. Then, how many least squares solutions will the system have?

2. Relevant equations

3. The attempt at a solution
I got the first part fine (I think...). I assume that Ax=b is consistent, and look for a contradiction. There is one: for Ax=b to be consistent, b must be in the column space of A. But we are told b is in the nullspace of AT, which is the orthogonal complement of R(A). So b isn't actually in R(A), and thus Ax=b is inconsistent by the fact that b isn't a linear combination of A's columns.

Now for the second part, I know I need to find all solutions to ATAx=ATb. In class we proved that if A is mxn with rank n, then there is a unique solution to the normal equations. Obviously rank is not n here, so I'm not sure what to do. I'm used to systems having either 0, 1, or infinitely many solutions... so I'm tempted to say infinitely many? But I can't justify that.

2. Nov 9, 2012

### haruspex

ATA will be 5x5 rank 3, yes? And you want all solutions of ATAx=0. Won't that be a 2-D subspace?

3. Nov 9, 2012

### StandardBasis

But I don't want to find the solutions to ATAx=0, I want to find solutions to ATAx=ATb.

Second, unless I misunderstand what it means to find a least squares solution, I thought I'm looking for the vector(s) that produce a projection of b (which isn't in the range aka column space of A) onto the range of A. If 2 vectors did do this, wouldn't linear combos of them also do it?

4. Nov 9, 2012

### haruspex

You wrote that b is in the nullspace of AT, so isn't ATb zero?
I don't understand how a vector can 'produce' a projection of another vector. But we agree you're looking for a subspace.

5. Nov 9, 2012

### StandardBasis

Ah, yes, my mistake for forgetting that.

Probably not the best choice of words on my part, to say produce. I meant that in the sense that if z is the particular least squares solution we're talking about, the p=Az where p is the 'closest' vector to b. So I chose produce because not z itself, but the product of A and z gives the vector we are searching for.

So I now understand we're looking for a 2-D subspace. But why would that mean there are 2 least squares solutions, and not infinitely many? After all, there are infinitely many solutions to the normal equations (the entire 2-D subspace in question!)

6. Nov 10, 2012

### haruspex

It would indeed mean infinitely many. Who's saying there are two?

7. Nov 10, 2012

### StandardBasis

Apologies, I thought your reference to a 2d subspace meant that the two basis vectors were the solutions.

Is there a way to visualize how infinitely many vectors can all lead to the same "closest vector" to b?

8. Nov 10, 2012

### haruspex

Yes, I was wondering about that. Clearly it is what will happen if ATA is singular, so need to construct an example like that. Suppose some column is all zeroes. That means we have no information about that dimension, so we can vary the solution in that dimension without changing the sum of squares.

9. Nov 11, 2012

### StandardBasis

Wait, one more question: how did I know that the product of A transpose and A has rank 3?

10. Nov 11, 2012

### haruspex

I was rather hoping that was a standard result you could appeal to. It's 30 years since I did any of this stuff.

11. Nov 11, 2012

### StandardBasis

Well, I guess I know that since A has rank 3, then transpose of A also has rank 3. The rank of a product is less than or equal to the minimum of the rank of the two multiplied matrices. So the rank is at least less than or equal to 3; but in any case, the product is not a matrix of full rank.

Is that enough? Perhaps someone with more immediate experience can provide a hint?

12. Nov 11, 2012

### haruspex

Yes, that suffices for this question. More generally, I would think ATA would have the same rank as A, but I don't see how to prove it easily.