Interpretación intuitiva de la matriz de adyacencia como operador lineal.

Question

Naturalmente, podemos describir gráficos a través de las mesas de "sí hay un borde" o "no no no" entre cada par de vértices, de modo que la definición de una matriz de adyacencia es fácil de entender. Pensando en estas tablas como matrices, sin embargo, añade estructura - específicamente, una interpretación como un operador lineal. ¿Por qué nos fijamos en ellos en esta luz? Es sólo para la aplicación - por ejemplo, de manera eficiente la obtención de una gran cantidad de datos acerca de un gráfico mediante el cálculo de su espectro? O es que hay también una intuitiva geométrica (o algebraica) la motivación detrás de la matriz de adyacencia?

Por ejemplo, el $2$-ruta ha matriz de adyacencia $$\mathcal{A}(P_2)=\left(\begin{array}{cc} 0 & 1\\1 & 0\end{array}\right)$$ which acts on a $2$-dimensional vector space by flipping the coordinates, $(x,y)\mapsto (y,x)$. Can we somehow intuitively connect this action to the $2$-camino? ¿Qué sucede para otras gráficas simples?

Answer 1

Si $G = (V, E)$ es un gráfico, a continuación, la matriz de adyacencia es un operador que actúa sobre el espacio de funciones de $V \to \mathbb{R}$ (por ejemplo) a través de

$$A(f)(v) = \sum_{v \to w} f(w).$$

La construcción de la matriz de adyacencia es por lo tanto una forma de linealización. Tenga en cuenta que esta descripción de la matriz de adyacencia hace la conexión entre las potencias de la matriz de adyacencia y rutas de acceso en el gráfico de inmediato.

Dicho de otra manera, hay una categoría llamada la categoría de luces de conjuntos, y un gráfico que puede ser considerado como un endomorfismo en esta categoría. La categoría de luces de conjuntos está estrechamente relacionada con la categoría de relaciones , excepto que realizar un seguimiento no sólo si las dos cosas están relacionadas, sino un "conjunto de formas" que dos cosas están relacionadas. Un adecuado subcategoría de esta categoría admite una linealización functor a la categoría de espacios vectoriales.