Computational cost of calculating an inverse via Gauss-Jordan

[Fractal20]

Homework Statement

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.

Homework Equations

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=1ⁿ (n-i)n + (i-1)n
=n² + [itex]\sum[/itex]_i=1ⁿ n² -1
=n³+n² multiplications

and the additions are
=[itex]\sum[/itex]_i=1ⁿ (n-i)(n-1) + (i-1)(n-1)
=n³ - 2n²+n

Is this incorrect? If so, can you give me a hint as to where I went astray? Thanks

 

[Fractal20]

Anybody?