Nullities for a class of skew-symmetric Toeplitz band matrices

For all $n>k\ge 1$, we give formulas for the nullity $N(n,k)$ of the $n \times n$skew-symmetricToeplitzbandmatrixwhosefirst$k$ superdiagonals have all entries $1$ and whose remaining superdiagonals have all entries $0$. This is accomplished by counting the number of cycles in certain directed graphs. As an application, for each fixed integer $z\ge 0$ and large fixed $k$, we give an asymptotic formula for the percentage of $n>k$ satisfying $N(n,k)=z$. For the purpose of rapid computation, an algorithm is devised that quickly computes $N(n,k)$ even for extremely large values of $n$ and $k$.