Matriz algoritmo de convergencia

Question

Supongamos que voy a empezar con un $n \times n$ matriz de ceros y unos:

$$\begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{bmatrix}$$

Entonces me normalizar cada fila tal que las sumas a $1$:

$$\begin{bmatrix} 0.& 0.& 0.& 0.5& 0.5\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ \end{bmatrix}$$

Y, a continuación, hacer lo mismo para cada columna:

$$\begin{bmatrix} 0. & 0. & 0. & 0.384615 & 0.384615\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ \end{bmatrix}$$

Este proceso se debe repetir 15 veces, y tengo:

$$\begin{bmatrix} 0. & 0. & 0. & 0.5 & 0.5\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ \end{bmatrix}$$

Suponiendo que la matriz original es tal que este proceso es estable, cada fila y columna en la final de la matriz, deben sumar a $1$.

Mis preguntas:

• Hay un nombre para lo que este algoritmo converge a, o algo estrechamente relacionados?

• Qué algoritmo se producen el mismo resultado, sino que convergen más rápido?

Answer 1

El algoritmo converge a una doblemente estocástica de la matriz. Debido a la normalización de filas y columnas es equivalente a multiplicar la matriz original a la izquierda y a la derecha, con algunos diagonal de la matriz (ver Sinkhorn del teorema), el doblemente estocástica de la matriz estará relacionada con el original de la matriz $Z$$P_d = D_1 Z D_2$.

Algoritmo alternativo puede ser en la solución del sistema de ecuaciones cuadráticas: