suppose there is given two dimensional array
int a[][]=new int[4][4];
i am trying to find determinant of matrices please help i know how find it mathematical but i am trying to find it in programaticaly i am using language java and c# but in this case i think c++ will be also helpfull
If you're fixed to 4x4, the simplest solution would be to just hardcode the formula.
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];
}
For a general NxN, the problem is considerably harder, with various algorithms in the order of O(N!), O(N^3), etc.
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;
}
This method is not sure to work, since you have to divide by a member of your matrix, if a member of your matrix is 0, you could get result det = NaN.
If you know how to do it mathematically, then apply this knowledge and write code that does exactly the same as you would do if you had to calculate the determinant by hand (on a paper). As Ignacio told you in his comment, please tell us what have you tried and maybe then you will get better answers. I will gladly edit my answer and help you out.
EDIT:
As it seems the problem here is not the formula itself, but understanding how to work with arrays, i would suggest something like this tutorial (i assume you use C#): how to: arrays in C#
Generate all the permuatations of integers 1..N, and for each such sequence s_1..s_N, calculate the product of the values of the cells M(i,s_i) multiplied by a sign value p(s_1..s_i), which is 1 if i-s_1 is even, and -1 otherwise. Sum all these products.
Postscript
As polygene says, there are inefficient algorithms, and this one is O(N!), since it keeps recalculating shared subproducts. But it's intuitive and space efficient, if done lazily.
Oh, and the sign function above is wrong: P(s_1..s_i) is +1, if s_i has odd index in the sequence 1..N with s_1..s_{i-1} removed, and -1 for even index.
I can confirm that the previous solution works for 3x3 and 4x4 but NOT for 5x5 etc. Following a solution (very simple) that works for any dimensions (also 5x5 or more).
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();
}
}
}
}
For anyone who might come to this question in search for algorithm for calculation determinant of matrix please note that above posted solution which consists of this code:
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;
}
is working for 3x3 and 4x4 but NOT for 5x5 etc.,
Here is a proof:
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);
}
}
However, as the question for specific for 4x4 I found that algorithm correct (at least in several cases I tested).
If your run above code you will get:
determinant is: -8 determinant is: -142 determinant is: NaN
I Know this question is answered, but for any one who might need an algorithm that can calculate the determinant of a matrix with any dimensions, this is what I came up with.
This class uses many different methods to make the matrix triangular and then, calculates the determinant of it. It can be used for matrix of high dimension like 500 x 500 or even more. the bright side of the this class is that you can get the result in BigDecimal so there is no infinity and you'll have always the accurate answer. By the way, using many various methods and avoiding recursion resulted in much faster way with higher performance to the answer. hope it would be helpful.
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];
}
}
}
And then this class receives a matrix of n x n from the user or can generate a random matrix of nxn and then calculates it's determinant. It also shows the solution and the final triangular matrix.
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;
}
}
