Determinant of a Square Matrix

Written by Paul Bourke
June 2001


The determinant of an n by n matrix will be written as follows
det(A) = |A| =
a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a3n
: : : aij :
an1 an2 an3 . . . ann

The solution is given by the so called "determinant expansion by minors". A minor Mij of the matrix A is the n-1 by n-1 matrix made by the rows and columns of A except the i'th row and the j'th column is not included. So for example M12 for the matrix A above is given below

M12 =
a21 a23 a24 . . . a2n
a31 a33 a34 . . . a3n
a41 a43 a44 . . . a4n
: : : aij, i!=1, j!=2 :
an1 an3 an4 . . . ann

The determinant is the given by the following where the sum is taken over a single row or column.

|A| = (-1)i+j aij Mij

Any row or column can be chosen across which to take the sum, when computing manually the row or column with the most zeros is chosen to minimise the amount of work. If the first row is chosen for the sum then the determinant in terms of the minors would be

|A| = a11 M11 - a12 M12 + a13 M13 - . . . + a1n M1n
Or expanded out as follows.
|A| = a11
a22 a23 a24 . . . a2n
a32 a33 a34 . . . a3n
a42 a43 a44 . . . a4n
: : : . . . :
an2 an3 an4 . . . ann
- a12
a21 a23 a24 . . . a2n
a31 a33 a34 . . . a3n
a41 a43 a44 . . . a4n
: : : . . . :
an1 an3 an4 . . . ann
+ a13
a21 a22 a24 . . . a2n
a31 a32 a34 . . . a3n
a41 a42 a44 . . . a4n
: : : . . . :
an1 an2 an4 . . . ann

. . . . . + a1n
a21 a22 a23 . . . a2(n-1)
a31 a32 a33 . . . a3(n-1)
a41 a42 a43 . . . a4(n-1)
: : : . . . :
an1 an2 an3 . . . an(n-1)

The process is repreated for each of the determinants above, on each expansion the dimension of the determinant in each term decreases by 1. When the terms are 2 by 2 matrices the determinant is given as

a11 a12
a21 a22
= a11 a22 - a12 a21

If the determinant is 0 the matrix said to be "singular". A singular matrix either has izero elements in an entire row or column, or else a row (or column) is a linear combination of other rows (or columns).

C source code example
/*
   Recursive definition of determinate using expansion by minors.
*/
double Determinant(double **a,int n)
{
   int i,j,j1,j2;
   double det = 0;
   double **m = NULL;

   if (n < 1) { /* Error */

   } else if (n == 1) { /* Shouldn't get used */
      det = a[0][0];
   } else if (n == 2) {
      det = a[0][0] * a[1][1] - a[1][0] * a[0][1];
   } else {
      det = 0;
      for (j1=0;j1<n;j1++) {
         m = malloc((n-1)*sizeof(double *));
         for (i=0;i<n-1;i++)
            m[i] = malloc((n-1)*sizeof(double));
         for (i=1;i<n;i++) {
            j2 = 0;
            for (j=0;j<n;j++) {
               if (j == j1)
                  continue;
               m[i-1][j2] = a[i][j];
               j2++;
            }
         }
         det += pow(-1.0,1.0+j1+1.0) * a[0][j1] * Determinant(m,n-1);
         for (i=0;i<n-1;i++)
            free(m[i]);
         free(m);
      }
   }
   return(det);
}
Contribution by Edward Popko, a well commented version: determinant.c for Microsoft C++ Visual Studio 6.0.




Inverse of a square matrix

Written by Paul Bourke
August 2002

See also: Determinant of a Square Matrix



The inverse of a square matrix A with a non zero determinant is the adjoint matrix divided by the determinant, this can be written as

 
1
 
A-1 =
 adj(A)
 
det(A)
 

The adjoint matrix is the transpose of the cofactor matrix. The cofactor matrix is the matrix of determinants of the minors Aij multiplied by -1i+j. The i,j'th minor of A is the matrix A without the i'th column or the j'th row.

Example (3x3 matrix)

The following example illustrates each matrix type and at 3x3 the steps can be readily calculated on paper. It can also be verified that the original matrix A multipled by its inverse gives the identity matrix (all zeros except along the diagonal which are ones).

A =
  1  
  2  
  0  
  -1  
  1  
  1  
  1  
  2  
  3  

Determinant = 9

Cofactor matrix =   
  
  +
  1  
  1  
  2  
  3  
  
  
  -
  -1  
  1  
  1  
  3  
  
  
  +
  -1  
  1  
  1  
  2  
  
  
  -
  2  
  0  
  2  
  3  
  
  
  +
  1  
  0  
  1  
  3  
  
  
  -
  1  
  2  
  1  
  2  
  
  
  +
  2  
  0  
  1  
  1  
  
  
  -
  1  
  0  
  -1  
  1  
  
  
  +
  1  
  2  
  -1  
  1  
  
       =  
  1  
  4  
  -3  
  -6  
  3  
  -0  
  2  
  -1  
  3  

Adjoint matrix = Transpose of cofactor matrix =
  1  
  -6  
  2  
  4  
  3  
  -1  
  -3  
  -0  
  3  

A-1 = Inverse of A =
  1/9  
  -6/9  
  2/9  
  4/9  
  3/9  
  -1/9  
  -3/9  
  0  
  3/9  

A A-1 =
  1  
  0  
  0  
  0  
  1  
  0  
  0  
  0  
  1  

Inverse of a 2x2 matrix

The inverse of a 2x2 matrix can be written explicitly, namely

  a  
  b  
  c  
  d  
 = 
1
  
ad - bc
  d  
  -b  
  -c  
  a  
Source code

The three functions required are the determinant, cofactor, and transpose. Examples of these are given below.

/*
   Recursive definition of determinate using expansion by minors.
*/
double Determinant(double **a,int n)
{
   int i,j,j1,j2;
   double det = 0;
   double **m = NULL;

   if (n < 1) { /* Error */

   } else if (n == 1) { /* Shouldn't get used */
      det = a[0][0];
   } else if (n == 2) {
      det = a[0][0] * a[1][1] - a[1][0] * a[0][1];
   } else {
      det = 0;
      for (j1=0;j1<n;j1++) {
         m = malloc((n-1)*sizeof(double *));
         for (i=0;i<n-1;i++)
            m[i] = malloc((n-1)*sizeof(double));
         for (i=1;i<n;i++) {
            j2 = 0;
            for (j=0;j<n;j++) {
               if (j == j1)
                  continue;
               m[i-1][j2] = a[i][j];
               j2++;
            }
         }
         det += pow(-1.0,j1+2.0) * a[0][j1] * Determinant(m,n-1);
         for (i=0;i<n-1;i++)
            free(m[i]);
         free(m);
      }
   }
   return(det);
}

/*
   Find the cofactor matrix of a square matrix
*/
void CoFactor(double **a,int n,double **b)
{
   int i,j,ii,jj,i1,j1;
   double det;
   double **c;

   c = malloc((n-1)*sizeof(double *));
   for (i=0;i<n-1;i++)
     c[i] = malloc((n-1)*sizeof(double));

   for (j=0;j<n;j++) {
      for (i=0;i<n;i++) {

         /* Form the adjoint a_ij */
         i1 = 0;
         for (ii=0;ii<n;ii++) {
            if (ii == i)
               continue;
            j1 = 0;
            for (jj=0;jj<n;jj++) {
               if (jj == j)
                  continue;
               c[i1][j1] = a[ii][jj];
               j1++;
            }
            i1++;
         }

         /* Calculate the determinate */
         det = Determinant(c,n-1);

         /* Fill in the elements of the cofactor */
         b[i][j] = pow(-1.0,i+j+2.0) * det;
      }
   }
   for (i=0;i<n-1;i++)
      free(c[i]);
   free(c);
}

/*
   Transpose of a square matrix, do it in place
*/
void Transpose(double **a,int n)
{
   int i,j;
   double tmp;

   for (i=1;i<n;i++) {
      for (j=0;j<i;j++) {
         tmp = a[i][j];
         a[i][j] = a[j][i];
         a[j][i] = tmp;
      }
   }
}