# Computational cost of calculating an inverse via Gauss-Jordan

• Fractal20
In summary, the computational cost for finding the inverse of an nxn matrix via Gauss-Jordan elimination involves n^3 + n^2 multiplications and n^3 - 2n^2 + n additions. The process involves eliminating entries below the diagonal first and then using the diagonal element to eliminate entries above the diagonal. After going through all n steps, the resulting matrix needs to be divided by the diagonal entries to obtain the identity matrix. If the calculation does not agree with fellow students, it may be helpful to review the steps and see where any mistakes were made.
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.

## 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 + $\sum$i=1n (n-i)n + (i-1)n
=n2 + $\sum$i=1n n2 -1
=n3+n2 multiplications

=$\sum$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

Anybody?

Autar Kaw

## What is the computational cost of calculating an inverse via Gauss-Jordan?

The computational cost of calculating an inverse via Gauss-Jordan depends on the size of the matrix, with larger matrices requiring more computational resources. It also depends on the efficiency of the algorithm used to perform the calculations.

## How does the size of the matrix affect the computational cost?

The size of the matrix directly affects the computational cost, as larger matrices require more operations to be performed in order to calculate the inverse. This can significantly increase the time and resources needed for the calculation.

## What is the efficiency of the Gauss-Jordan algorithm for calculating inverses?

The Gauss-Jordan algorithm is known for its efficiency in calculating inverses, as it uses row operations to reduce the matrix to reduced row-echelon form, making it easier to find the inverse. However, for larger matrices, the computational cost may still be significant.

## Are there any alternative methods for calculating inverses that have a lower computational cost?

Yes, there are alternative methods for calculating inverses, such as the LU decomposition method, which can have a lower computational cost for larger matrices. However, the choice of method also depends on the specific characteristics of the matrix being inverted.

## How can the computational cost of calculating an inverse via Gauss-Jordan be reduced?

The computational cost of calculating an inverse via Gauss-Jordan can be reduced by implementing efficient algorithms and optimizing the code for matrix operations. Additionally, using parallel processing techniques can also help to reduce the computational cost.

• Calculus and Beyond Homework Help
Replies
4
Views
1K
• Calculus and Beyond Homework Help
Replies
3
Views
774
• Calculus and Beyond Homework Help
Replies
5
Views
10K
• Math Proof Training and Practice
Replies
23
Views
1K
• General Math
Replies
22
Views
3K
• Precalculus Mathematics Homework Help
Replies
1
Views
727
• Calculus and Beyond Homework Help
Replies
1
Views
2K
• General Math
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Linear and Abstract Algebra
Replies
5
Views
1K