DeterminantOfMatrix


4. Determinant of a 2D matrix

Problem:

Given a 2D matrix, Determine it’s Determinant.

Solution:

This implementation is done using C#.NET. Rectangular Matrix is declared using int[,] syntax.

public static long EvaluateDeterminant(int[,] matrix)
{
long determinant = 0;

if (matrix == null || matrix.GetUpperBound(0) != matrix.GetUpperBound(1))
{
Console.WriteLine("Non-square matrix can't have a determinant");

return determinant;
}

int row_UB = matrix.GetUpperBound(0);

determinant = Determinant(matrix, row_UB + 1);

return determinant;
}

private static long Determinant(int[,] matrix, int size)
{
long determinant = 0;

if (size == 1) // 1x1 MAtrix
{
determinant = matrix[0, 0];
}
else if (size == 2) // 2x2 MAtrix
{
determinant = matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]; // can hash this multiplication
}
else
{
int multiplier = 1;

for (int i = 0; i < size; i++)
{
multiplier = (i % 2 == 0) ? 1 : -1;

determinant += multiplier * matrix[0, i] * Determinant(GetMinor(matrix, size, 0, i), size - 1);
}
}

return determinant;
}

/// <summary>
/// Gets the Minor of a Square Matrix
/// </summary>
/// <param name="matrix"></param>
/// <param name="size"></param>
/// <param name="rowIndex"></param>
/// <param name="colIndex"></param>
/// <returns></returns>
/// <remarks>
/// If function has to be Public, Certain checks on rowIndex, ColIndex should be made and size need not to be passed
/// </remarks>

private static int[,] GetMinor(int[,] matrix, int size, int rowIndex, int colIndex)
{
int minorSize = size - 1;
int[,] minor = new int[minorSize, minorSize];

for (int i = 0; i < rowIndex; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i, j] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = 0; j < colIndex; j++)
{
minor[i - 1, j] = matrix[i, j];
}
}

for (int i = 0; i < rowIndex; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i, j - 1] = matrix[i, j];
}
}

for (int i = rowIndex + 1; i < size; i++)
{
for (int j = colIndex + 1; j < size; j++)
{
minor[i - 1, j - 1] = matrix[i, j];
}
}

return minor;
}

Advertisements

About Sunil Singhal

A human being whose dreams are tied to a Horse that will never tire
This entry was posted in Algorithms and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s