determinant of matrix

general
1

hello

I am doing some problem which include part of finding greatest matching and perfect matching in graph. I found that it is easy to implement it by tutte’s matrix. I read algorithm here.

 for (int i=0;i<n;++i) {
	int k = i;
	for (int j=i+1;j<n;++j)
		if (abs(a[j][i])>abs(a[k][i]))
			k=j;//find row number in which current column has maximum value  
	if (abs(a[k][i])<EPS) {
		det = 0;
		break;
	}``
	for(int s=i;s<m;s++){
	double tmp=a[i][s];
	a[i][s]=a[k][s];
	a[k][s]=tmp;
	}//swap current row with the maximum value row found
	if(i!=k)
		det =-det;//if row swapped then determinant would be multiplied by (-1)
	det*= a[i][i];
	for (int j=i+1;j<n;++j)
		a[i][j]/= a[i][i]; //divide the row by a[i][i] where colun number is greater then i




     for (int j=0;j<n;++j)
		if (j!=i&&abs(a[j][i])>EPS)
			for (int k=i+1;k<n;++k)
				a[j][k]-= a[i][k]*a[j][i];

}

but i am unable to understand the last two loops of algorithm what actually they are doing.and i also printed the matrix after each operation and at the end i am not getting upper triangular matrix but determinant calculated is always right.

1 Like
2

The last 4 lines of the code you posted (if that’s the part you’re asking about) seem to be just Gaussian elimination. Specifically, you try to subtract the i-th row from other rows, so that the only non-zero element in the i-th column would be a[i][i]. Then, if the matrix is full-rank, it’ll be diagonalized this way (so determinant = product of diagonal elements), and det A = 0 otherwise. (When writing this, I assume you know at least the basics of Gaussian elimination and lingebra.)

2 Likes
3

Refer to this if you want to know whats happening in this code
http://courses.cms.caltech.edu/cs171/c2-1.pdf

1 Like
4

I am able to capture it is gaussian elimination but the final matrix is not result as the upper triangular matrix ,so how we can just multiply all the diagonal values to get determinant.it should be upper triangular for that.
thanks

1 Like
5

I think it will be upper triangular. On what input do you think it wouldn’t be?

1 Like
6

check this. you will always get right determinant but matrix is not as it should be.it is not upper nor lower triangular

7

I see, the one who coded it obviously doesn’t realize that the loops can go from n-1 to i and not from i+1 to n-1. Check this out: http://ideone.com/U4Ou2k.

The code in the OP simply doesn’t modify the i-th column in the i-th cycle. In proper Gaussian elimination, that column would contain zeroes anywhere but at the diagonal, if modified - this code skips the step, but does correct work on columns i+1 to n-1, and when further computing the determinant, only these columns matter. It’s a weird way, but it works.

8

thanks xellos to make me clear. i understand it. kind a silly mistake… any way this part of code was taken from e-maxx site.
thanks again…