[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?
Best Answer
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.