1

suppose that $G$ is connected and $A_L$ is adjacency matrix of line graph of $G$,show that the rank of $A_L$ over field $\mathbb{Z}_2$ is :

$$rank_{\mathbb{Z}_2}(A_L)=\left\{\begin{matrix} n-1 & n \: is \: odd \\ n-2& n \: is \: even \end{matrix}\right.$$

using the formula $A_L =X^T X-2I$,because we are in $\mathbb{Z}_2$ we can omit $2I$ ,so we must work with $X^T X$,which $X$ is incident matrix of $G$,now I don't know how should I continue,maybe this way is not right.

any idea,hint or theorem which I should consider will be great ,thanks!

kpax
  • 2,911

1 Answers1

3

Let $B$ be the vertex-edge incidence matrix of the connected graph $G$ on $n$ vertices. Then $\dim(\ker(B^T))=1$ and $\ker(B^TB)$ consists of the vectors $y$ such that $By=0$ and the vectors $z$ such that $Bz$ is the all-ones vector $\bf1$.

If $Bz=\bf{1}$, then $0=\bf{1}^T Bz=\bf{1}^T\bf{1}=n$. Hence if $n$ is odd and $e=|E(G)|$, we have $\ker(B)=\ker(B^TB)$ and therefore the rank of $B^TB$ is $e-(e-n+1)=n-1$.

Suppose $n$ is even. I claim there is a subset $T$ of $E(G)$ such that each vertex is incident with an odd number of edges. If $z$ is the characteristic vector of $T$ (viewed as a subset of $E(G)$), then $Bz=\bf1$. In this case the dimension of $\ker(B^TB)$ is $e-n+2$ and the rank of $B^TB$ is $n-2$.

The subset $T$ is known as a $T$-join. One construction is as follows. Divide $V(G)$ into pairs and for each pair choose a path with the vertices of the pair as its vertices of degree one. Then the mod 2 sum of the edge sets of these paths is a $T$-join.

Chris Godsil
  • 13,703