# Question on Linear Algebra

1. Oct 16, 2008

### tulsidas

1. The problem statement, all variables and given/known data

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 AT.
We get,

AT A x = AT b

Solving for x now, we get

x = [inverse of ( AT A)] ATb

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?

3. 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 AT on both sides from the left, is a valid one in the first place.

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

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

2. Oct 16, 2008

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

3. Oct 16, 2008

### 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!

4. Oct 16, 2008

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

5. Oct 16, 2008

### 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 AT 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: ATAx = ATb

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

6. Oct 16, 2008

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.

7. Oct 16, 2008

### HallsofIvy

Staff Emeritus
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 (xi, yi). 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 xi 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 yi 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.

8. Oct 16, 2008

### tulsidas

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 AT 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, ATb lies in the column space of ATA.

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

Another question, how do we get back to Ax = b from ATAx = ATb?