7

I'm new to programming and I was looking for a way to find the determinant of a matrix. I found this code online, but I have trouble understanding the algorithm in place here. I have no problems for the base of the recursion , but the continue and main loop I have trouble understanding. Big thanks to anyone who can explain to me the algorithm.

int determ(int a[MAX][MAX],int n) {
  int det=0, p, h, k, i, j, temp[MAX][MAX];
  if(n==1) {
    return a[0][0];
  } else if(n==2) {
    det=(a[0][0]*a[1][1]-a[0][1]*a[1][0]);
    return det;
  } else {
    for(p=0;p<n;p++) {
      h = 0;
      k = 0;
      for(i=1;i<n;i++) {
        for( j=0;j<n;j++) {
          if(j==p) {
            continue;
          }
          temp[h][k] = a[i][j];
          k++;
          if(k==n-1) {
            h++;
            k = 0;
          }
        }
      }
      det=det+a[0][p]*pow(-1,p)*determ(temp,n-1);
    }
    return det;
  }
}
Benjamin Bannier
  • 55,163
  • 11
  • 60
  • 80
user3144334
  • 135
  • 1
  • 1
  • 9
  • 6
    It calculates the determinant from minors. The inner cycle forms minors in `temp`. Also, that's a horrible way to calculate the determinant. – Joker_vD Jan 19 '14 at 18:05
  • @user3144334 The minor is a matrix with one row and one column tossed away. The minors used here are all with the first row tossed out, and to toss the `p`th column, you have to skip it while copying the elements from `a` to `temp` – Joker_vD Jan 19 '14 at 18:36
  • 1
    Computing the determinant with a super-exponential complexity, well done... and even a `pow(-1,p)` to make it obvious at a glance how nice the code is... – Marc Glisse Jan 19 '14 at 18:45

2 Answers2

7

This algorithm uses a divide-conquer approach for solving the problem (finding the determinant of an N*N Matrix).

The algorithm uses a recursive pattern which is one of divide and conquer approaches. You can find out this by noticing the algorithm is calling itself in the third condition statement.

Every recursive algorithm have an exit condition which is the first if-statement in your code. and they also contain a section which is the solution to the most convenient problem or an atomic problem of the main big problem which is hard to solve in the first place. The atomic problem or the most-divided problem can be solved easily as you can see the the second if-statement of your code. In your case it is actually solving the determinant of a 2*2 Matrix.

The most important part of your code to understand which is challenging a little bit too is the part you do the dividing (which is recursive too!). This part has the key to conquering either. By doing a little back trace and numerical examples you can find it out:

det = det + a[0][p] * pow(-1,p) * determ(temp,n-1);

For the final suggestion try a 3*3 Matrix which only needs one dividing. Good luck with that.

This book is a great one to start studying and understanding algorithms

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Novin Shahroudi
  • 620
  • 8
  • 18
  • Thanks a lot I only want to ask what the continue statement does? if j == p then you skip right ahead to det=det+a[0][p]*pow(-1,p)*determ(temp,n-1); or something else ? – user3144334 Jan 19 '14 at 18:37
  • @user3144334 Oh, you just don't know what `continue` does... `for (...) { if (x) { continue; } b; c; }` is equivalent to `for (...) { if (!x) { b; c; } }`. – Joker_vD Jan 19 '14 at 18:45
  • It continues the 'for' loop for one more execution. check this out: http://www.cplusplus.com/doc/tutorial/control/ - continue can be used in all statements which have condition: http://www.tutorialspoint.com/cplusplus/cpp_continue_statement.htm – Novin Shahroudi Jan 19 '14 at 18:46
0
#include <iostream>

using std::cin;
using std::cout;
using std::endl;

int **submatrix(int **matrix, unsigned int n, unsigned int x, unsigned int y) {
    int **submatrix = new int *[n - 1];
    int subi = 0;
    for (int i = 0; i < n; i++) {
        submatrix[subi] = new int[n - 1];
        int subj = 0;
        if (i == y) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if (j == x) {
                continue;
            }
            submatrix[subi][subj] = matrix[i][j];
            subj++;
        }
        subi++;
    }
    return submatrix;
}

int determinant(int **matrix, unsigned int n) {
    int det = 0;
    if (n == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[1][0] * matrix[0][1];
    }
    for (int x = 0; x < n; ++x) {
        det += ((x % 2 == 0 ? 1 : -1) * matrix[0][x] * determinant(submatrix(matrix, n, x, 0), n - 1));
    }

    return det;
}

int main() {
    int n;
    cin >> n;
    int **matrix = new int *[n];
    for (int i = 0; i < n; ++i) {
        matrix[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    cout << determinant(matrix, n);

    return 0;
}
sav0I
  • 1