Как найти определитель матрицы java

Предположим, что дан двумерный массив

int a[][]=new int[4][4];

я пытаюсь найти определитель матриц, пожалуйста, помогите, я знаю, как найти его математическим, но я пытаюсь найти его программно, я использую язык Java и C#, но в этом случае я думаю, что C++ будет также полезным

Если вы установили 4×4, самым простым решением было бы просто жестко закодировать формулу.

public double determinant(int[][] m) {
  return

  m[0][3] * m[1][2] * m[2][1] * m[3][0] - m[0][2] * m[1][3] * m[2][1] * m[3][0] -
  m[0][3] * m[1][1] * m[2][2] * m[3][0] + m[0][1] * m[1][3] * m[2][2] * m[3][0] +
  m[0][2] * m[1][1] * m[2][3] * m[3][0] - m[0][1] * m[1][2] * m[2][3] * m[3][0] -
  m[0][3] * m[1][2] * m[2][0] * m[3][1] + m[0][2] * m[1][3] * m[2][0] * m[3][1] +
  m[0][3] * m[1][0] * m[2][2] * m[3][1] - m[0][0] * m[1][3] * m[2][2] * m[3][1] -
  m[0][2] * m[1][0] * m[2][3] * m[3][1] + m[0][0] * m[1][2] * m[2][3] * m[3][1] +
  m[0][3] * m[1][1] * m[2][0] * m[3][2] - m[0][1] * m[1][3] * m[2][0] * m[3][2] -
  m[0][3] * m[1][0] * m[2][1] * m[3][2] + m[0][0] * m[1][3] * m[2][1] * m[3][2] +
  m[0][1] * m[1][0] * m[2][3] * m[3][2] - m[0][0] * m[1][1] * m[2][3] * m[3][2] -
  m[0][2] * m[1][1] * m[2][0] * m[3][3] + m[0][1] * m[1][2] * m[2][0] * m[3][3] +
  m[0][2] * m[1][0] * m[2][1] * m[3][3] - m[0][0] * m[1][2] * m[2][1] * m[3][3] -
  m[0][1] * m[1][0] * m[2][2] * m[3][3] + m[0][0] * m[1][1] * m[2][2] * m[3][3];
}

Для общего NxN задача значительно сложнее, с различными алгоритмами в порядке O(N!), O(N^3), так далее.

Рекомендации

• Wikipedia/ Определитель
• EuclidianSpace.com/Determinant 4×4 формула

Смежные вопросы

• Как найти определитель большой матрицы
• какой алгоритм определения матрицы наилучший
• Вычисление определителя матрицы NxN в C#

static double DeterminantGaussElimination(double[,] matrix)
{
    int n = int.Parse(System.Math.Sqrt(matrix.Length).ToString());
    int nm1 = n - 1;
    int kp1;
    double p;
    double det=1;
    for (int k = 0; k < nm1; k++)
    {
        kp1 = k + 1;
        for(int i=kp1;i<n;i++)
        {
            p = matrix[i, k] / matrix[k, k];
            for (int j = kp1; j < n; j++)
                matrix[i, j] = matrix[i, j] - p * matrix[k, j];
        }
    }
    for (int i = 0; i < n; i++)
        det = det * matrix[i, i];
    return det;

}

Этот метод не обязательно работает, так как вам нужно разделить на элемент вашей матрицы, если элемент вашей матрицы равен 0, вы можете получить результат det = NaN.

Если вы знаете, как сделать это математически, примените эти знания и напишите код, который будет действовать точно так же, как если бы вам приходилось вычислять определитель вручную (на бумаге). Как сказал вам Игнасио в своем комментарии, расскажите, пожалуйста, что вы пробовали, и, возможно, тогда вы получите лучшие ответы. Я с удовольствием отредактирую свой ответ и помогу вам.

РЕДАКТИРОВАТЬ:

Поскольку проблема здесь заключается не в самой формуле, а в понимании работы с массивами, я бы предложил что-то вроде этого урока (я предполагаю, что вы используете C#): how to: массивы в C#

Я могу подтвердить, что предыдущее решение работает для 3×3 и 4×4, но НЕ для 5×5 и т. Д. Следуя решению (очень простому), которое работает для любых размеров (также 5×5 и более).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;    

namespace MatrixTest
{
public class Matrix
{
    private int dimension; //number of rows & colums for matrix
    private double[][] matrix; //holds values of matrix itself

    /// <summary>
    /// Create dim*dim matrix and fill it with data passed to this constructor.
    /// </summary>
    /// <param name="double_array"></param>
    /// <param name="dim"></param>
    public Matrix(double[][] double_array)
    {
        matrix = double_array;
        dimension = matrix.Length;
        // check square matrix:
        for (int i = 0; i < dimension; i++)
            if (matrix[i].Length != dimension)
                throw new Exception("Matrix is not square");
    }

    /// <summary>
    /// Get determinant of current matrix
    /// </summary>
    /// <returns></returns>
    public double Determinant()
    {
        if (dimension == 1)
            return matrix[0][0];
        // else ricorsive call:
        double det = 0;
        for (int j = 0; j < dimension; j++)
        {
            if (j % 2 == 0)
                det += matrix[0][j] * GetSubmatrix(this, 0, j).Determinant();
            else
                det -= matrix[0][j] * GetSubmatrix(this, 0, j).Determinant();
        }
        return det;
    }

    /// <summary>
    /// Return a new Matrix with:
    /// dimension = passed matrix dimension - 1
    /// elements = all element of the original matrix, except row and column specified
    /// </summary>
    /// <param name="m"></param>
    /// <param name="rowToExclude"></param>
    /// <param name="colToExclude"></param>
    /// <returns></returns>
    public Matrix GetSubmatrix(Matrix m, int rowToExclude, int colToExclude)
    {
        double[][] values = new double[m.dimension - 1][];
        for (int i = 0; i < m.dimension; i++)
        {
            // create row array:
            if (i < m.dimension - 1)
                values[i] = new double[m.dimension - 1];
            // copy values:
            for (int j = 0; j < m.dimension; j++)
                if (i != rowToExclude && j != colToExclude)
                    values[i < rowToExclude ? i : i - 1][j < colToExclude ? j : j - 1] = m.matrix[i][j];
        }
        return new Matrix(values);
    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            Matrix mat02 = new Matrix(
                new double[][] {
                new double[] { 1.0, 2.0},
                new double[] { -2.0, -5.0} });

            Matrix mat03 = new Matrix(
                new double[][] {
                new double[] { 1.0, 2.0, -1.0 },
                new double[] { -2.0, -5.0, -1.0},
                new double[] { 1.0, -1.0, -2.0 } });

            Matrix mat04 = new Matrix(
                new double[][] {
                new double[] {1.0, 2.0, 1.0, 3.0},
                new double[] { -2.0, -5.0, -2.0, 1.0 },
                new double[] { 1.0, -1.0, -3.0, 2.0 },
                new double[] {4.0, -1.0, -3.0, 1.0} });

            Matrix mat05 = new Matrix(
                new double[][] {
                new double[] {1.0, 2.0, 1.0, 2.0, 3.0},
                new double[] {2.0, 1.0, 2.0, 2.0, 1.0},
                new double[] {3.0, 1.0, 3.0, 1.0, 2.0},
                new double[] {1.0, 2.0, 4.0, 3.0, 2.0},
                new double[] {2.0, 2.0, 1.0, 2.0, 1.0} });


            double determinant = mat02.Determinant();
            Console.WriteLine("determinant is: {0}", determinant);

            determinant = mat03.Determinant();
            Console.WriteLine("determinant is: {0}", determinant);

            determinant = mat04.Determinant();
            Console.WriteLine("determinant is: {0}", determinant);

            determinant = mat05.Determinant();
            Console.WriteLine("determinant is: {0}", determinant);

            Console.ReadLine();
        }
    }
}

}

Сгенерируйте все перестановки целых чисел 1..N и для каждой такой последовательности s_1..s_N рассчитайте произведение значений ячеек M(i,s_i), умноженных на значение знака p(s_1..s_i), который равен 1, если i-s_1 четный, и -1 в противном случае, Суммируйте все эти продукты.

