Matrices y Google Pagerank

Normalmente uno estudia las matemáticas como una aburrida y a veces absurda secuencia de cálculos, que cada vez se pone más enredada -solo piensen que los niños parten estudiando teoría de conjuntos que es lo más abstracto y complicado que existe- enseñada a veces por ganapanes que con suerte entienden la mitad de lo que dicen. No es raro que tanta gente las termine odiando.

Pero hay cosas tan lindas y tan interesantes que cuesta imaginarse. A veces uno no se da cuenta de eso hasta muchos años después que le enseñaron. Una de esas cuestiones asombrsas son las matrices, una forma de notación abreviada para representar y manipular información.

Sin saberlo trabajamos con matrices a cada rato: una hoja de cálculo Excel es exactamente una matriz, donde colocamos valores arreglados en filas y columnas y cada celda tiene un subíndice ij que nos permite localizarla A1,1; B3,5; etc.

La noción de matrices es una de las más antiguas en matemáticas, la conocían los chinos hace mucho más de 2000 años y les llamaban -apropiadamente- "cuadrados mágicos", porque cuando uno arregla los números de cierta forma aparecen propiedades que parecen de magia y ha tomado siglos entender por que funcionan.

El uso más conocido es la receta que nos enseñan en el colegio para resolver sistemas de ecuaciones lineales con matrices y sus determinantes. Lo más lindo de las matrices es que sus propiedades "mágicas" -que por ejemplo permiten resolver sistemas de ecuaciones- vienen de la forma y de la simetría, son propiedades que se pueden descubrir y usar por intuición, sin saber realmente por que funcionan, como se hizo durante muchos años.

Las matrices no solo sirven para resolver sistemas de ecuaciones lineales, también pueden representar muchas otras cosas como por ejemplo grafos, lo que facilita mucho su manipulación en una computadora. Un grafo con cientos o miles de nodos es muy difícil de interpretar, pero se puede representar por una matriz y gracias a las propiedades "mágicas" de las matrices se pueden calcular valores con más facilidad.

La relación entre la forma, la simetría y las propiedades de lo que representa una matriz es muy importante, las matrices más simétricas son las que tienen las propiedades más interesantes y asombrosas. 

Por ejemplo la matriz cuadrada, con las mismas filas que columnas representan un sistema de ecuaciones que tiene una única solución (hay tantas ecuaciones como variables). Cuando hay menos ecuaciones que variables la matriz es rectangular y la solución no es única, sino que hay un espacio, una zona dentro de la cual hay infinitas soluciones factibles, el borde de esa zona es normalmente donde están las soluciones óptimas en programación lineal.

En el curso de Networks: friends, money and bytes me entero que Google usa propiedades de las matrices para calcular el Page Rank, que ordena a las páginas web según su importancia. A grandes rasgos se considera un grafo donde cada página web es un nodo y se conecta con las demás por links que salen a otras páginas o que entran de ciertas páginas. Por ejemplo imaginemos la web con solo cuatro sitios web, podría ser algo así:
(Ignoren las rayas en rojo, que son del profesor) Esto se podría representar con la siguiente matriz:
0, 0, 1, 0
0, 0, 1, 0
0, 0, 0, 1
1, 1, 1, 0
Donde cada fila representa un nodo (web) y si envía un link se coloca un 1 y si no envía se coloca un 0. Cada columna indica también el nodo hacia donde se envía el link. Por ejemplo la web 1 envía solo un link a la web 3, etc. 

Luego esta matriz se "normaliza" es decir cada valor se divide por el total de links enviados, en los tres primeros casos solo envían uno y en el cuarto se envían tres, así es que queda:
0, 0, 1, 0
0, 0, 1, 0
0, 0, 0, 1
1/3, 1/3, 1/3, 0
Y así tenemos el grafo representado por una matriz ¿y para que sirve esto?, bueno, es una matriz cuadrada de 4x4 así es que tiene propiedades mágicas. Una de estas propiedades es el eigenvalor y eleigenvector, que son una especie de factor de escala, que mantiene propiedades fundamentales de la matriz al multiplicarla. Si nuestra matriz es H, el eigenvalor lambda y el eigenvector pi se definen por esta igualdad:

H multiplicado por pi=lambda multiplicado por pi 

Bueno, resulta que este eigenvector almacena los valores que usa Google para rankear cada web ¿Como llegaron en Google a esa conclusión? Sepa Moya, ya les dije que las matrices son mágicas, a mi me llega hasta allí nomás el brazo. El hecho es que este eigenvector almacena la solución del sistema de ecuaciones lineales que representan al grafo. Y si quieren ver como se calculan los eigen (valor y vector propio hablando en cristiano) pueden leerlo aquí.

Claro que esa es una simplificación nomás porque hay varias otras complicaciones: las matrices de todas las páginas relevantes son enormes así es que se deben calcular usando métodos numéricos (iterativos), y hay casos especiales que complican la representación de matrices, pero todo tiene su solución y después de varias piruetas algebraicas se llega a la gran matriz G que es la que usa Google para asignar el Page Rank.