Least Squares Solutions for Inconsistent Linear Systems

[StandardBasis]

Homework Statement

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(A^T). First, prove that the system Ax=b must be inconsistent. Then, how many least squares solutions will the system have?

Homework Equations

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 A^T, 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 A^TAx=A^Tb. 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.

 

[haruspex]

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

 

[StandardBasis]

But I don't want to find the solutions to A^TAx=0, I want to find solutions to A^TAx=A^Tb.

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?

 

[haruspex]

But I don't want to find the solutions to A^TAx=0, I want to find solutions to A^TAx=A^Tb.

You wrote that b is in the nullspace of A^T, so isn't A^Tb zero?

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?

I don't understand how a vector can 'produce' a projection of another vector. But we agree you're looking for a subspace.

 

[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!)

 

[haruspex]

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?

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

 

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

 

[haruspex]

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

Yes, I was wondering about that. Clearly it is what will happen if A^TA 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.

 

[StandardBasis]

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

 

[haruspex]

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

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

 

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

 

[haruspex]

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.

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