In this article, we are going find the Determinant of a matrix using different approaches. Before finding the value of a determinant, we must know about a matrix determinant. A matrix's determinant is a particular integer specified only for square matrices (matrices having the same number of rows and columns). A determinant is used frequently in calculus and other algebraic matrices; it describes the matrix in the context of a real number that may be used to solve a system of linear equations and identify the inverse of a matrix.
How do you compute?
The determinant of a matrix can be determined as follows: for each element of the first row or column, obtain the cofactor of those components, multiply the component with the determinants of the associated cofactor, and then add them with opposite signs. In the most basic case, the determinant of a 1*1 matrix is the single value itself. The cofactor of an element is a matrix obtained by eliminating the element's columns and rows from that matrix.
Approach 1:
Filename: Determinant.cpp
Let's take an example to illustrate the determinant of the 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 is O(N^2) . The following recurring relation can be used to calculate the time-based complexity of the determinantOfMatrix method :
T(N) =N*T(N-1) + O(N^3)
The first number, N*T(N-1) , indicates the time required to calculate the determinants of the (N-1) x (N-1) submatrices . In contrast, the second value, O(N-3) , represents the time required to calculate the cofactors that are needed for every single component in the original matrix's first row. We can calculate the factor that determines an NxN matrix as a sum of its determinants (N-1)x(N-1) matrices, each of which calls for O(N^2) operations to get the cofactors, using expansion by digits. As a result, the determinantOfMatrix method has a time-based complexity of O(N!) , which is the most extreme case when the matrix is a recombination matrix.
The display function has a time complexity of O(N^2) because it loops throughout all the matrix members to print them. Its computational complexity is O(N!) because the determinantOfMatrix function dominates the entire time complexity of the program's code.
Space Complexity: O(N*N)
By applying the determinant properties, we iterate through each diagonal element, making all of the elements below the diagonal zero.
Approach 2:
If this diagonal element is zero, we will look for the next non-zero element in the same column.
There are two possibilities.
Case 1: If there isn't a non-zero element. In this case, the value of the determinant for the matrix is 0.
Case 2: If a non-zero element is present, there are two possibilities.
- Case a: If the index matches a diagonal row member, we reduce all of the column items to zero using the determinant properties.
- Case b: Here, we must swap the row with the corresponding diagonal element columns and continue the case 'a'; procedure.
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 is the total amount of rows (or columns) in a matrix.
Auxiliary Space: O(1) because the matrix has been modified in place.
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)