# calculating matrix rank with gaussian elimination

[The answer to my problem has been found: it was a simple sign error. the pseudo code below is fine]

I have implemented an algorithm in c++ that should calculate the matrix rank of a given n x m matrix, but it turns out, that sometimes the rank calculation yields a value less than expected. I'm not posting this on stackoverflow.com since I think it's rather a problem with the mathematics behind.

So here's my pseudo code:

• Of a given n x m matrix M, find the position of the entry of the the first column which has the highest absolute value (often called pivot element): $i=argmax(|M_{j,1}|)$

• Swap the first row with row i.

• If $M_{1,1}$ is not zero:

• make a step of the gaussian elimination
• Set matrix N of size (n - 1) x (m - 1) as the matrix M without the first row and column
• calculate the rank of matrix N, the rank of matrix M will be rank(N) + 1
• If $M_{1,1}$ is zero:

• Set matrix N of size n x (m - 1) as the matrix M without the first column
• calculate the rank of matrix N, the rank of matrix M will be rank(N).

Is this recursive algorithm right?

-
No glaring errors in the pseudocode you give here, except that you're not actually presenting any base cases -- there might be all sorts of problems in your implementation of it, of course. Have you tried logging out the intermediate matrices of a run that gives a wrong result, to find out whether they correspond to hand calculations? – Henning Makholm Apr 10 '12 at 21:05
well the matrices it does fail with are of size 18 x 8, so posting an example isn't really nice. I assume it's a problem with the "not zero" check, but I don't get it. I know about "numerically zero" so I actually check if the pivot element is in the range of (- 1e-12, 1e-12 ), so afaik this should be good – stefan Apr 10 '12 at 21:33
i found the mistake. it was a sign error in the method finding the pivot element. how pathetic :D thanks for your effort in helping me :) – stefan Apr 10 '12 at 21:36
– Zev Chonoles Apr 11 '12 at 0:47