Demostrar que un grafo construido con matrices es fuertemente regular

Question

Supongamos que $F_q$ es un campo con $q$ elementos. Considere todos los $2\times d$ matrices con entradas en $F_q$ , por lo que tenemos $q^{2d}$ matrices. Consideremos cada matriz como un vértice, y dos vértices $A$ y $B$ son adyacentes cuando $\operatorname{rank}(A-B)=1$ . Queremos demostrar que este gráfico introducido es fuertemente regular.

Fijo un vértice arbitrario $A$ . Como estas matrices tienen dos filas, pongo una de las filas (primera fila) de la matriz $B$ con el elemento de identidad de la operación de adición (primera) del campo, y luego poner la otra fila (segunda) la inversa de las entradas de la segunda fila de $A$ . En este caso $\operatorname{rank}(A-B)$ será 1. Ahora sustituye la primera y la segunda en el párrafo anterior, entonces tenemos otra $B$ con las propiedades que queremos, por lo que obtengo este resultado de que este gráfico es 2-regular, pero no tengo ni idea de $\lambda$ y $\mu$ .

Por favor revise mi respuesta y si esta mal por favor hágalo bien, y por favor ayúdeme con otra parte, gracias.

Answer 1

El gráfico no será en general $2$ -regular. Para un ejemplo sencillo, tomemos $q=d=2$ . Las matrices de rango $1$ son

$$\begin{align*} &\pmatrix{1&0\\0&0},\pmatrix{0&1\\0&0},\pmatrix{1&1\\0&0},\\ &\pmatrix{1&0\\1&0},\pmatrix{0&1\\0&1},\pmatrix{1&1\\1&1},\\ &\pmatrix{0&0\\1&0},\pmatrix{0&0\\0&1},\pmatrix{0&0\\1&1}\;,\\ \end{align*}$$

por lo que cualquier matriz $A$ es adyacente al $9$ matrices obtenidas mediante la adición de uno de estos rangos $1$ matrices a $A$ . Así, el gráfico en este caso es $9$ -regular.

En el caso general podemos contar el rango $1$ de la siguiente manera. Si la primera fila es cero, la segunda puede ser cualquier vector no nulo en $\Bbb F_q^d$ , por lo que hay $q^d-1$ posibilidades para la segunda fila. Si la primera fila no es cero, la segunda puede ser cualquier múltiplo escalar de la primera; hay $q^d-1$ posibles primeras filas no nulas y $q$ escalares, por lo que en total hay $(q+1)(q^d-1)$ rango $1$ matrices. Dado que $A$ y $B$ son adyacentes si $A=B+R$ para algún rango $1$ matriz $R$ se deduce que el gráfico es $(q+1)(q^d-1)$ -regular.

Dejemos que $\mathscr{R}$ sea el conjunto de rango $1$ matrices; son las matrices adyacentes a $Z$ la matriz cero. Supongamos que $R\in\mathscr{R}$ y $A$ es adyacente a ambos $R$ y $Z$ . entonces $A\in\mathscr{R}$ y $A-R\in\mathscr{R}\setminus\{-R\}$ . A la inversa, $R+S$ es adyacente a ambos $R$ y $Z$ para cualquier $S\in\mathscr{R}\setminus\{-R\}$ . Así, el número de matrices adyacentes a ambos $R$ y $Z$ es $|\mathscr{R}|-1=(q+1)(q^d-1)-1$ . Ahora utiliza el hecho de que para cualquier $A,B$ y $C$ , $A$ es adyacente a $B$ si $A+C$ es adyacente a $B+C$ para demostrar que

$$\lambda=|\mathscr{R}|-1=(q+1)(q^d-1)-1\;.$$

Supongamos ahora que $A$ no es adyacente a $Z$ es decir, que $\operatorname{rank}(A)=2$ . Entonces $R$ es adyacente a ambos $A$ y $Z$ si $R\in\mathscr{R}$ y $A-R\in\mathscr{R}$ . Así, el número de matrices adyacentes a ambos $A$ y $Z$ es el número de pares ordenados $\langle R,S\rangle$ de rango $1$ matrices tales que $R+S=A$ . (No tenemos que preocuparnos por la posibilidad de que $R=S$ ya que en ese caso $\operatorname{rank}(R+S)\le 1$ y $R+S\ne A$ .)

• Demuestre que este número es el mismo para todos los rangos $2$ matriz $A$ . SUGERENCIA: Intenta contar los $R\in\mathscr{R}$ tal que $A-R\in\mathscr{R}$ . Utiliza el hecho de que una matriz no nula está en $\mathscr{R}$ si su segunda fila es un múltiplo escalar de su primera fila, o su primera fila es cero.

• A continuación, utilice de nuevo el hecho de que la adyacencia es invariante de la traslación (es decir, para cualquier $A,B$ y $C$ , $A$ es adyacente a $B$ si $A+C$ es adyacente a $B+C$ ) para demostrar que este número es $\mu$ .

Answer 2

Los gráficos en cuestión son el caso de diámetro dos de los llamados gráficos de formas bilineales. La forma más fácil de demostrar que son fuertemente regulares es mostrar que su grupo de automorfismo es un grupo de permutación de rango tres, es decir, que el estabilizador de un vértice tiene exactamente tres órbitas. Esto se reduce al álgebra lineal directa: los mapas que envían una matriz $M$ a $AMB^T$ (con $A,B$ invertible) fija la matriz cero y actúa transitivamente sobre las matrices de rangos uno y dos.

Contar funciona y es más interesante en algunos aspectos, pero es más trabajo.