# Rank of circulant matrix with $k$ ones per row

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?

• Interesting question. If I may ask, what motivates the question? Where does this come from? Oct 20, 2019 at 20:32
• @RodrigodeAzevedo brainstorming potential solution strategies for a programming contest problem I’m writing. I don’t want to be too specific or Googleable. Oct 20, 2019 at 21:33
• This question rang a bell. Sure enough, I seem to have answered a related question back in 2017. Metamorphy's answer (+1) gets to the point. Linking it because of the game/programming challenge in the other thread. Oct 21, 2019 at 18:23

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$$).