Voy a mostrar un código recursivo para calcular el determinante de una matriz cuadrada de orden n. No voy a explicar tan en detalle que cosa es el determinante pues son conocimientos "básicos" de algebra que deben saber si necesitan utilizar esté código.
Veamos que:
Sea A una matriz cuadrada; asociada a esa matriz hay un número llamado determinante, que se simboliza por |A| o det(A) y que se calcula de la siguiente forma:
- Si el orden de A es 2 el determinante es el producto de los elementos de la diagonal principal menos el producto de los elementos de la diagonal secundaria:
Ej:
A = (a00, a01)
(a10, a11)
Luego: det(A) = a00*a11 - a10*a01
- Si el orden de A es 3 el determinante se calcula utilizando la llamada Regla de Sarrus, según la cual si A es la matriz de orden 3:
A = (a00, a01, a02)
(a10, a11, a12)
(a20, a21, a22)
y: det(A) = a00*a11*a22 + a01*a12*a20 + a02*a10*a21 - a02*a11*a20 - a01*a10*a22 - a00*a12*a21
Ahora, si el orden de la matriz es superior a 3 el determinante se reduce al de una matriz de orden 3 o de orden 2 de la siguiente manera (que es la que vamos a implementar):
A partir de la matriz cuadrada arbitraria A, si removemos la fila i y la columna j obtenemos una nueva matriz de orden (una unidad) menor que la matriz A y que la vamos a denotar como Aij, cuyo determinante det(Aij) recibe el nombre de menor complementario del elemento aij. Si a este det(Aij) le acompañamos de su signo (-1)i+j tenemos el adjunto de aij
Resumiendo:
Menor complementario de aij = det(Aij)
Adjunto de aij = cij = (-1)i+j*det(Aij)
Entonces, si A es una matriz cuadrada de orden mayor que 3 el determinante de A se obtiene eligiendo una fila o columna arbitraria de A y multiplicando a cada elemento de esta por su adjunto. De esta forma, si elegimos la fila i, el determinante de A es:
det(A) = SUMATORIA(desde i, j=1 hasta n)(aij * (-1)i+j * det(Aij))
Espero esto se haya entendido, trate de explicarlo lo más sencillo posible.
Ahora vamos al código:
Vamos a tener varios métodos con las siguientes signaturas:
Código
public static int Determinant(int[,] matrix) static int DeterminantOrder2(int[,] matrix) static int DeterminantRec(int[,] matrix) static void FillMatrix(int[,] matrix, int[,] toFill, int row, int column)
Como podemos observar el método Determinant() va a ser el método portal, luego tenemos para calcular el determinante de una matriz de orden 2, luego para calcular el determinante de una matriz de orden mayor que 2 y el último es un método auxiliar para rellenar la matriz adjunta de los menores.
Código
public static int Determinant(int[,] matrix) { //Comprobamos que sea cuadrada if (matrix.GetLength(0) != matrix.GetLength(1)) //Vemos si es de orden 2 if (matrix.GetLength(0) == 2) return DeterminantOrder2(matrix); else return DeterminantRec(matrix); }
En este ^^ método lo primero que hacemos es comprobar que la matriz sea cuadrada, para esto comprobamos el valor del método .GetLength(), el cual devuelve un int que representa la cantidad de elementos en cada dimensión, o sea el orden de la matriz horizontal y vertical. En este caso tenemos dos dimensiones, por lo tanto comprobamos que si se cumple que:
Código
matrix.GetLength(0) != matrix.GetLength(1)
Entonces lanzamos una excepción pues la matriz no es cuadrada.
Luego, ya que sabemos que la matriz es cuadrada vamos a comprobar si es de orden 2 y llamamos al método correspondiente, sino es de orden mayor y llamamos al método recursivo.
Veamos primero el método DeterminantOrder2():
Código
static int DeterminantOrder2(int[,] matrix) { return (matrix[0, 0] * matrix[1, 1]) - (matrix[0, 1] * matrix[1, 0]); }
Este método es muy sencillo lo cual no es necesario explicar nada. (Revisen arriba como se calcula el determinante de orden 2)
Ahora, vamos con el método DeterminatRec() que viene a ser "el más complicado", lo pongo entre comilla, porque no es más que una representación en código de la ecuación que les presenté antes para calcular el determinante de orden mayor que 2:
Código
static int DeterminantRec(int[,] matrix) { //Caso de parada que sea de orden 2 y lo calculamos con el método para //el determinante de orden 2 if (matrix.GetLength(0) == 2) { return DeterminantOrder2(matrix); } else { int det = 0; //Inicializamos una variable para almacenar el valor del determinante //En este ciclo recorremos una fila para para obtener el adjunto de cada elemento //de esta fila así calcular el determinante de este fijando cada elemento de la fila //0 for (int i = 0; i < matrix.GetLength(1); i++) { //Creamos una matriz para rellenarla con la matriz para luego calcular su //determinante llamando recursivo. Esta matriz tiene un orden menor (en una //unidad) que la matriz original //Aquí llamamos al método auxiliar que se encarga de rellenar la matriz auxiliar FillMatrix(matrix, minor, 0, i); //Aquí lo que vamos a definir si lo que se hace es sumar o restar. Esto es una //manera de representar el cambio de signo que trae consigo el (-1) elevado a //i+j. En este caso como utilizamos la fila 0 siempre, ese número va a ser //positivo solo cuando estemos en una columna (j) que sea par, negativo en //caso contrario if (i % 2 == 0) //Aquí lo que hacemos es multiplicar el valor del elemento en cuestión //por el adjunto teniendo en cuenta el signo correspondiente y se lo //sumamos a la variable det (en el else es lo mismo lo que con el signo //negativo). Aquí es donde está la llamada recursiva pues hay que calcular el //determinante de la matriz "minor" det+= (matrix[0, i]) * (DeterminantRec(minor)); else det+= (-matrix[0, i]) * (DeterminantRec(minor)); } //Una vez que ya recorrimos toda la fila, devolvemos el determinante return det; } }
Ya explique todo en los comentarios del código.
Ahora veamos el método FillMatrix():
Este método recibe la matriz desde la cual se van a sacar los valores, la matriz donde se van a copiar (de un orden menor en una unidad), la fila y la columna que se va a eliminar:
Código
static void FillMatrix(int[,] matrix, int[,] toFill, int row, int column) { //Ciclo anidado para recorrer la matriz desde la cual se van a sacar los valores for (int i = 0; i < matrix.GetLength(0); i++) { for (int j = 0; j < matrix.GetLength(1); j++) { //Si estamos en una fila menor a la que se va a eliminar if (i < row) { //Si estamos en una columna menor a la que se va a eliminar if (j < column) toFill[i, j] = matrix[i, j]; //Copiamos el valor normalmente else if (j > column) //En este momento estamos en una fila menor a la que se va a //eliminar pero por encima de la columna a eliminar, por lo tanto //se saca el valor de la matriz y se coloca en una columna con una //unidad menos (j-1) toFill[i, j - 1] = matrix[i, j]; } else //Si estamos en una fila mayor a la que se va a eliminar if (i > row) { //Si estamos en una columna mayor a la que se va a eliminar if (j < column) //En este momento estamos por encima de la fila a eliminar pero por debajo //de la columna a eliminar, por lo tanto tenemos que quitarle una unidad a la fila //(i-1) toFill[i - 1, j] = matrix[i, j]; else if (j > column) //Aquí estamos por encima tanto de la fila como de la columna a eliminar por lo //tanto le quitamos una unidad tanto a las filas como a la columna (i-1, j-1) toFill[i - 1, j - 1] = matrix[i, j]; } } } }
Espero que este código se haya entendido, sino, ya saben que pueden preguntar, opinar y/o criticar.
Quizás no sea la mejor manera (complejidad temporal) de hacerlo, si tienen alguna sugerencia será bienvenida.
Espero seguir subiendo códigos pronto.
Salu2s