постскриптум

Как говорит полиген, существуют неэффективные алгоритмы, и это O(N!), Так как он продолжает пересчитывать общие субпродукты. Но это интуитивно понятно и экономно, если лениво.

Да, и указанная выше функция знака неверна: P(s_1..s_i) равно +1, если s_i имеет нечетный индекс в последовательности 1..N с удаленным s_1..s_{i-1}, и -1 для четного индекс.

Для тех, кто может прийти на этот вопрос в поисках алгоритма для определения определителя матрицы, обратите внимание, что вышеприведенное решение состоит из этого кода:

static double DeterminantGaussElimination(double[,] matrix)
        {
            int n = int.Parse(System.Math.Sqrt(matrix.Length).ToString());
            int nm1 = n - 1;
            int kp1;
            double p;
            double det=1;
            for (int k = 0; k < nm1; k++)
            {
                kp1 = k + 1;
                for(int i=kp1;i<n;i++)
                {
                    p = matrix[i, k] / matrix[k, k];
                    for (int j = kp1; j < n; j++)
                        matrix[i, j] = matrix[i, j] - p * matrix[k, j];
                }
            }
            for (int i = 0; i < n; i++)
                det = det * matrix[i, i];
            return det;

        }

работает для 3×3 и 4×4, но НЕ для 5×5 и т. д.,

Вот доказательство:

using System;

public class Matrix
{
    private int row_matrix; //number of rows for matrix
    private int column_matrix; //number of colums for matrix
    private double[,] matrix; //holds values of matrix itself

    //create r*c matrix and fill it with data passed to this constructor
    public Matrix(double[,] double_array)
    {
        matrix = double_array;
        row_matrix = matrix.GetLength(0);
        column_matrix = matrix.GetLength(1);
        Console.WriteLine("Contructor which sets matrix size {0}*{1} and fill it with initial data executed.", row_matrix, column_matrix);
    }

    //returns total number of rows
    public int countRows()
    {
        return row_matrix;
    }

    //returns total number of columns
    public int countColumns()
    {
        return column_matrix;
    }

    //returns value of an element for a given row and column of matrix
    public double readElement(int row, int column)
    {
        return matrix[row, column];
    }

    //sets value of an element for a given row and column of matrix
    public void setElement(double value, int row, int column)
    {
        matrix[row, column] = value;
    }

    public double deterMatrix()
    {
        int n = int.Parse(System.Math.Sqrt(matrix.Length).ToString());
        int nm1 = n - 1;
        int kp1;
        double p;
        double det = 1;
        for (int k = 0; k < nm1; k++)
        {
            kp1 = k + 1;
            for (int i = kp1; i < n; i++)
            {
                p = matrix[i, k] / matrix[k, k];
                for (int j = kp1; j < n; j++)
                    matrix[i, j] = matrix[i, j] - p * matrix[k, j];
            }
        }
        for (int i = 0; i < n; i++)
            det = det * matrix[i, i];
        return det;
    }
}

internal class Program
{
    private static void Main(string[] args)
    {
        Matrix mat03 = new Matrix(new[,]
        {
            {1.0, 2.0, -1.0},
            {-2.0, -5.0, -1.0},
            {1.0, -1.0, -2.0},
        });

        Matrix mat04 = new Matrix(new[,]
        {
            {1.0, 2.0, 1.0, 3.0},
            {-2.0, -5.0, -2.0, 1.0},
            {1.0, -1.0, -3.0, 2.0},
            {4.0, -1.0, -3.0, 1.0},
        });

        Matrix mat05 = new Matrix(new[,]
        {
            {1.0, 2.0, 1.0, 2.0, 3.0},
            {2.0, 1.0, 2.0, 2.0, 1.0},
            {3.0, 1.0, 3.0, 1.0, 2.0},
            {1.0, 2.0, 4.0, 3.0, 2.0},
            {2.0, 2.0, 1.0, 2.0, 1.0},
        });

        double determinant = mat03.deterMatrix();
        Console.WriteLine("determinant is: {0}", determinant);

        determinant = mat04.deterMatrix();
        Console.WriteLine("determinant is: {0}", determinant);

        determinant = mat05.deterMatrix();
        Console.WriteLine("determinant is: {0}", determinant);
    }
}

Однако, как вопрос для конкретного для 4×4, я нашел этот алгоритм правильным (по крайней мере, в нескольких случаях, которые я тестировал).

Если вы запустите код выше, вы получите:

определитель: -8 определитель: -142 определитель: NaN

Я знаю, что на этот вопрос ответили, но для любого, кому может понадобиться алгоритм, который может вычислить определитель матрицы с любыми измерениями, это то, что я придумал.

Этот класс использует много разных методов, чтобы сделать матрицу треугольной, а затем вычисляет ее определитель. Может использоваться для матрицы высокого размера, например, 500 х 500 или даже больше. яркая сторона этого класса в том, что вы можете получить результат в BigDecimal, чтобы не было бесконечности, и у вас всегда был точный ответ. Кстати, использование множества различных методов и избежание рекурсии привели к гораздо более быстрому пути с более высокой производительностью ответа. надеюсь, это будет полезно.

import java.math.BigDecimal;


public class DeterminantCalc {

private double[][] matrix;
private int sign = 1;


DeterminantCalc(double[][] matrix) {
    this.matrix = matrix;
}

public int getSign() {
    return sign;
}

public BigDecimal determinant() {

    BigDecimal deter;
    if (isUpperTriangular() || isLowerTriangular())
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));

    else {
        makeTriangular();
        deter = multiplyDiameter().multiply(BigDecimal.valueOf(sign));

    }
    return deter;
}


/*  receives a matrix and makes it triangular using allowed operations
    on columns and rows
*/
public void makeTriangular() {

    for (int j = 0; j < matrix.length; j++) {
        sortCol(j);
        for (int i = matrix.length - 1; i > j; i--) {
            if (matrix[i][j] == 0)
                continue;

            double x = matrix[i][j];
            double y = matrix[i - 1][j];
            multiplyRow(i, (-y / x));
            addRow(i, i - 1);
            multiplyRow(i, (-x / y));
        }
    }
}


public boolean isUpperTriangular() {

    if (matrix.length < 2)
        return false;

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < i; j++) {
            if (matrix[i][j] != 0)
                return false;

        }

    }
    return true;
}


public boolean isLowerTriangular() {

    if (matrix.length < 2)
        return false;

    for (int j = 0; j < matrix.length; j++) {
        for (int i = 0; j > i; i++) {
            if (matrix[i][j] != 0)
                return false;

        }

    }
    return true;
}


public BigDecimal multiplyDiameter() {

    BigDecimal result = BigDecimal.ONE;
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            if (i == j)
                result = result.multiply(BigDecimal.valueOf(matrix[i][j]));

        }

    }
    return result;
}


// when matrix[i][j] = 0 it makes it's value non-zero
public void makeNonZero(int rowPos, int colPos) {

    int len = matrix.length;

    outer:
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (matrix[i][j] != 0) {
                if (i == rowPos) { // found "!= 0" in it's own row, so cols must be added
                    addCol(colPos, j);
                    break outer;

                }
                if (j == colPos) { // found "!= 0" in it's own col, so rows must be added
                    addRow(rowPos, i);
                    break outer;
                }
            }
        }
    }
}


//add row1 to row2 and store in row1
public void addRow(int row1, int row2) {

    for (int j = 0; j < matrix.length; j++)
        matrix[row1][j] += matrix[row2][j];
}


//add col1 to col2 and store in col1
public void addCol(int col1, int col2) {

    for (int i = 0; i < matrix.length; i++)
        matrix[i][col1] += matrix[i][col2];
}


//multiply the whole row by num
public void multiplyRow(int row, double num) {

    if (num < 0)
        sign *= -1;


    for (int j = 0; j < matrix.length; j++) {
        matrix[row][j] *= num;
    }
}


//multiply the whole column by num
public void multiplyCol(int col, double num) {

    if (num < 0)
        sign *= -1;

    for (int i = 0; i < matrix.length; i++)
        matrix[i][col] *= num;

}


