Solving Linear Algebra with Full Column Rank Matrix

[tulsidas]

Homework Statement

The system Ax = b does not have a solution.
A is a full column rank matrix.

Multiply both sides of the equation, Ax =b with A^T.
We get,

A^T A x = A^T b

Solving for x now, we get

x = [inverse of ( A^T A)] A^Tb

By using relevant examples, we find that solution for the system exists, a contradiction to what the system looked like originally!

How is this possible? Is there some incorrect assumption?

The Attempt at a Solution

One doubt that I have is that I am not entirely sure whether the operation of multiplying the system with A^T on both sides from the left, is a valid one in the first place.

inverse of A^T does not exist. So there is no way of returning back to the original system i.e Ax = b from A^T A x = A^T b

Is this a reasonable question and ,if not, where I am going wrong? What seems to be the problem?

 

[rmcdra]

A transpose is when you change the column and rows of a matrix. Doesn't a matrix and its transversal multiplied gives you a square matrix? A square matrix has an inverse. The results of your X matrix will determine if your system has a solution or not.

 

[tulsidas]

@rmcdra
Small problem in that assumption:
not every square matrix has an inverse.
if the square matrix in full rank, then the inverse exists.

Given the condition, that A is full column rank, ATA if also going to be full column rank and therefore it will be invertible.

That, fact, cannot help in solving the problem though!

 

[rmcdra]

Thank you for correcting my assumption about square matrices. Still the fact remains if the solution for the system does not exist or is non-deterministic, the solution to X matrix will still express this.

 

[tulsidas]

@rmcdra

Ok let me clarify my question with an example...

say we have three equations

x1 = 1
x2 = 1
x1 + x2 = 3

Obviously the system has no solution.

Now construct the system : Ax = b

A is a rectangular matrix with (1,0,1) as the first column and (0,1,1) as the second column.

b is a column vector with entries 1, 1 and 3.

Now multiply A^T on both sides of Ax = b from the left. ( i expressed a doubt on the validity of this operation...see my first post)

We have: A^TAx = A^Tb

A^TA works out to be square matrix with the first column as (2,1) and the second column as (1,2)

ATb works out to be a column vector again with both the entries as 4.

Solve for x1 and x2 and you get the solution as x1=x2= 4/3.

How did the system become solvable?

 

[statdad]

Solving the system

$$A x = b$$

using

$$x = (A'A)^{-1} A'b$$

is the same method used in regression when the least squares estimates of the regression coefficients are found. The process does not solve the original system (notice that 4/3, 4/3 doesn't solve the system you give as an example), but it does solve this system:

$$A'A x = A'b$$

The solution is the point from the column space of A that is closest to the original vector x.

 

[HallsofIvy]

What you are getting, x= (AA')^-1)A'b is one type of "generalized inverse".
IF Ax= b has an inverse, then A^-1= (AA')^-1)A'. If A does not have an inverse, its "generalized inverse" may exist.

For example, suppose you have the problem of finding M and N such that y= Mx+ N for n points (x_i, y_i). Of course, a single line will not, in general, go through n points, for n> 2, so that problem has no solution.

You can, however, cast it as a matrix problem: solve Ax= b where A is the n by 2 matrix having the x_i values as the first column, all 1s on the second column, x is the 2 by 1 column matrix with the unknown value M as the first row and N as the second, and b is the n by 1 column matrix having the y_i values as each row.

Of course, A has no inverse since it is not a square matrix. But you can do just what you have suggested and get a solution. It will give you the "least squares" line- the line that comes closest to all the points in the sense that the sum of the distances from each point to the line is a minimum.

 

[tulsidas]

@statdad and HallsofIvy

I must admit that I have not started studying topics on orthogonality. I am looking at this problem purely from the perspective of vector spaces.

Agreed that the solution obtained is the least-squares solution and it still does not satisfy the original system.

My question was more in tune with how the vector spaces have changed after this operation of multiplying A^T on both the sides of Ax = b from the left.

In the first case (for Ax = 0 i.e) ,clearly b is not in the column space of A.

But in the second case, A^Tb lies in the column space of A^TA.

I am not able to picture the alterations in the vector spaces as a result of multiplication of A^T. That is the problem.

Another question, how do we get back to Ax = b from A^TAx = A^Tb?