Hoy he leído la afirmación de que si $A$ $B$ son matrices dispersas, a continuación, $AB$ es también escasa. Yo no lo creía al principio, pero no podía exhibir un contraejemplo. Así es esta afirmación en el hecho verdadero? Si es así, cómo es escaso es $AB$? Puede un buen resultado como `si $A$ $s$- escasa e $B$ $t$- disperso, $AB$ es (?)-dispersos?"
Respuesta
¿Demasiados anuncios?
Si cada columna de $B$ tiene más de $t$ cero entradas, cada columna de $AB$ es la combinación lineal de los en la mayoría de las $t$ columnas de $A$. Si las columnas de a $A$ tienen en la mayoría de $s$ cero entradas, esto implica que cada columna de $AB$ puede tener en la mayoría de $st$ cero entradas.
Si desea que el resultado en términos de filas, sólo transponer todo.
Aquí es un ejemplo de que el producto de dos $2$-matrices dispersas se $4$escasos:
$$ \begin{bmatrix}\bullet & \bullet & & \\ \bullet & \bullet & & \\ & & \bullet & \bullet \\ & & \bullet & \bullet\end{bmatrix} \begin{bmatrix}\bullet & & \bullet & \\ & \bullet & & \bullet \\ \bullet & & \bullet & \\ & \bullet & & \bullet\end{bmatrix} = \begin{bmatrix}\bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet \\ \bullet & \bullet & \bullet & \bullet\end{bmatrix} $$