// sort the cols from the biggest to the lowest value
public void sortCol(int col) {

    for (int i = matrix.length - 1; i >= col; i--) {
        for (int k = matrix.length - 1; k >= col; k--) {
            double tmp1 = matrix[i][col];
            double tmp2 = matrix[k][col];

            if (Math.abs(tmp1) < Math.abs(tmp2))
                replaceRow(i, k);
        }
    }
}


//replace row1 with row2
public void replaceRow(int row1, int row2) {

    if (row1 != row2)
        sign *= -1;

    double[] tempRow = new double[matrix.length];

    for (int j = 0; j < matrix.length; j++) {
        tempRow[j] = matrix[row1][j];
        matrix[row1][j] = matrix[row2][j];
        matrix[row2][j] = tempRow[j];
    }
}


//replace col1 with col2
public void replaceCol(int col1, int col2) {

    if (col1 != col2)
        sign *= -1;

    System.out.printf("replace col%d with col%d, sign = %d%n", col1, col2, sign);
    double[][] tempCol = new double[matrix.length][1];

    for (int i = 0; i < matrix.length; i++) {
        tempCol[i][0] = matrix[i][col1];
        matrix[i][col1] = matrix[i][col2];
        matrix[i][col2] = tempCol[i][0];
    }
}

}

И затем этот класс получает матрицу nxn от пользователя или может генерировать случайную матрицу nxn, а затем вычисляет ее определитель. Также показано решение и окончательная треугольная матрица.

import java.math.BigDecimal;
import java.security.SecureRandom;
import java.text.NumberFormat;
import java.util.Scanner;


public class DeterminantTest {

public static void main(String[] args) {

    String determinant;

    //generating random numbers
int len = 500;
SecureRandom random = new SecureRandom();
double[][] matrix = new double[len][len];

for (int i = 0; i < len; i++) {
    for (int j = 0; j < len; j++) {
        matrix[i][j] = random.nextInt(500);
        System.out.printf("%15.2f", matrix[i][j]);
    }
}
System.out.println();

/*double[][] matrix = {
    {1, 5, 2, -2, 3, 2, 5, 1, 0, 5},
    {4, 6, 0, -2, -2, 0, 1, 1, -2, 1},
    {0, 5, 1, 0, 1, -5, -9, 0, 4, 1},
    {2, 3, 5, -1, 2, 2, 0, 4, 5, -1},
    {1, 0, 3, -1, 5, 1, 0, 2, 0, 2},
    {1, 1, 0, -2, 5, 1, 2, 1, 1, 6},
    {1, 0, 1, -1, 1, 1, 0, 1, 1, 1},
    {1, 5, 5, 0, 3, 5, 5, 0, 0, 6},
    {1, -5, 2, -2, 3, 2, 5, 1, 1, 5},
    {1, 5, -2, -2, 3, 1, 5, 0, 0, 1}
};

    double[][] matrix = menu();*/

    DeterminantCalc deter = new DeterminantCalc(matrix);

    BigDecimal det = deter.determinant();

    determinant = NumberFormat.getInstance().format(det);

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix.length; j++) {
            System.out.printf("%15.2f", matrix[i][j]);
        }
        System.out.println();
    }

    System.out.println();
    System.out.printf("%s%s%n", "Determinant: ", determinant);
    System.out.printf("%s%d", "sign: ", deter.getSign());

}


public static double[][] menu() {

    Scanner scanner = new Scanner(System.in);

    System.out.print("Matrix Dimension: ");
    int dim = scanner.nextInt();

    double[][] inputMatrix = new double[dim][dim];

    System.out.println("Set the Matrix: ");
    for (int i = 0; i < dim; i++) {
        System.out.printf("%5s%d%n", "row", i + 1);
        for (int j = 0; j < dim; j++) {

            System.out.printf("M[%d][%d] = ", i + 1, j + 1);
            inputMatrix[i][j] = scanner.nextDouble();
        }
        System.out.println();
    }
    scanner.close();

    return inputMatrix;
}

}