El algoritmo de Reducción Gaussiana es probablemente uno de los algoritmos mejor conocidos y de mayor aplicación en el área del Álgebra Lineal. Es básico para los cursos de nivel universitario, pero muchos conocen el proceso desde niveles educativos más elementales.

Su utilidad es de gran magnitud y trasciende lo que deseo expresar en esta entrada. No obstante un análisis que me parece interesante realizar como computólogo es el de la cantidad de operaciones elementales requeridas para llevar una matriz cuadrada y arbitraria a su forma escalonada reducida.

Este planteamiento me fue presentado hace un par de semanas por mi profesor, Dr. Leonardo Martínez durante su curso de Álgebra Lineal, cuyas notas se encuentran en línea y recomiendo ampliamente estudiar como una referencia formal al tema.

Resulta de particular interés para mí puesto que como computólogo, es de mi incumbencia el análisis algorítmico para cuantificar su eficiencia. Si bien este problema no lidia directamente con la complejidad del algoritmo directamente, sí nos sirve como un primer acercamiento.

Álgoritmo de Reducción Gaussiana.

El algoritmo de Reducción Gaussiana, también conocido como Eliminación Gaussiana o algoritmo de Gauss-Jordan, nos sirve para llevar una matriz a su forma escalonada reducida.

La forma escalonada reducida de una matriz cumple con:

  • No hay una fila con entradas distintas de cero, debajo de una fila con únicamente entradas iguales a cero.

  • En filas con entradas distintas de cero, la primer entrada distinta de cero se encuentra estrictamente a la derecha de la primer entrada no cero de la fila anterior.

  • En filas con entradas distintas de cero, la primer entrada distinta de 0 tiene al 1, y es la única entrada distinta de cero en su columna.

La tercera condición es necesaria para la forma escalonada reducida. La forma escalonada simple de una matriz puede cumplir solo con las primeras dos condiciones.

El Teorema de Reducción Gaussiana nos dice que toda matriz puede ser llevada a su forma escalonada reducida en una cantidad finita de pasos. Curiosamente, y para nuestro beneficio, la demostración del teorema se presenta de manera algorítmica, por lo tanto, la misma demostración nos dice cómo encontrar la forma escalonada reducida.

No enunciaré el algoritmo de manera que quede demostrado el teorema puesto que no es la intención del post demostrarlo, pero sí enunciaré el algoritmo de una manera que considero suficientemente clara para aplicarlo.

El algoritmo es el siguiente:

  1. En la primera columna de la matriz con entradas no todas cero, buscamos la primer entrada (de arriba hacia abajo) distinta de cero.

  2. La fila con la entrada que encontramos en el paso anterior, la intercambiamos con la fila de hasta arriba.

  3. Multiplicamos la fila por el inverso multiplicativo de la entrada encontrada antes, de manera que obtengamos 1 en la primer entrada.

  4. Ponemos todas las entradas en la misma columna como 0, restando multiplos del primer renglón.

  5. Repetimos el proceso, en la submatriz que queda de quitar el primer renglón.

Operaciones elementales.

Las operaciones elementales en una matriz son 3 “acciones” (solo por no repetir la palabra operaciones) que podemos realizar sobre una matriz, y las utilizamos para llevarla a la forma escalonada reducida. Tienen una importancia mayor puesto que nos sirve para encontrar una forma equivalente de un sistema de ecuaciones lineales que a su vez es más sencillo de resolver, pero de momento no entremos en eso.

Las operaciones elementales son 3, y si bien introdujimos el algoritmo de reducción gaussiana sin mencionarlas, es importante saber que en realidad es lo único que utilizamos para llevar a cabo el algoritmo. Desde un punto de vista de desarrollador, serían nuestros subprocesos a partir de los cuáles construimos el algoritmo.

Las operaciones son:

  1. Intercambio de filas.

  2. Multiplicación de las entradas de una fila por un mismo escalar (léase “número”).

  3. Sumar a una fila un múltiplo de otra fila: el múltiplo de una fila sería el resultado de aplicar la operación anterior.

Podemos darnos cuenta de que la tercer operación en realidad utiliza la operación 2 por debajo, pero para términos prácticos (y por bases teóricas ligadas a las matrices elementales) la consideraremos como una sola operación.

Número de operaciones del algoritmo.

Con lo anterior claro podemos enunciar el resultado que queremos demostrar:

Toda matriz en $M_n(F)$ se puede llevar a su forma escalonada reducida usando a lo más $n^2$ operaciones elementales.

La notación $M_n(F)$ solo nos dice que nuestra matriz es cuadrada (es decir, tiene el mismo número de filas y columnas) y su tamaño de cada lado es $n$. En otras palabras, la matriz con la que vamos a trabajar es de tamaño $n\times n$.

Para demostrar lo anterior, utilizaremos obviamente el algoritmo de reducción gaussiana, y las operaciones elementales anteriormente definidas.

Podemos demostrarlo de manera muy rigurosa utilizando una notación que implique índices, recursión y de más, pero como el resto del post, por esta ocasión me enfocaré en dar una explicación que apele a la intuición y simplemente siga un algoritmo.

Entonces, comenzando con el algoritmo tenemos que primero debemos buscar el primer renglón distinto de cero y tomar la primera entrada distinta de cero de ahí mismo. Si bien esto nos importaría al evaluar la complejidad del algoritmo, por ahora solo queremos contar el número de operaciones elementales necesarias, entonces lo omitimos.

El siguiente paso del algoritmo sí nos importa, puesto que es un intercambio de filas. Como vimos antes, esto es una operación elemental, entonces lo contamos. Hasta ahorita llevamos 1 operación. No obstante, también puede suceder que la fila encontrada sea la primera en la matriz, y entonces no necesitamos un intercambio de filas. Concluimos que llevamos 0 o 1 operaciones.

En el tercer paso el algoritmo nos pide multiplicar por el inverso de la primera entrada. Si la primer entrada distinta de cero es 1, entonces no hay necesidad de multiplicar. Si no es el caso, entonces realizamos la multiplicación. Ahora llevamos entre 0 y 2 operaciones. El ejercicio nos pide demostrar que a lo más son $n^2$ operaciones. Entonces, solo nos enfocaremos en el peor caso. Hasta ahorita el peor caso es cuando hemos hecho 2 operaciones.

El paso 4 del algoritmo nos dice que restemos múltiplos del renglón. En el peor de los casos tenemos que hacer eso para los $n-1$ renglones que hay debajo. Sumado a las 2 operaciones que ya habíamos hecho, tenemos $n+1$.

Pero antes de continuar notemos que, si hicimos $n-1$ restas, entonces no hicimos el intercambio de filas del paso 2 del algoritmo. No podemos hacer un intercambio de filas y además $n-1$ restas puesto que, significaría que nuestra fila no era la primera distinta de cero, contradiciendo la condición del algoritmo.

Con lo anterior podemos concluir que en el peor de los casos, hasta ahorita tenemos $n$ pasos (ya sean 0 intercambios, 1 multiplicación y $n-1$ restas; o 1 intercambio, 1 multiplicación y $n-2$ restas).

Finalmente podemos llegar a la conclusión. El paso 5 nos dice que vamos a repetir eso con las demás filas distintas de 0. En el peor de los casos tenemos $n$ filas distintas de cero (pues nuestra matriz es de tamaño $n\times n$).

Si hicimos el proceso $n$ veces y cada iteración tiene $n$ operaciones, en el peor de los casos hicimos $n^2$ operaciones elementales, demostrando la proposición.


Cabe aclarar que lo anterior no es realmente la complejidad en tiempo del algoritmo. No estamos midiendo exactamente el número de pasos que toma ejecutar el algoritmo, únicamente estamos viendo cuántas operaciones elementales toma. Cada operación elemental se puede traducir en varias operaciones al implementar el algoritmo: simplemente el multiplicar una fila por un escalar va a tomar $n$ operaciones dada una matriz de tamaño $n$.

Pero de cualquier manera es un buen ejercicio teórico, para practicar nuestra comprensión algorítmica.