Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Question on Linear Algebra

  1. Oct 16, 2008 #1
    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. jcsd
  3. Oct 16, 2008 #2
    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.
  4. Oct 16, 2008 #3
    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!
  5. Oct 16, 2008 #4
    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.
  6. Oct 16, 2008 #5

    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???
  7. Oct 16, 2008 #6


    User Avatar
    Homework Helper

    Solving the system

    A x = b


    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.
  8. Oct 16, 2008 #7


    User Avatar
    Science Advisor

    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.
  9. Oct 16, 2008 #8
    @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 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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook