matrix inverse

[vesyyr]

I need to inverse a matrix given in a file.
The problem is I'm stuck with writing determinant finding algoritm into code.

I found this algoritm about finding determinant of nxn matrix. This is what i need:

http://www.maths.surrey.ac.uk/explore/emmaspages/option1.html#top

and here:

a11 a12 a13
a21 a22 a23
a31 a32 a33

Det= a11(a22a33 ? a23a32) ? a12(a21a33 ? a23a31) + a13(a21a32 ? a22a31)
Note the pattern of + and ? signs.
The general formula is compact, but tedious to compute. Here it is for an n by n matrix A:
detA = ai1Ci1 + ai2Ci2 + · · · + ainCin

where Cij are referred to as the cofactors and are computed from
Cij = (?1)i+j detMij
The term Mij is known as the ”minor matrix” and is the matrix you get if you eliminate row
i and column j from matrix A. So to find the determinant of e.g. a 4×4 matrix, you end up
calculating a bunch of 3 × 3 matrix determinants (much easier). Obviously you can apply this
technique recursively (probably using a computer).

***************

Can some1 please write it into my code or if he has time even complete the full inverse.

I read the matrix from a file into an array "row":
----------------

#!/usr/bin/awk -f
BEGIN{}
{
m=1
while (m <= NF){
row[NR,m] = $m
m++
}
}

END{}

--------------

thank you.

 

[vesyyr]

I got something done, but it only works for 2*2 and 3*3 matrices. There must be a mistake. I used the code I found somewhere:

int determinant(int b[5][5],int m) //FUNCTION TO CALCULATE
DETERMINANT
{
int i,j,sum = 0,c[5][5];
if(m==2)
{ //BASE CONDITION
sum = b[0][0]*b[1][1] - b[0][1]*b[1][0];
return sum;
}
for(int p=0;p<m;p++)
{
int h = 0,k = 0;
for(i=1;i<m;i++)
{
for( j=0;j<m;j++)
{
if(j==p)
continue;
c[h][k] = b[j];
k++;
if(k == m-1)
{
h++;
k = 0;
}

}
}

sum = sum + b[0][p]*pow(-1,p)*determinant(c,m-1);
}
return sum;
}



I also used this:
function det( a, n )

if n = 2 then

d := a11·a22 - a12·a21

else

d := 0

for i := 1...n do

M1i <-- A with row 1 and column i deleted

d := d + (-1)(i-1)·a1i·det( M1i, n - 1 )

end for

end if

return d

end function







And got my awk code:

function det(a, n) {
if (n == 2) {
d = a[1,1] * a[2,2] - a[1,2] * a[2,1]
print d
}

else {
d=0
for(i = 1; i <= n; i++){
k=1
j=1
for (x = 2; x <= n; x++) {
for (z = 1; z <= n; z++){
if (z==i)
{z++}
M[k,j]= a[x,z]
j++}
j=1
k++


}
d= d + miinus1_astmel(i-1)*a[1,i]*det( M, n - 1)
}
return d


}


function miinus1_astmel{
vastus=1
for (x=1; x<=n; x++){
vastus=vastus*(-1)
}
return vastus
}



Looks the same to me, but somewhere is a mistake.

 

[hoinz]

Hello vesyyr,

interesting problem, reminds me of my math classes...

I did not check all of your code, but one problem could be in determining
M1n <-- A with row 1 and column n deleted.

look at this piece of code:
if (z==i)
{z++}
M[k,j]= a[x,z]

In case of i=n this will become:
M[k,j]= a[x,n+1]
But what is a[x,n+1], if A is an n*n-matrix?

And by the way, just curious, may I ask why you are trying to solve this problem in awk?
Homework perhaps?
I am sure you will improve your awk skills that way.
But regarding speed, I am also sure that a solution in a scripting language like awk will never be able to compete with a solution in a compiler language like C.
Or in other words: Don't use your solution in a commercial product!

regards

 

[vesyyr]

for (x = 2; x <= n; x++) {
for (z = 1; z <= n; z++){
if (z==i)
{z++}
if (z==n+1)
{break}
M[k,j]= a[x,z]
j++}

should fix the problem.
But there must be more something wrong. With 4*4 matrix still gives wrong answer.

 

[fpmurphy]

Just a note, it is less compute intensive to calculate the determinant of a matrix using Gauss-Jordan Elimination. Do a web search to find examples of this method.