The number of entries equal to 1 in a binary matrix and the number of directed cycles in the graph corresponding to the matrix

61 Views Asked by At

Let $G$ be a directed graph (with loops) of $p$ vertices and $A(G)$ be the $p\times p$ adjacency matrix of $G$. Assume that $A(G)$ is nilpotent modulo $p$. This means that the number of walks of length $p$ of $G$ is a multiple of $p$. Now, assume that the main diagonal of $A(G)$ is full of 1. This means that every vertex of $G$ has loop. For example, $p=2$ and $A(G)=\begin{bmatrix}1&1\\ 1& 1\end{bmatrix}$ is such a matrix. I would like to prove that for every prime number $p$, such binary $p$-nilpotent matrices should have be equal to the all ones matrix. Does any one has any idea about that or about the bounds for the numbers of entries equal to one of such nilpotent matrices?