Forma de fila-escalón reducida de una matriz

8

El objetivo de este desafío es crear un programa que tome una matriz y genere su forma reducida de escalón de fila.

Una matriz está en forma reducida de fila-escalón si cumple con todas las siguientes condiciones:

  1. Si hay una fila donde cada entrada es cero, entonces esta fila se encuentra debajo de cualquier otra fila que contenga una entrada distinta de cero.
  2. La entrada que no está a la izquierda de una fila es igual a 1.
  3. La entrada que no está a la izquierda de una fila es la única entrada que no es cero en su columna.
  4. Considere dos entradas distintas distintas a la izquierda, una ubicada en la fila i, columna j y la otra ubicada en la fila s, columna t. Si s>i, entonces t>j.

Fuente

El proceso general para transformar la matriz es:

  1. Trate cada fila i de 1 a n a su vez, y trabaje a través de las columnas j de 1 a m omitiendo cualquier columna de todas las entradas cero.
  2. Encuentre la siguiente columna j con una entrada distinta de cero.
  3. Intercambie filas, si es necesario, de modo que el elemento pivote A (i, j) no sea cero.
  4. Haga que el pivote sea igual a 1 dividiendo cada elemento en la fila de pivote por el valor del pivote.
  5. Haga que todos los elementos encima y debajo del pivote sean iguales a 0 restando un múltiplo adecuado de la fila del pivote entre sí.
  6. Repita para todas las filas.

Si desea leer más sobre este tipo de matriz, vea el artículo de Wikipedia y una herramienta y artículo (pasos anteriores) que muestra los pasos para transformar la matriz.

En cuanto al desafío real, aquí va:

La entrada se puede proporcionar de la forma que desee a través de STDIN o equivalente, solo explíquelo en su respuesta. La salida será la forma reducida de fila-escalón de la entrada en la misma forma que la entrada a través de STDOUT o equivalente. Las lagunas estándar no están permitidas y las bibliotecas o funciones externas que realizan esta tarea tampoco están permitidas ( TI-BASICel rref(comando de, por ejemplo). Puede escribir un programa o función completa. Este es el código de golf, el BYTES más bajo gana. ¡Buena suerte!

Entrada de ejemplo: [[2,1,1,14][-1,-3,2,-2][4,-6,3,-5]]

Salida de ejemplo: [[1,0,0,1][0,1,0,5][0,0,1,7]]

GamrCorps
fuente
55
Debe dar alguna explicación del proceso de reducción aquí, por lo que esta pregunta aún tiene sentido cuando esos enlaces se vuelven malos.
Sparr
Se agregó una explicación. Espero que sea lo suficientemente detallado.
GamrCorps
¿Se nos permite usar `ref ()` `, solucionadores de ecuaciones lineales o cualquier otra solución integrada que casi resuelva el problema?
lirtosiast
Mientras haya un paso más complejo que algo así method(ref(matrix)), yo diría que siga adelante
GamrCorps

Respuestas:

2

R, 232 bytes

function(M){p=1;R=nrow(M);C=ncol(M);for(r in 1:R){if(C<=p)break;i=r;while(M[i,p]==0){i=i+1;if(R==i){i=r;p=p+1;if(C==p)return(M)}};t=M[i,];M[i,]=M[r,];M[r,]=t;M[r,]=M[r,]/M[r,p];for(i in 1:R)if(i!=r)M[i,]=M[i,]-M[r,]*M[i,p];p=p+1};M}

Esto es solo una implementación del algoritmo de eliminación gaussiano habitual.

Sin golf:

rref <- function(M) {
    p <- 1
    R <- nrow(M)
    C <- ncol(M)
    for (r in 1:R) {
        if (C <= p)
            break
        i <- r
        while (M[i, p] == 0) {
            i <- i + 1
            if (R == i) {
                i <- r
                p <- p + 1
                if (C == p)
                    return(M)
            }
        }
        t <- M[i, ]
        M[i, ] <- M[r, ]
        M[r, ] <- t
        M[r, ] <- M[r, ] / M[r, p]
        for (i in 1:R)
            if (i != r)
                M[i, ] <- M[i, ] - M[r, ] * M[i, p]
        p <- p + 1
    }
    M
}
Alex A.
fuente
Creo que puedes salirte con la M[c(i,r),]=M[c(r,i),]t=M[i,];M[i,]=M[r,];M[r,]=t
tuya en