Apr 24, 2013

Tutorial: Determinant of a Matrix in Java

Calculating the determinant of a quadratic matrix A=(a_ij) of size n using Laplace's formula with expanding along the i-th row is given by
where A_ij is the so-called minor (it is A with the i-th row and j-th column removed). Note that it is a recursive definition; it terminates since the size of the matrices decreases and the determinant of a number is the number itself.

In Java it can be implemented like this (for i=1, i.e. the first row):

package de.bigdev;

public class Determinant {

    /**
     * Determinant of a matrix using Laplace's formula with expanding along the
     * 0th row. It is not checked whether the matrix is quadratic!
     * 
     * @param m Matrix
     * @return determinant
     */
    public static double det(double[][] m) {
        int n = m.length;
        if (n == 1) {
            return m[0][0];
        } else {
            double det = 0;
            for (int j = 0; j < n; j++) {
                det += Math.pow(-1, j) * m[0][j] * det(minor(m, 0, j));
            }
            return det;
        }
    }

    /**
     * Computing the minor of the matrix m without the i-th row and the j-th
     * column
     * 
     * @param m input matrix
     * @param i removing the i-th row of m
     * @param j removing the j-th column of m
     * @return minor of m
     */
    private static double[][] minor(final double[][] m, final int i, final int j) {
        int n = m.length;
        double[][] minor = new double[n-1][n-1];
        // index for minor matrix position:
        int r = 0, s = 0;
        for (int k = 0; k < n; k++) {
            double[] row = m[k];
            if (k != i) {
                for (int l = 0; l < row.length; l++) {
                    if (l != j) {
                        minor[r][s++] = row[l];
                    }
                }
                r++;
                s = 0;
            }
        }
        return minor;
    }

    private static void printMatrix(double[][] m) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m.length; i++) {
            double[] row = m[i];
            sb.append("[");
            for (int j = 0; j < row.length; j++) {
                sb.append(" ");
                sb.append(row[j]);
            }
            sb.append(" ]\n");
        }
        sb.deleteCharAt(sb.length() - 1);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        System.out.println("Determinant");
        System.out.println("===========");
        
        double[][] a = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 0 } };
        double[][] b = { { 1 } };
        double[][] c = { { 1, 2 }, { 3, 4 } };
        
        System.out.println("");
        System.out.println("Testing minor");
        System.out.println("=============");
        printMatrix(a);
        System.out.println("deleting row 3, and column 2:");
        printMatrix(minor(a, 2, 1));

        System.out.println("");
        System.out.println("Testing det");
        System.out.println("===========");
        
        printMatrix(b);
        System.out.println("has det=" + det(b) +"\n");
        
        printMatrix(c);
        System.out.println("has det=" + det(c) +"\n");
        
        printMatrix(a);
        System.out.println("has det=" + det(a) +"\n");
    }
}

You get following output on the console:


Determinant
===========

Testing minor
=============
[ 1.0 2.0 3.0 ]
[ 4.0 5.0 6.0 ]
[ 7.0 8.0 0.0 ]
deleting row 3, and column 2:
[ 1.0 3.0 ]
[ 4.0 6.0 ]

Testing det
===========
[ 1.0 ]
has det=1.0

[ 1.0 2.0 ]
[ 3.0 4.0 ]
has det=-2.0

[ 1.0 2.0 3.0 ]
[ 4.0 5.0 6.0 ]
[ 7.0 8.0 0.0 ]
has det=27.0

No comments:

Post a Comment