06 Mai 2021

Determinanten mit Java berechnen

Neulich musste ich in einem Program Determinanten berechnen. Für 2x2 und 3x3 Matrizen gibt es viele passende Codebeispiele im Netz. Bei einer 4x4 Matrix oder noch größeren findet sich kaum etwas. Also habe ich selbst eine Funktion geschrieben, die die Determinante für beliebige Matrixgrößen berechnen kann und welche ich euch im Folgenden vorstelle.

Die Funktion entwichelt die Determinante nach der ersten Spalte. Es hat bei einer nxn-Matrix eine Laufzeit von 𝒪(n²). Genutzt werden kann es wie folgt (am Beispiel der 4x4 Einheitsmatrix):

double[][] m = new double[][] { { 1, 0, 0, 0 }, { 0, 1, 0, 0 }, { 0, 0, 1, 0 }, { 0, 0, 0, 1 } };
System.out.println(Det.det(m));

Das eigentliche Program sieht wie im Folgenden aus. Ihr dürft es euch gerne unter der MIT-Lizenz kopieren und in euren eigenen Projekten verwenden. Bitte achtet darauf, dass ihr eine quadratische Matrix eingebt. Eine nichtquadratische Matrix oder ein Array, wo die Zeilen unterschiedlich lang sind, quittiert das Program mit einer IllegalArgumentException.

/**
 * Calculates the determinate of a square matrix.
 * 
 * @author Björn Beckendorf, 2021
 */
/*
 * Copyright (c) 2021 Björn Beckendorf
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

public class Det {
	/**
	 * Calculates the determinate of a square matrix
	 * 
	 * @param m The matrix to calculate the determinate of
	 * @return The determinate of <em>m</em>
	 * @throws IllegalArgumentException if <em>m</em> is not square
	 */
	public static double det(double[][] m) {
		for (double[] row : m) {
			if (row.length != m.length) {
				throw new IllegalArgumentException("Given matrix is not square");
			}
		}
		boolean incl[] = new boolean[m.length];
		for (int i = 0; i < m.length; i++)
			incl[i] = true;
		return _det(m, 0, incl);
	}

	private static double _det(double[][] m, int curCol, boolean[] rowsIncl) {
		if (m.length == curCol + 1) {
			for (int i = 0; i < m.length; i++) {
				if (rowsIncl[i]) {
					return m[curCol][i];
				}
			}
		}
		int sign = 1;
		double det = 0.0;
		for (int i = 0; i < m.length; i++) {
			if (rowsIncl[i]) {
				rowsIncl[i] = false;
				det += sign * m[curCol][i] * _det(m, curCol + 1, rowsIncl);
				rowsIncl[i] = true;
				sign *= -1;
			}
		}
		return det;
	}
}