Dada una mat[][] de array cuadrada de dimensión N , la tarea es encontrar el determinante de la array utilizando el método de condensación pivote.
Ejemplos:
Entrada: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Salida: 0
Explicación:
Ejecutar R3 = R3 – R2 modifica la array mat[] [] a {{1, 2, 3}, {4, 5, 6}, {1, 1, 1}}.
Ejecutar R2 = R2 – R1 modifica la array mat[][] a {{1, 2, 3}, {1, 1, 1}, {1, 1, 1}}.
Ahora, las filas R2 y R3 son iguales.
Por lo tanto, la voluntad determinante de la array se vuelve igual a cero (usando la propiedad de array).Entrada: mat[][] = {{1, 0, 2, -1}, {3, 0, 0, 5}, {2, 1, 4, -3}, {1, 0, 5, 0} }
Salida: 30
Enfoque: la idea es utilizar el método de condensación pivotal para calcular el determinante de la array mat[][] . A continuación se muestra la explicación detallada del método propuesto:
En este método de cálculo del determinante de dimensión N × N , array cuadrada :
- Primero, la array A[][] de dimensión N*N se reduce a la array B[][] de dimensión (N – 1)*(N – 1) tal que:
- Luego, el valor determinante de A[][] se puede encontrar a partir de la array B[][] usando la fórmula,
- Ahora reduzca aún más la array a (N – 2)*(N – 2) y calcule el determinante de la array B[][] .
- Y repita el proceso anterior hasta que la array se vuelva de dimensión 2*2 .
- Luego, el determinante de la array de dimensión 2×2 se calcula usando la fórmula det(A) = ad-bc para una array, digamos A[][] como {{a, b}, {c, d}} .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos D , para almacenar el determinante de la array .
- Iterar mientras N es mayor que 2 y verificar lo siguiente:
- Verifique si mat[0][0] es 0 , luego intercambie la fila actual con la siguiente fila de modo que mat[i][0] > 0 usando la propiedad de array.
- De lo contrario, si no se encuentra ninguna fila tal que mat[i][0] > 0 , imprima cero.
- Ahora, multiplique D por pow(1 / mat[0][0], N – 2) .
- Calcule la siguiente array, digamos B[][] , de dimensión (N – 1) x (N – 1) usando la fórmula b[i – 1][j – 1] = mat[0][0 * mat[i ][i] – tapete[0][j] * tapete[i][0] .
- Asigne tapete = B .
- Multiplique D por el determinante de la array mat[][] de dimensión 2×2 , es decir mat[0][0] * mat[1][1] – mat[0][j] * mat[i][0 ].
- Finalmente, imprima el valor almacenado en D .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to swap values
void swap(float& i, float& j)
{
float temp = i;
i = j;
j = temp;
}
// Function to find the determinant
// of matrix M[][]
float determinantOfMatrix(
vector<vector<float> > mat, int N)
{
float mul = 1;
// Iterate over N while N > 2
while (N > 2) {
// Store the reduced matrix
// of dimension (N-1)x(N-1)
float M[N - 1][N - 1];
int next_index = 1;
// Check if first element
// of first row is zero
while (mat[0][0] == 0) {
if (mat[next_index][0] > 0) {
// For swapping
for (int k = 0; k < N; k++) {
swap(mat[0][k],
mat[next_index][k]);
}
// Update mul
mul = mul * pow((-1),
(next_index));
}
else if (next_index == (N - 1))
return 0;
next_index++;
}
// Store the first element
// of the matrix
float p = mat[0][0];
// Multiply the mul by
// (1/p) to the power n-2
mul = mul * pow(1 / p, N - 2);
// Calculate the next matrix
// of dimension (N-1) x (N-1)
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
// Calculate each element of
// the matrix from previous
// matrix
M[i - 1][j - 1] = mat[0][0]
* mat[i][j]
- mat[i][0]
* mat[0][j];
}
}
// Copy elements of the matrix
// M into mat to use it in
// next iteration
for (int i = 0;
i < (N - 1); i++) {
for (int j = 0;
j < (N - 1); j++) {
mat[i][j] = M[i][j];
}
}
// Decrement N by one
N--;
}
// Calculate the determinant
// of reduced 2x2 matrix and
// multiply it with factor mul
float D = mul * (mat[0][0]
* mat[1][1]
- mat[0][1]
* mat[1][0]);
// Print the determinant
cout << D;
}
// Driver Code
int main()
{
// Given matrix
vector<vector<float> > mat = { { 1, 0, 2, -1 },
{ 3, 0, 0, 5 },
{ 2, 1, 4, -3 },
{ 1, 0, 5, 0 } };
// Size of the matrix
int N = mat.size();
// Function Call
determinantOfMatrix(mat, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the determinant
// of matrix M[][]
static void determinantOfMatrix(int[][] mat, int N)
{
int mul = 1;
// Iterate over N while N > 2
while (N > 2)
{
// Store the reduced matrix
// of dimension (N-1)x(N-1)
int [][]M = new int[N - 1][N - 1];
int next_index = 1;
// Check if first element
// of first row is zero
while (mat[0][0] == 0)
{
if (mat[next_index][0] > 0)
{
// For swapping
for (int k = 0; k < N; k++)
{
int temp = mat[0][k];
mat[0][k] = mat[next_index][k];
mat[next_index][k] = temp;
}
// Update mul
mul = (int) (mul * Math.pow((-1),
(next_index)));
}
else if (next_index == (N - 1))
return;
next_index++;
}
// Store the first element
// of the matrix
int p = mat[0][0];
// Multiply the mul by
// (1/p) to the power n-2
mul = (int) (mul * Math.pow(1 / p, N - 2));
// Calculate the next matrix
// of dimension (N-1) x (N-1)
for (int i = 1; i < N; i++)
{
for (int j = 1; j < N; j++)
{
// Calculate each element of
// the matrix from previous
// matrix
M[i - 1][j - 1] = mat[0][0]
* mat[i][j]
- mat[i][0]
* mat[0][j];
}
}
// Copy elements of the matrix
// M into mat to use it in
// next iteration
for (int i = 0;
i < (N - 1); i++)
{
for (int j = 0;
j < (N - 1); j++)
{
mat[i][j] = M[i][j];
}
}
// Decrement N by one
N--;
}
// Calculate the determinant
// of reduced 2x2 matrix and
// multiply it with factor mul
int D = mul * (mat[0][0]
* mat[1][1]
- mat[0][1]
* mat[1][0]);
// Print the determinant
System.out.print(D);
}
// Driver Code
public static void main(String[] args)
{
// Given matrix
int[][] mat = { { 1, 0, 2, -1 },
{ 3, 0, 0, 5 },
{ 2, 1, 4, -3 },
{ 1, 0, 5, 0 } };
// Size of the matrix
int N = mat.length;
// Function Call
determinantOfMatrix(mat, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to find the determinant # of matrix M[][] def determinantOfMatrix(mat, N): mul = 1 # Iterate over N while N > 2 while (N > 2): # Store the reduced matrix # of dimension (N-1)x(N-1) M = [[0 for i in range(N-1)] for j in range(N-1)] next_index = 1 # Check if first element # of first row is zero while (mat[0][0] == 0): if (mat[next_index][0] > 0): # For swapping for k in range(N): temp = mat[0][k] mat[0][k] = mat[next_index][k] mat[next_index][k] = temp # Update mul mul = mul * pow((-1),(next_index)) elif (next_index == (N - 1)): return 0; next_index += 1 # Store the first element # of the matrix p = mat[0][0] # Multiply the mul by # (1/p) to the power n-2 mul = mul * pow(1 / p, N - 2) # Calculate the next matrix # of dimension (N-1) x (N-1) for i in range(1,N): for j in range(1,N,1): # Calculate each element of # the matrix from previous # matrix M[i - 1][j - 1] = mat[0][0] * mat[i][j] - mat[i][0] * mat[0][j] # Copy elements of the matrix # M into mat to use it in # next iteration for i in range(N - 1): for j in range(N - 1): mat[i][j] = M[i][j] # Decrement N by one N -= 1 # Calculate the determinant # of reduced 2x2 matrix and # multiply it with factor mul D = mul * (mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0]) # Print the determinant print(int(D)) # Driver Code if __name__ == '__main__': # Given matrix mat = [[1, 0, 2, -1],[3, 0, 0, 5], [2, 1, 4, -3], [1, 0, 5, 0]] # Size of the matrix N = len(mat) # Function Call determinantOfMatrix(mat, N) # This code is contributed by bgangwar59.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the determinant
// of matrix [,]M
static void determinantOfMatrix(int[,] mat, int N)
{
int mul = 1;
// Iterate over N while N > 2
while (N > 2)
{
// Store the reduced matrix
// of dimension (N-1)x(N-1)
int [,]M = new int[N - 1,N - 1];
int next_index = 1;
// Check if first element
// of first row is zero
while (mat[0,0] == 0)
{
if (mat[next_index,0] > 0)
{
// For swapping
for (int k = 0; k < N; k++)
{
int temp = mat[0,k];
mat[0,k] = mat[next_index,k];
mat[next_index,k] = temp;
}
// Update mul
mul = (int) (mul * Math.Pow((-1),
(next_index)));
}
else if (next_index == (N - 1))
return;
next_index++;
}
// Store the first element
// of the matrix
int p = mat[0,0];
// Multiply the mul by
// (1/p) to the power n-2
mul = (int) (mul * Math.Pow(1 / p, N - 2));
// Calculate the next matrix
// of dimension (N-1) x (N-1)
for (int i = 1; i < N; i++)
{
for (int j = 1; j < N; j++)
{
// Calculate each element of
// the matrix from previous
// matrix
M[i - 1,j - 1] = mat[0,0]
* mat[i,j]
- mat[i,0]
* mat[0,j];
}
}
// Copy elements of the matrix
// M into mat to use it in
// next iteration
for (int i = 0;
i < (N - 1); i++)
{
for (int j = 0;
j < (N - 1); j++)
{
mat[i,j] = M[i,j];
}
}
// Decrement N by one
N--;
}
// Calculate the determinant
// of reduced 2x2 matrix and
// multiply it with factor mul
int D = mul * (mat[0,0]
* mat[1,1]
- mat[0,1]
* mat[1,0]);
// Print the determinant
Console.Write(D);
}
// Driver Code
public static void Main(String[] args)
{
// Given matrix
int[,] mat = { { 1, 0, 2, -1 },
{ 3, 0, 0, 5 },
{ 2, 1, 4, -3 },
{ 1, 0, 5, 0 } };
// Size of the matrix
int N = mat.GetLength(0);
// Function Call
determinantOfMatrix(mat, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for the above approach
// Function to find the determinant
// of matrix M[][]
function determinantOfMatrix(mat, N)
{
let mul = 1;
// Iterate over N while N > 2
while (N > 2)
{
// Store the reduced matrix
// of dimension (N-1)x(N-1)
let M = new Array(N - 1);
for(let i = 0; i < N - 1; i++)
{
M[i] = new Array(N - 1);
for(let j = 0; j < N - 1; j++)
{
M[i][j] = 0;
}
}
let next_index = 1;
// Check if first element
// of first row is zero
while (mat[0][0] == 0)
{
if (mat[next_index][0] > 0)
{
// For swapping
for (let k = 0; k < N; k++)
{
let temp = mat[0][k];
mat[0][k] = mat[next_index][k];
mat[next_index][k] = temp;
}
// Update mul
mul = (mul * Math.pow((-1),
(next_index)));
}
else if (next_index == (N - 1))
return;
next_index++;
}
// Store the first element
// of the matrix
let p = mat[0][0];
// Multiply the mul by
// (1/p) to the power n-2
mul = (mul * Math.pow(parseInt(1 / p, 10), N - 2));
// Calculate the next matrix
// of dimension (N-1) x (N-1)
for (let i = 1; i < N; i++)
{
for (let j = 1; j < N; j++)
{
// Calculate each element of
// the matrix from previous
// matrix
M[i - 1][j - 1] = mat[0][0]
* mat[i][j]
- mat[i][0]
* mat[0][j];
}
}
// Copy elements of the matrix
// M into mat to use it in
// next iteration
for (let i = 0;
i < (N - 1); i++)
{
for (let j = 0;
j < (N - 1); j++)
{
mat[i][j] = M[i][j];
}
}
// Decrement N by one
N--;
}
// Calculate the determinant
// of reduced 2x2 matrix and
// multiply it with factor mul
let D = mul * (mat[0][0]
* mat[1][1]
- mat[0][1]
* mat[1][0]);
// Print the determinant
document.write(D);
}
// Given matrix
let mat = [ [ 1, 0, 2, -1 ],
[ 3, 0, 0, 5 ],
[ 2, 1, 4, -3 ],
[ 1, 0, 5, 0 ] ];
// Size of the matrix
let N = mat.length;
// Function Call
determinantOfMatrix(mat, N);
// This code is contributed by decode2207.
</script>
Producción:
30
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por sahurasmita409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA