Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

[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?

share|improve this question
    
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
1  
add comment

1 Answer 1

up vote 0 down vote accepted

The algorithm itself is right, there was only a little mistake in the pivot element search.

The validity of this algorithm can be shown via induction. Here are arguments to support the statement (not a full and clean proof):

For an arbitrary ( n x 1 )- Matrix, the rank is 1 if and only if there is at least one non-zero entry.

For an (n x m )-Matrix the gaussian elimination will produce an empty column if and only if the rank of the matrix is not maximal.

Searching for the pivot element asserts that the gaussian elimination is valid.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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