Laplace Expansion

This is a discussion on Laplace Expansion within the C Programming forums, part of the General Programming Boards category; Hi folks, I've been trying to develop a piece of code that will calculate the determinant of an n*n matrix...I ...

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    103

    Laplace Expansion

    Hi folks,
    I've been trying to develop a piece of code that will calculate the determinant of an n*n matrix...I managed to develop the function that returns the minor of the matrix, that is the sub matrix without the sent row and column.
    Yet, the recursive function that calculates the determinant doesn't seem to work. the program ends right after displaying the original matrix.
    Here is the code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    int power(int , int); /*Prototype of the function that calculates the power.*/
    int **minor(int** , int , int); /*Prototype of the function that determines the minor of the matrix. */ 
    int det(int **, int, int); /*Prototype of the recursive function that calculates the determinant of the matrix*/
    int main(){
               int order; /* The order of the matrix*/
               int element; /*The element of which the minor will be calculated*/
               char answer; /*The reexecution directive*/
               do{
                  printf("The following program calculates the determant of a matrix.\n\n");
                  printf("First, Enter the order of your matrix:");
                  scanf("%d",&order); /*Reading the order from the user*/
                  int **matrix = (int **)malloc(sizeof(int *) * (order)); /*allocating memory for the matrix*/
                  for (int i = 0; i < order ; i++) 
                           matrix[i] = (int *)malloc((order) * sizeof(int));
                  printf("Now, you will fill your %d * %d matrix.\n",order,order);
                  for (int i = 0 ; i < order ; i++){  /*Filling the Matrix*/
                           for (int j = 0 ; j < order ; j++){
                               printf("Enter the element corresponding to the position [%d][%d]:",i,j);
                               scanf("%d",&matrix[i][j]);
                               }
                      }
                  printf("Your matrix is now completely filled as the following:\n\n");
                  for (int i = 0 ; i < order ; i++){  /*Displaying the matrix*/
                           for (int j = 0 ; j < order ; j++)
                               printf("\t%d  ",matrix[i][j]);
                           printf("\n");
                      }
                  int x = det(matrix, order, matrix[0][0]);
                  printf("The determinant is %d.",x);
                  printf("\nRun the program again?\n");
                  printf("(1 for yes, any other key for no):");
                  scanf(" %c",&answer);
                  }while(answer == '1');
               printf("\n\n\t\t\tEnd of Program. Bye\n");
               printf("\n\t\t\t");
               system("PAUSE");
               return 0;
        }
    int power(int a, int b){
                            int result;
                            if (!b)
                                   result = 1;
                            else
                                result = a * power(a, b - 1); 
                            return result;
        }
    int **minor(int **matrix, int order, int element){
                                                      int **submatrix = (int **)malloc(sizeof(int *) * (order - 1)); /*allocating memory for the submatrix*/
                                                      for (int i = 0; i < order - 1 ; i++) 
                                                               submatrix[i] = (int *)malloc((order - 1) * sizeof(int));
                                                      int row = -1, column = -1,exit_loop = 0;
                                                      for (int i = 0 ; i < order ; i++){  /*Getting the exact position of the element*/
                                                          for (int j = 0 ; j < order ; j++)
                                                              if (element == matrix[i][j]){
                                                                           row = i;
                                                                           column = j;
                                                                           exit_loop = 1;
                                                                           break;
                                                                           }
                                                          if(exit_loop)
                                                                       break;
                                                      }
                                                      int row2 = 0;
                                                      int column2 = 0;
                                                      int i = 0, j= 0;
                                                      while(row2 < order){   /*Copying the original matrix to the sub matrix (minor)*/
                                                                    if (row2 != row){
                                                                                    while(column2 < order){
                                                                                                  if(column2 != column)
                                                                                                             submatrix[i][j++] = matrix[row2][column2];
                                                                                                  column2++;
                                                                          }
                                                                    i++;
                                                                    }
                                                                    row2++;
                                                                    column2 = 0;
                                                                    j = 0;      
                                                                 }
                                                      return submatrix; /*Returning the submatrix*/
    
        }
    int det(int **x, int order, int index){
                                int sum = 0;
                                if(order == 1)
                                              sum = x[0][0];
                                sum = power(-1,x[0][index]) * x[0][index] * det((minor(x, order - 1, x[0][index])), order - 1, ++index);
                                return sum;
        
        }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Things that stick out: In your det function, do you really want to do the sum line in the base case? Shouldn't that be in an else? Also (-1)^index is not the same as (-1)^(x[0][index]). And your det should add a bunch of things up; right now it just does the (0,0) element.

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    I've added an else to separate the base case from the general case...
    Yet, nothing changed. I didn't understand your sentence about power function tough.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You are computing (-1)^(number in the matrix in the 0,index spot). Unfortunately, that appears nowhere in the formula for the determinant. What does appear is (-1)^index.

  5. #5
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    Ok, I see now what you meant!! here is an updated code:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    int power(int , int); /*Prototype of the function that calculates the power.*/
    int **minor(int** , int , int); /*Prototype of the function that determines the minor of the matrix. */ 
    int det(int **, int, int); /*Prototype of the recursive function that calculates the determinant of the matrix*/
    int main(){
               int order; /* The order of the matrix*/
               int element; /*The element of which the minor will be calculated*/
               char answer; /*The reexecution directive*/
               do{
                  printf("The following program calculates the determant of a matrix.\n\n");
                  printf("First, Enter the order of your matrix:");
                  scanf("&#37;d",&order); /*Reading the order from the user*/
                  int **matrix = (int **)malloc(sizeof(int *) * (order)); /*allocating memory for the matrix*/
                  for (int i = 0; i < order ; i++) 
                           matrix[i] = (int *)malloc((order) * sizeof(int));
                  printf("Now, you will fill your %d * %d matrix.\n",order,order);
                  for (int i = 0 ; i < order ; i++){  /*Filling the Matrix*/
                           for (int j = 0 ; j < order ; j++){
                               printf("Enter the element corresponding to the position [%d][%d]:",i,j);
                               scanf("%d",&matrix[i][j]);
                               }
                      }
                  printf("Your matrix is now completely filled as the following:\n\n");
                  for (int i = 0 ; i < order ; i++){  /*Displaying the matrix*/
                           for (int j = 0 ; j < order ; j++)
                               printf("\t%d  ",matrix[i][j]);
                           printf("\n");
                      }
                  int x = det(matrix, order, 0);
                  printf("%d",x);
                  printf("\nRun the program again?\n");
                  printf("(1 for yes, any other key for no):");
                  scanf(" %c",&answer);
                  }while(answer == '1');
               printf("\n\n\t\t\tEnd of Program. Bye\n");
               printf("\n\t\t\t");
               system("PAUSE");
               return 0;
        }
    int power(int a, int b){
                            int result;
                            if (!b)
                                   result = 1;
                            else
                                result = a * power(a, b - 1); 
                            return result;
        }
    int **minor(int **matrix, int order, int element){
                                                      int **submatrix = (int **)malloc(sizeof(int *) * (order - 1)); /*allocating memory for the submatrix*/
                                                      for (int i = 0; i < order - 1 ; i++) 
                                                               submatrix[i] = (int *)malloc((order - 1) * sizeof(int));
                                                      int row = -1, column = -1,exit_loop = 0;
                                                      for (int i = 0 ; i < order ; i++){  /*Getting the exact position of the element*/
                                                          for (int j = 0 ; j < order ; j++)
                                                              if (element == matrix[i][j]){
                                                                           row = i;
                                                                           column = j;
                                                                           exit_loop = 1;
                                                                           break;
                                                                           }
                                                          if(exit_loop)
                                                                       break;
                                                      }
                                                      int row2 = 0;
                                                      int column2 = 0;
                                                      int i = 0, j= 0;
                                                      while(row2 < order){   /*Copying the original matrix to the sub matrix (minor)*/
                                                                    if (row2 != row){
                                                                                    while(column2 < order){
                                                                                                  if(column2 != column)
                                                                                                             submatrix[i][j++] = matrix[row2][column2];
                                                                                                  column2++;
                                                                          }
                                                                    i++;
                                                                    }
                                                                    row2++;
                                                                    column2 = 0;
                                                                    j = 0;      
                                                                 }
                                                      return submatrix; /*Returning the submatrix*/
    
        }
    int det(int **x, int order, int index){
                                int sum = 0;
                                if(order == 1)
                                              sum = x[0][0];
                                else
                                    sum = power(-1,x[0][index]) * x[0][index] * det((minor(x, order - 1, x[0][index])), order - 1, ++index);
                                return sum;
        
        }
    Still the problem persists...

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You don't appear to have changed much.

    Anyway, put some debugging printf's in your functions and see how far you get. I'm guessing you run yourself out of memory at some point.

  7. #7
    Registered User
    Join Date
    Apr 2008
    Posts
    103
    I have put a printf right after the else statement, the text appeared, but I get an error: the memory couldn't be read.why?

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,532
    How about indentation?

    How does this compare
    - to what you've posted above?
    - to what you actually see in your IDE?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int power(int , int); /*Prototype of the function that calculates the power.*/
    int **minor(int** , int , int); /*Prototype of the function that determines the minor of the matrix. */ 
    int det(int **, int, int); /*Prototype of the recursive function that calculates the determinant of the matrix*/
    
    int main(){
        int order; /* The order of the matrix*/
        int element; /*The element of which the minor will be calculated*/
        char answer; /*The reexecution directive*/
    
        do{
            printf("The following program calculates the determant of a matrix.\n\n");
            printf("First, Enter the order of your matrix:");
            scanf("%d",&order); /*Reading the order from the user*/
    
            int **matrix = (int **)malloc(sizeof(int *) * (order)); /*allocating memory for the matrix*/
            for (int i = 0; i < order ; i++) 
                matrix[i] = (int *)malloc((order) * sizeof(int));
    
            printf("Now, you will fill your %d * %d matrix.\n",order,order);
            for (int i = 0 ; i < order ; i++){  /*Filling the Matrix*/
                for (int j = 0 ; j < order ; j++){
                    printf("Enter the element corresponding to the position [%d][%d]:",i,j);
                    scanf("%d",&matrix[i][j]);
                }
            }
    
            printf("Your matrix is now completely filled as the following:\n\n");
            for (int i = 0 ; i < order ; i++){  /*Displaying the matrix*/
                for (int j = 0 ; j < order ; j++)
                    printf("\t%d  ",matrix[i][j]);
                printf("\n");
            }
    
            int x = det(matrix, order, 0);
            printf("%d",x);
    
            printf("\nRun the program again?\n");
            printf("(1 for yes, any other key for no):");
            scanf(" %c",&answer);
        }while(answer == '1');
    
        printf("\n\n\t\t\tEnd of Program. Bye\n");
        printf("\n\t\t\t");
        system("PAUSE");
        return 0;
    }
    
    int power(int a, int b){
        int result;
        if (!b)
            result = 1;
        else
            result = a * power(a, b - 1); 
        return result;
    }
    
    int **minor(int **matrix, int order, int element){
        int **submatrix = (int **)malloc(sizeof(int *) * (order - 1)); /*allocating memory for the submatrix*/
        for (int i = 0; i < order - 1 ; i++) 
            submatrix[i] = (int *)malloc((order - 1) * sizeof(int));
    
        int row = -1, column = -1,exit_loop = 0;
        for (int i = 0 ; i < order ; i++){  /*Getting the exact position of the element*/
            for (int j = 0 ; j < order ; j++)
            if (element == matrix[i][j]){
                row = i;
                column = j;
                exit_loop = 1;
                break;
            }
            if(exit_loop)
            break;
        }
    
        int row2 = 0;
        int column2 = 0;
        int i = 0, j= 0;
        while(row2 < order){   /*Copying the original matrix to the sub matrix (minor)*/
            if (row2 != row){
                while(column2 < order){
                    if(column2 != column)
                        submatrix[i][j++] = matrix[row2][column2];
                    column2++;
                }
                i++;
            }
            row2++;
            column2 = 0;
            j = 0;      
        }
        return submatrix; /*Returning the submatrix*/
    
    }
    
    int det(int **x, int order, int index){
        int sum = 0;
        if(order == 1)
            sum = x[0][0];
        else
            sum = power(-1,x[0][index]) * 
                  x[0][index] * 
                  det( (minor(x, order - 1, x[0][index])), order - 1, ++index);
        return sum;
    }
    Oh, and check the red code at the end.
    Your ++ has a really good chance of screwing up the indices of the rest of the expression.
    Try index+1 and have a completely safe and predictable expression.

    Oh, and one more thing, use more { } in the places where you're relying on the single statement behaviour of for() and if(). You can just about get away with it in a well indented program, but with poor indentation, it's a disaster waiting to happen.

    Finally, read the FAQ on casting malloc.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Macro expansion
    By onebrother in forum C Programming
    Replies: 1
    Last Post: 11-02-2007, 03:08 AM
  2. Replies: 1
    Last Post: 08-02-2006, 09:45 AM
  3. expected primary expansion before ')' token.
    By agent d00nut in forum C++ Programming
    Replies: 10
    Last Post: 11-06-2005, 04:54 AM
  4. taylor series expansion
    By noor_mirza in forum C++ Programming
    Replies: 1
    Last Post: 10-23-2002, 10:02 PM
  5. Expansion
    By Generator in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 10-02-2001, 05:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21