Rank of circulant matrix with $k$ ones per row

Question

Consider the $n\times n$ matrix over the field $\mathbb F_2$ formed by creating the circulant matrix of the vector consisting of $k$ ones followed by $n-k$ zeroes. E.g., for $n=4$ and $k=2$, the resulting matrix is

$$\begin{bmatrix}1 & 1 & 0 & 0\\ 0 & 1 & 1 & 0\\0 & 0 & 1 & 1\\1 & 0&0 &1\end{bmatrix}.$$

What is the rank of this matrix?

I suspect the answer is $n-d+1$, where $d=\gcd(n,k)$. I can prove this is an upper bound on the rank, since the following vectors are linearly independent and lie in the kernel of the matrix: $$\begin{bmatrix}1 & (i\ \textrm{zeroes}) & 1 & (d-2-i\ \textrm{zeroes}) & 1 & (i\ \textrm{zeroes}) & \cdots \end{bmatrix}$$ with $d-1$ different choices for $i$. Is there an easy way to see that these completely describe the kernel?

Answer 1

The answer is $\begin{cases}n-d,&2\mid k/d\\n-d+1,&2\not\mid k/d\end{cases}$, where $d=\gcd(n,k)$ as in the OP. In case of an arbitrary field of characteristic $p$ (including $p=0$), this holds with $2$ replaced by $p$.

For a proof, let $\mathbb{F}$ be a field of characteristic $p$, $A$ be the "left cyclic shift" operator on $\mathbb{F}^n$: $$A(x_1,x_2,\ldots,x_n):=(x_2,\ldots,x_n,x_1),$$ and let $f_k(x)=\sum_{j=0}^{k-1}x^j\in\mathbb{F}[x]$. The matrix being considered is then that of $f_k(A)$.

Note that $A^n$ is the identity operator, hence the kernel of $f_k(A)$ is equal to the kernel of $g(A)$, where $$g(x)=\gcd\big(x^n-1,f_k(x)\big)$$ (computed over $\mathbb{F}$; recall a proof: $g(x)=u(x)(x^n-1)+v(x)f_k(x)$ for some $u,v\in\mathbb{F}[x]$, hence $g(A)=v(A)f_k(A)$ and $\operatorname{ker}f_k(A)\subseteq\operatorname{ker}g(A)$; conversely, $g(x)$ divides $f_k(x)$...). Since $$\gcd(x^n-1,x^k-1)=x^d-1,$$ and the remainder of $f_k(x)$ divided by $x^d-1$ is equal to $(k/d)f_d(x)$, we have $$g(x)=\begin{cases}x^d-1,&p\mid k/d,\\f_d(x),&p\not\mid k/d\end{cases}.$$ Thus, if $k/d$ is a multiple of $p$, the kernel consists of all vectors $(x_1,\ldots,x_n)$ such that $x_{j+d}=x_j$ for all $j$ (and therefore has dimension $d$); otherwise, we have an additional constraint $x_1+\ldots+x_d=0$ (giving dimension $d-1$).