In this guide, we will explore various methods for calculating the Determinant of a matrix. Prior to determining the value of a determinant, it is essential to understand the concept of a matrix determinant. The determinant of a matrix is a unique scalar value defined specifically for square matrices (matrices with equal rows and columns). This determinant plays a crucial role in calculus and algebraic operations involving matrices; it provides a numerical representation of the matrix, aiding in solving linear equations systems and determining the matrix's inverse.
How do you compute?
The calculation of a matrix's determinant involves the process of obtaining the cofactor of each element in the first row or column. This entails multiplying each element with the determinant of its corresponding cofactor and summing them with alternating signs. In a simple scenario, the determinant of a 1*1 matrix equals the sole value present. The cofactor of an element refers to a matrix derived by excluding the respective element's rows and columns from the original matrix.
Approach 1:
Filename: Determinant.cpp
Let's consider an example to demonstrate calculating the determinant of a matrix in C++.
//Program to find the determinant of the matrix
#include <iostream>
using namespace std;
// declaring the dimensions of the square matrix
#define N 4
// Function for finding the cofactor
// matrix[p][q] in tem[][]. num is
// the current values of matrix[][]
void getCofactorMatrix(int matrix[N][N],
int tem[N][N], int p1,
int q1, int num)
{
int i = 0, j = 0;
//Loop for iterating of the matrix
for (int rows = 0; rows < num; rows++)
{
for (int cols = 0; cols < num; cols++)
{
// Transferring into a temporary matrix
// just those elements that are not in the supplied row and column
if (rows != p1 && cols != q1)
{
tem[i][j++] = matrix[rows][cols];
// Because the row is complete, increase the row index as well as reset the cols index.
if (j == num - 1)
{
j = 0;
i++;
}
}
}
}
}
/* A recursive function for determining the determinant of a matrix, where num is the current length of the matrix[][].*/
int determinantOfMatrix(int matrix[N][N], int num)
{
// result
int Determinent = 0;
// If the matrix has a single element, this is the default case.
if (num == 1)
return matrix[0][0];
// for storing the co-factors
int tem[N][N];
//for storing sign
int signs = 1;
//iterating over each element
for (int f = 0; f < num; f++)
{
getCofactorMatrix(matrix, tem, 0, f, num);
Determinent += signs * matrix[0][f] *
determinantOfMatrix(tem, num - 1);
//Adding opposite sign
signs = -signs;
}
return Determinent;
}
// function to display matrix
void displayMatrix(int matrix[N][N],
int rows, int cols)
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
cout << " " << matrix[i][j];
cout << "n";
}
}
// Main
int main()
{
int matrix[N][N]= {{1, 3, 4, -1},
{2, 0, 3, 5},
{2, 9, 2, -3},
{1, 2, 1, 1}};
// function calling
cout << "The Determinant of the matrix is: " <<
determinantOfMatrix(matrix, N);
return 0;
}
Output:
The determinant of the matrix is: 10
Time Complexity: O(N!)
Explanation:
The time complexity of the getCofactorMatrix function amounts to O(N^2). To determine the time complexity of the determinantOfMatrix method, we can employ the following recurrent relation:
T(N) =N*T(N-1) + O(N^3)
The initial number, N*T(N-1), signifies the duration needed to compute the determinants of the (N-1) x (N-1) submatrices. Conversely, the subsequent figure, O(N-3), denotes the time taken to compute the cofactors essential for each element in the first row of the original matrix. The calculation of the factor determining an NxN matrix involves summing the determinants of (N-1) x (N-1) matrices, each requiring O(N^2) operations to ascertain the cofactors through digit expansion. Consequently, the method determinantOfMatrix exhibits a time complexity of O(N!), which is the most severe scenario when the matrix is a permutation matrix.
The time complexity of the display function is O(N^2) as it iterates over all elements in the matrix to display them. The computational complexity, on the other hand, is O(N!) as the determinantOfMatrix function significantly influences the overall time complexity of the program.
Space Complexity: O(N*N)
When utilizing the determinant properties, we go through each diagonal element, setting all elements below the diagonal to zero.
Approach 2:
If this particular diagonal entry equals zero, we will search for the subsequent non-zero element within the identical column.
There are two possibilities.
In Case 1: If there is no non-zero element, the determinant of the matrix will be 0.
- Scenario a: When a non-zero element exists, and it aligns with a diagonal row element, we nullify all elements in that column by leveraging determinant characteristics.
- Scenario b: In this instance, we interchange the row with the respective diagonal element columns and proceed with the aforementioned 'a' scenario.
Example:
Filename: Determinanat2.cpp
//Program to find the determinant of a matrix
#include <bits/stdc++.h>
using namespace std;
// declaring the dimensions of a matrix
#define N 4
// Function to get determinant of matrix
int detOfMatrix(int matrix[N][N], int n)
{
// variables initiaiazation
int nums1, nums2, determinant = 1, in,
sum = 1;
// temp array for storing the rows
int tem[n + 1];
// iterating over loop elements
for (int i = 0; i < n; i++)
{
// index value
in = i;
//Find the index which has non-zero elements
while (in < n && matrix[in][i] == 0)
{
in++;
}
//If no nonzero element is found
if (in == n)
{
// if it is zero
continue;
}
if (in != i)
{
// looping over the matrix to swap elements
for (int j = 0; j < n; j++)
{
swap(matrix[in][j], matrix[i][j]);
}
//When we move rows through determinant features, the sign of the determinant changes.
determinant = determinant * pow(-1, in- i);
}
//Sorting the diagonal elements
for (int j = 0; j < n; j++)
{
tem[j] = matrix[i][j];
}
// visiting over every element of the below diagonal
for (int j = i + 1; j < n; j++)
{
// the diagobal element
nums1 = tem[i];
//the element of the next row
nums2 = matrix[j][i];
// iterating over a columns
for (int k = 0; k < n; k++)
{
// Making the diagonal
// element and the subsequent row element equal through multiplication
matrix[j][k]
= (nums1 * matrix[j][k]) - (nums2 * tem[k]);
}
sum = sum * nums1;
}
}
//The diagonal elements are multiplied to get the determinant
for (int i = 0; i < n; i++)
{
determinant = determinant * matrix[i][i];
}
return (determinant / sum);
}
// Driver code
int main()
{
int matrix[N][N] = {{3, 0, 2, -2},
{3, 0, 3, 4},
{3, 1, 4, -3},
{1, 0, 4, 9}};
// function calling
printf("The Determinant of the given matrix is: %d",
detOfMatrix(matrix, N));
return 0;
}
Output:
The Determinant of the given matrix is: 31
Complexity:
Time complexity: O(N 3)
Space Complexity: O(N)
Approach 3: Gauss-Jordan Elimination Technique
Steps:
- Beginning with the provided matrix, and set the determinant to 1 .
- While maintaining track of the determinant, use simple row operations to convert the matrix to its row-column form.
- If there are any row exchange operations, multiply the value of the determinant by -1 .
- If any row contains a coefficient that leads to a value of zero, the determinant is zero, and we can stop here.
- The determinant is the product of the diagonal elements in the row-column form.
- Return the value of the determinant.
Example:
Filename: DeterminantByGauss.cpp
#include <iostream>
#include <cmath>
using namespace std;
const int MAXNum = 105;
double array[MAXNum][MAXNum];
double determinantValue(int num) {
double determinant = 1.0;
for (int i = 0; i < num; i++) {
int pivotelement = i;
for (int j = i + 1; j < num; j++) {
if (abs(array[j][i]) > abs(array[pivotelement][i])) {
pivotelement = j;
}
}
if (pivotelement != i) {
swap(array[i], array[pivotelement]);
determinant *= -1;
}
if (array[i][i] == 0) {
return 0;
}
determinant *= array[i][i];
for (int j = i + 1; j < num; j++) {
double fact = array[j][i] / array[i][i];
for (int k = i + 1; k < num; k++) {
array[j][k] -= fact * array[i][k];
}
}
}
return determinant;
}
int main() {
int num = 4;
double mat[4][4] = {{2, 1, 2, -1},
{3, 0, 4, 3},
{1, 3, 4, -3},
{1, 0, 7, 1}};
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
array[i][j] = mat[i][j];
}
}
double determinant = determinantValue(num);
cout << "The Determinant value is= " << determinant << endl;
return 0;
}
Output:
The Determinant value is= 85
Complexity:
Time Complexity: O(N 3 ), where N represents the total number of rows or columns in a given matrix.
Auxiliary Space: O(1) as the matrix has been altered in situ.
Approach 4: Cofactor Expansion
Steps:
- Create a function to compute the determinate value of a matrix using cofactor expansions .
- If the matrix being evaluated is not a square matrix, return an error statement.
- Return an element if the matrix has 1×1 .
- Return the value of the determinant if the combination of elements is 2×2 using the ad-bc formula .
- If the number of elements is larger than 2×2 , loop over the first row and compute the cofactor for every single component.
- Multiply each cofactor by its associated element with the sign (+/-) of the element.
- Add the results of step 6 to obtain the determinant.
Example:
Filename: Cofactor.cpp
#include<iostream>
#include<cmath>
using namespace std;
int determinantValue(int mat[4][4], int num){
int determinant = 0;
int submat[4][4];
if(num == 1){
return mat[0][0];
}
else if(num == 2){
return ((mat[0][0] * mat[1][1]) - (mat[1][0] * mat[0][1]));
}
else{
for(int x = 0; x < num; x++){
int subin = 0;
for(int i = 1; i < num; i++){
int subjn = 0;
for(int j = 0; j < num; j++){
if(j == x){
continue;
}
submat[subin][subjn] = mat[i][j];
subjn++;
}
subin++;
}
determinant = determinant + (pow(-1, x) * mat[0][x] * determinantValue(submat, num-1));
}
}
return determinant;
}
int main(){
int mat[4][4] = {{1, 0, 4, 3},
{6, 1, 0, 4},
{2, 0, 2, 3},
{2, 0, 8, 2}};
int num = 4;
int determinant = determinantValue(mat, num);
cout<<"Determinant: "<<determinant<<endl;
return 0;
}
Output:
The Determinant is: 24
Complexity:
Time Complexity: O(N!)
Space Complexity: O(N^2)
