1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Computational cost of calculating an inverse via Gauss-Jordan

  1. Jan 23, 2013 #1
    1. The problem statement, all variables and given/known data
    Find the computational cost for finding the inverse of an nxn matrix via Gauss-Jordan elimination. That is setting up A|I and converting it to I|A-1.

    2. Relevant equations

    3. The attempt at a solution
    So I can't see where I went wrong, but my answer does not agree with my fellow students.

    Consider the ith step in the process. We need to first eliminate the entries in rows below the ith diagonal entry and then use this diagonal element to eliminate the entries above the ith diagonal. Consider eliminating the entries below first.

    We have (n-i) rows and for each row we must calculate the constant by which to multiply by. Then we must multiply the remaining n-i elements in that row plus the (i-1) entries on the augmented side (it is i-1 since the entries are 0 on the augmented side to the right of the diagonal and the ith diagonal entry is a 1 and thus we need not calculate the constant to multiple again). Altogether that is (n-i+i-1+1)=n multiplications for each on the (n-i) rows. Also, for each row there are (n-i-1) additions plus i additions on the augmented side for a total of (n-i-1+i)=(n-1) additions for each of the (n-i) rows.

    For eliminating the entries above the ith diagonal for each of the (i-1) rows we must compute the constant to multiply by, and the product with the (n-i+i-1) remaining entries (again i;m not including the ith diagonal entry in the augmented matrix since it is a 1). Thus we get (i-1)n multiplications and (i-1)(n-1) additions.

    After going through i:1->n we only need to divide each row by the diagonal entry to get the identity. We must calculate the constant to multiple and then multiply the n entries on the augmented side for a total of (n+1)n multiplications.

    Thus the multiplications are
    =(n+1)n + [itex]\sum[/itex]i=1n (n-i)n + (i-1)n
    =n2 + [itex]\sum[/itex]i=1n n2 -1
    =n3+n2 multiplications

    and the additions are
    =[itex]\sum[/itex]i=1n (n-i)(n-1) + (i-1)(n-1)
    =n3 - 2n2+n

    Is this incorrect? If so, can you give me a hint as to where I went astray? Thanks
  2. jcsd
  3. Jan 24, 2013 #2
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook