Prove that a graph which is constructed with matrices is strongly regular

103 Views Asked by At

Suppose that $F_q$ is a field with $q$ elements. Consider all $2\times d$ matrices with entries in $F_q$, so we have $q^{2d}$ matrices. Consider each matrix as a vertex, and two vertices $A$ and $B$ are adjacent when $\operatorname{rank}(A-B)=1$. We want to prove that this graph which was introduced is strongly regular.

I fix an arbitrary vertex $A$. Because these matrices have two rows, I put one of rows (first row) of matrix $B$ with identity element of adding (first) operation of field, then put the other row (second) the converse of second row entries of $A$. In this case $\operatorname{rank}(A-B)$ will be 1. Now substitute first and second in above paragraph, then we have another $B$ with the properties we want, so I get this result that this graph is 2-regular, but I have no idea about $\lambda$ and $\mu$.

Please check my answer and if this is wrong please make it right, and please help me with other part, thanks.

2

There are 2 best solutions below

0
On BEST ANSWER

The graph will not in general be $2$-regular. For a simple example take $q=d=2$. The matrices of rank $1$ are

$$\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*}$$

so any matrix $A$ is adjacent to the $9$ matrices obtained by adding one of these rank $1$ matrices to $A$. Thus, the graph in this case is $9$-regular.

In the general case we can count the rank $1$ matrices as follows. If the first row is zero, the second row can be any non-zero vector in $\Bbb F_q^d$, so there are $q^d-1$ possibilities for the second row. If the first row is not zero, the second row can be any scalar multiple of the first; there are $q^d-1$ possible non-zero first rows and $q$ scalars, so altogether there are $(q+1)(q^d-1)$ rank $1$ matrices. Since $A$ and $B$ are adjacent iff $A=B+R$ for some rank $1$ matrix $R$, it follows that the graph is $(q+1)(q^d-1)$-regular.

Let $\mathscr{R}$ be the set of rank $1$ matrices; these are the matrices adjacent to $Z$, the zero matrix. Suppose that $R\in\mathscr{R}$, and $A$ is adjacent to both $R$ and $Z$. then $A\in\mathscr{R}$, and $A-R\in\mathscr{R}\setminus\{-R\}$. Conversely, $R+S$ is adjacent to both $R$ and $Z$ for any $S\in\mathscr{R}\setminus\{-R\}$. Thus, the number of matrices adjacent to both $R$ and $Z$ is $|\mathscr{R}|-1=(q+1)(q^d-1)-1$. Now use the fact that for any $A,B$ and $C$, $A$ is adjacent to $B$ iff $A+C$ is adjacent to $B+C$ to show that

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

Now suppose that $A$ is not adjacent to $Z$, i.e., that $\operatorname{rank}(A)=2$. Then $R$ is adjacent to both $A$ and $Z$ iff $R\in\mathscr{R}$ and $A-R\in\mathscr{R}$. Thus, the number of matrices adjacent to both $A$ and $Z$ is the number of ordered pairs $\langle R,S\rangle$ of rank $1$ matrices such that $R+S=A$. (We don’t have to worry about the possibility that $R=S$, since in that case $\operatorname{rank}(R+S)\le 1$, and $R+S\ne A$.)

  • Show that this number is the same for every rank $2$ matrix $A$. HINT: Try to count the $R\in\mathscr{R}$ such that $A-R\in\mathscr{R}$. Use the fact that a non-zero matrix is in $\mathscr{R}$ iff either its second row is a scalar multiple of its first row, or its first row is zero.

  • Then use again the fact that adjacency is translation-invariant (i.e., for any $A,B$ and $C$, $A$ is adjacent to $B$ iff $A+C$ is adjacent to $B+C$) to show that this number is $\mu$.

0
On

The graphs in question are the diameter-two case of the so-called bilinear forms graphs. The easiest way to prove they are strongly regular is to show that their automorphism group is a rank-three permutation group, i.e., that stabilizer of a vertex has exactly three orbits. This reduces to straightforward linear algebra - the maps that send a matrix $M$ to $AMB^T$ (with $A,B$ invertible) fixes the zero marrix and act transitively on the matrices of ranks one and two.

Counting works and is more interesting in some ways, but it is more work.