¿Qué significa "ortogonal de vectores propios de valor propio cero"? Son los autovalores realmente igual a 0?
Vector propio de valor propio cero es un vector $\mathbf{a}$ tal que $L\mathbf{a}=\mathbf{0}$. En este caso
$$\begin{bmatrix}
L_{G_{1}} & 0\\
0 & L_{G_{2}}
\end{bmatrix}
\begin{bmatrix}
0\\
1
\end{bmatrix}
=
\begin{bmatrix}
0\\
0
\end{bmatrix}
\text{ y }
\begin{bmatrix}
L_{G_{1}} & 0\\
0 & L_{G_{2}}
\end{bmatrix}
\begin{bmatrix}
1\\
0
\end{bmatrix}=
\begin{bmatrix}
0\\
0
\end{bmatrix}$$
por lo tanto los vectores $\mathbf{a}_1=[1,\dots,1,0,\dots,0]^T$ $\mathbf{a}_2=[0,\dots,0,1,\dots,1]^T$ son vectores propios correspondientes al autovalor 0.
Ellos son ortogonales desde $\mathbf{a}_1^T\mathbf{a}_2=0$. Ya sabemos que estos vectores son ortogonales, deben ser linealmente independientes.
¿Cómo sabemos que estos valores corresponden a $\lambda_2$?
Dado que los valores propios son cada vez más ordenado y tenemos dos vectores propios linealmente independientes, es decir, al menos dos autovalores son cero, sabemos que $\lambda_1=\lambda_2=0$.
Sospecho que todos los $\lambda$'s están ordenados por la multiplicidad. Pero, ¿cómo puedo probar que cada n por n simétrica matriz tiene n autovalores, contados con su multiplicidad.
Autovalores son raíces del polinomio característico, que tiene el grado $n$. Así que, contando multiplicidad, no es $n$ de ellos. Aquí estamos hablando de multiplicidad algebraica, véase wikipedia.
¿Por qué en realidad es verdadera si $u$ $v$ están conectados por una arista, tenemos $x(u)=x(v)$, no es obvio para mí, incluso si $x$ es vector propio, y lo que ocurre en el caso general?
Desde $\sum\limits_{(u,v)\in E}^{} (x(u)-x(v))^{2} = 0$ es una suma de no negativo números reales, cada uno de ellos debe ser cero. Así que tenemos $(x(u)-x(v))^{2}=0$ y, en consecuencia, $(x(u)-x(v))=0$, para cada una de las $(u,v)\in E$.
OK, por ahora vamos a comprobar que $\lambda_{1}=0$, pero, ¿qué acerca de la $\lambda_{2}$?
Se ha demostrado en la anterior parte de la prueba, que (si $G$ está conectado) cada vector propio para el cero es múltiplo de $[1,1,\dots,1]^T$. Esto demuestra que el subespacio propio correspondiente a cero autovalor tiene dimensión 1, es decir, la multiplicidad geométrica de este autovalor es 1.
EDIT: Lo que he escrito aquí antes era innecesario complicado. El laplaciano de la matriz es simétrica, por lo tanto es diagonalizable. Por lo tanto, algebraicas y geométricas de la multiplicidad son el mismo.
Sin embargo, debemos mostrar que la multiplicidad algebraica de $\lambda_1=0$ es 1. Supongamos que esto no sería cierto. Esto implicaría que existe un vector $\mathbf a$ tal que $L \mathbf a = [1,1,\dots,1]^T$. Esto implicaría que el vector $[1,1,\dots,1]^T$ pertenece a la columna de espacio de la matriz $L$. Pero directamente de la definición de Laplace de la matriz , podemos ver que este vector es ortogonal a cada columna de $L$. (Al menos para los no-ponderado gráficos - yo no creo que sobre el caso ponderado.)
Estoy de acuerdo con usted en que este último argumento parece ser que faltan en el pdf-archivo vinculado. (Y, probablemente, diferentes explicaciones son posibles.)
Sólo unas pocas palabras de explicación. (Pero es mejor leerlo con más detalles en la wiki o en algún libro de texto de álgebra lineal.)
Si $\mathbf{a}$ es un vector propio de una matriz de $A$, significa que $(A-\lambda I)\mathbf a=\mathbf 0$. Si algebraica multiplicidad (=la multiplicidad de $\lambda$ como una raíz del polinomio característico) es mayor que la multiplicidad geométrica (=dimensión de la correspondiente espacio propio), esto implica que no es un autovector $\mathbf a$ y un autovector generalizado $\mathbf b$ tal que $(A-\lambda I)\mathbf b=\mathbf a$ .
Esta fue la propiedad que hemos utilizado en el último párrafo.
Geométrica de la multiplicidad es, precisamente, el número de bloques de Jordan en la forma normal de Jordan.
Cabe recordar, que en el libro Bapat: Grafos y Matrices, Universitext, Springer, 2010, el Laplaciano de la matriz se define como sigue.
El autor define, en primer lugar
el (vértice borde) matriz de incidencia de G se denota por a $Q(G)$, que es el $n\times m$ matriz con entradas de $0$ si el vértice y arista incidente, $1$ si el borde se inicia en este vértice y $-1$ si termina allí. Es relativamente fácil demostrar que el rango de $Q(G)$ $n-k$ donde $k$ es el número de componentes conectados de este gráfico, ver p.11 y 12 de este libro.
A continuación, el Laplaciano de la matriz se puede obtener como $L(G)=Q(G)Q(G)^T$, ver p.45
Utilizando este hecho llegamos $\operatorname{rank}(L)=\operatorname{rank}(QQ^T)=\operatorname{rank}(Q)$, véase el Lema 4.3, p.46.
El hecho de que la matriz de $Q$ y su matriz de Gram $QQ^T$ tienen el mismo rango se menciona en el mismo libro en p.10
como ejercicio:
Deje $A$ $m\times n$ matriz. Mostrar que $A$ $A^TA$ tienen el mismo espacio nulo. Por lo tanto
a la conclusión de que $\operatorname{rank} A = \operatorname{rank}A^TA$.
I. e., se ha demostrado que la $n-\operatorname{rank}(G)$ es el número de componentes conectados.
Desde $L(G)$ es simétrica es diagonalizable, y por lo tanto este es el mismo que el número de no-cero autovalores.
De nuevo, no sé si algo similar se puede hacer en el caso ponderado.
