0
$\begingroup$

Hello guys I am writing program to compute determinant(this part i already did) and Inverse matrix with GEPP. Here problem arises since i have completely no idea how to inverse Matrix using GEPP, i know how to inverse using Gauss Elimination ([A|I]=>[I|B]). I have searched through internet but still no clue, could you please explain me?

Here is my matlab code (maybe someone will find it useful), as of now it solves AX=b and computes determinant:

function [det1,X ] = GEPP( A, b )
%GEPP
perm=0;

n = length(b);
if n~=m 
error('vector has wrong size');
end
for j = 1:n
    p=j;
    % choice of main element
    for i = j:n
        if abs(A(i,j)) >= abs(A(p,j))
            p = i;
        end
    end
    if A(p,j) == 0
        error('Matrix A is singular');
    end
    %rows permutation
    t       = A(p,:);
    A(p,:)  = A(j,:);
    A(j,:) = t;
    t       = b(p);
    b(p)    = b(j);
    b(j)    = t;
    if~(p==i)
    perm=perm+1;
    end

    % reduction
    for i = j+1:n
        t       = (A(i,j)/A(j,j)); 
        A(i,:)  = A(i,:)-A(j,:)*t; 
        b(i)    = b(i)-b(j)*t; 
    end 
end
%determinant
mn=1;
for i=1:n
    mn=mn*A(i,i);
end
det1=mn*(-1)^perm;
% solution
X   = zeros(1,n); 
X(n) = b(n)/A(n,n); 

if (det1~=0)
for i = 1:n
    s = sum( A(i, (i+1):n) .* X((i+1):n) ); 
    X(i) = (b(i) - s) / A(i,i); 
end
end
end
$\endgroup$
  • $\begingroup$ you should also post this on stackoverflow $\endgroup$ – iostream007 Jun 9 '13 at 16:37
  • $\begingroup$ I posted it on stack, but they told me that here is a better place... $\endgroup$ – Matthew Grossman Jun 9 '13 at 16:46
  • $\begingroup$ OK lets see someone can help you $\endgroup$ – iostream007 Jun 9 '13 at 16:49
  • $\begingroup$ @MatthewGrossman: Welcome to MSE! Are you looking for a GEPP algorithm to code up or an example of how to use GEPP or am I misunderstanding your question? Regards $\endgroup$ – Amzoti Jun 9 '13 at 17:00
  • $\begingroup$ I have GEPP algorithm to solve AX=B, what I need is HOW TO COMPUTE INVERSE MATRIX USING GAUSSIAN ELIMINATION WITH PARTIAL PIVOTING $\endgroup$ – Matthew Grossman Jun 9 '13 at 17:36
3
$\begingroup$

It really is no different than doing Gaussian Elimination with Pivoting, but repeating each step to an augmented matrix.

We would set up and do GEPP to both sides of the augmented matrix $[A | I]$.

If the matrices condition number plays nice, we will end up with $[I | A^{-1}]$. Note, I would recommend you also look into the Crout and the Doolittle procedures as better alternatives! Also, it is worth noting that you must be careful with single precision, rounding and numerical issues!

So, lets do a difficult example of what I described above so you can see it in practice (so, just take whichever variant of GEPP you are using and set up the augmented matrix as above and see if you end up with the inverse as I show below).

$$A = \left[\begin{array}{ccccc} 1 & 1/2 & 1/3 & 1/4 & 1/5 \\ 1/2 & 1/3 & 1/4 & 1/5 & 1/6 \\ 1/3 & 1/4 & 1/5 & 1/6 & 1/7 \\ 1/4 & 1/5 & 1/6 & 1/7 & 1/8 \\ 1/5 & 1/6 & 1/7 & 1/8 & 1/9 \end{array}\right]$$

Do pivoted Gaussian Elimination (row reduction):

Setup the augmented matrix $[A | I]$ as:

$$\left[\begin{array}{ccccc|ccccc} 1 & 1/2 & 1/3 & 1/4 & 1/5 & 1 & 0 & 0 & 0 & 0\\ 1/2 & 1/3 & 1/4 & 1/5 & 1/6 & 0 & 1 & 0 & 0 & 0\\ 1/3 & 1/4 & 1/5 & 1/6 & 1/7 & 0 & 0 & 1 & 0 & 0\\ 1/4 & 1/5 & 1/6 & 1/7 & 1/8 & 0 & 0 & 0 & 1 & 0\\ 1/5 & 1/6 & 1/7 & 1/8 & 1/9 & 0 & 0 & 0 & 0 & 1 \end{array}\right]$$

Perform the following GEPP steps:

  • Subtract 1/2 (row 1) from row 2
  • Multiply row 1 by 60
  • Multiply row 2 by 120
  • Multiply row 3 by 420
  • Multiply row 4 by 840
  • Multiply row 5 by 2520
  • Subtract 7/3 (row 1) from row 3
  • Multiply row 3 by 3
  • Subtract 7/2 (row 1) from row 4
  • Multiply row 4 by 2
  • Subtract 42/5 (row 1) from row 5
  • Multiply row 5 by 5
  • Swap row 2 with row 5
  • Subtract 1/8 (row 2) from row 3
  • Multiply row 3 by -8
  • Subtract 3/20 (row 2) from row 4
  • Multiply row 4 by -20
  • Subtract 1/84 (row 2) from row 5
  • Multiply row 5 by -84
  • Swap row 3 with row 5
  • Subtract 2/3 (row 3) from row 4
  • Multiply row 4 by 3
  • Subtract 8/15 (row 3) from row 5
  • Multiply row 5 by 15
  • Swap row 4 with row 5
  • Subtract 3/7 (row 4) from row 5
  • Multiply row 5 by 7/8
  • Subtract 128 (row 5) from row 4
  • Subtract 224 (row 5) from row 3
  • Subtract 896 (row 5) from row 2
  • Subtract 12 (row 5) from row 1
  • Subtract 3 (row 4) from row 3
  • Subtract 15 (row 4) from row 2
  • Subtract 5/21 (row 4) from row 1
  • Subtract 8 (row 3) from row 2
  • Subtract 1/6 (row 3) from row 1
  • Subtract 1/28 (row 2) from row 1
  • Divide row 1 by 60
  • Divide row 2 by 840
  • Divide row 3 by 120
  • Divide row 4 by 63

Our final solution using GEPP gives us (in this case), the desired $[I | A^{-1}]$ as:

$$\left[\begin{array}{ccccc|ccccc} 1 & 0 & 0 & 0 & 0 & 25 & -300 & 1050 & -1400 & 630\\ 0 & 1 & 0 & 0 & 0 & -300 & 4800 & -18900 & 26880 & -12600\\ 0 & 0 & 1 & 0 & 0 & 1050 & -18900 & 79380 & -117600 & 56700\\ 0 & 0 & 0 & 1 & 0 & -1400 & 26880 & -117600 & 179200 & -88200\\ 0 & 0 & 0 & 0 & 1 & 630 & -12600 & 56700 & -88200 & 44100 \end{array}\right]$$

$\endgroup$
  • $\begingroup$ oh, my, the formatting nightmare! Nice work, and +10K for all that effort! $\endgroup$ – Namaste Jun 10 '13 at 0:11
  • $\begingroup$ Amzoti u used row swapping, don't u have to use permutation matrix then? $\endgroup$ – Matthew Grossman Jun 10 '13 at 8:42
  • $\begingroup$ You are thinking about $LU$ and related factorizations. For Gaussian Elimination w/pivoting, you can use rows or columns. See another example here. That is why I asked if you wanted an algorithm, so you can see what is legal and that you typically use row or column pivoting and that there are multiple approaches. If you have your schema coded up, run the matrix above through it and see if it produces the same result. $\endgroup$ – Amzoti Jun 10 '13 at 12:38
  • $\begingroup$ Thanks, Amzoti, for the support! $\endgroup$ – Namaste Jun 11 '13 at 4:21
  • $\begingroup$ Minor goals...silly goals...might make, but not break, my day if I reach them, or not. ;-) $\endgroup$ – Namaste Jun 11 '13 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.