dimanche 1 janvier 2017

Determinant of random matrix nearly always zero

Hello and happy new year.

I implemented a matrix class, and one static method is to create a random matrix.

It's fairly simple and seems to work

public static Matrix random(int m, int n)
{
    Random r = new Random();
    Matrix rndMatrix = new Matrix(m, n);
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            rndMatrix.setEntry(Math.random(), i, j);
        }
    }
    return rndMatrix;
}

The members of a matrix object are the various methods, 2 integers that represent number of rows and columns, and a double[][] that represents the data.

I also implemented a method that calculates the determinant of a given matrix.

It's rather complex but this is the code

public double determinant() throws RuntimeException // Via Gauss elimination. O(n^3)
{
    int m, n;
    double det = 1;
    m = this.getDimensions()[0];
    n = this.getDimensions()[1];

    if(m != n) // not a square matrix
    {
        System.out.println("determinant given non square matrix");
        RuntimeException e = new RuntimeException();
        throw e;
    }

    Matrix copy = new Matrix(this); // work on a copy, don't change original

    for(int i = 0; i < m-1; i++) // pivot row (and column) is i
    {
        double maxPivot = Math.abs(copy.getEntry(i, i));
        int maxPivotRow = i;
        for(int j = 1; j < m; j++) // perform partial pivoting for numerical stability
        {
            double potentialPivot = copy.getEntry(j, i);
            if(Math.abs(potentialPivot) > maxPivot)
            {
                maxPivot = potentialPivot;
                maxPivotRow = j;
            }
        } //now our pivot is at copy[maxPivotRow][i]

        if(maxPivotRow != i) //need to swap rows
        {
            det *= -1; //each row swap changes sign of determinant

            for(int j = 0; j < m; j++) //change row i and row maxPivotRow. j runs on columns
            {
                double temp = copy.getEntry(i, j);
                copy.setEntry(copy.getEntry(maxPivotRow, j), i, j);
                copy.setEntry(temp, maxPivotRow, j);
            } // now our pivot is at copy[i][i]
        }

        if(copy.getEntry(i, i) == 0) //Pivot is 0, meaning determinant is 0
            return det;

        for(int j = i + 1; j < m; j++) // rank!
        {
            double coefficient = copy.getEntry(j, i) / copy.getEntry(i, i);
            for(int k = i; k < m; k++)
            {
                double currentElement = copy.getEntry(j, k);
                copy.setEntry(currentElement - coefficient * copy.getEntry(i, k), j, k);
            }
        } 
    }// copy is now row reduced, upper triangular. determinant is product of diagonal

    for(int i = 0; i < m; i++)
    {
        det *= copy.getEntry(i, i);
    }

    return det;
}

the calculation is done via gaussian elimination (with partial pivoting) and then multiplying the elements on the diagonal. I have tested it several times and it seems to work.

the problem is that it doesn't work on random matrices, or well, I'm getting an unexpected behavior.

9 out of 10 times i'll create a random matrix and calculate its determinant, it will print 0.0 or -0.0.

This seems odd. "Most" matrices are invertible. So why does this happen? Is there a bug? Do I not understand the math?




Aucun commentaire:

Enregistrer un commentaire