5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Interesting question. If I may ask, what motivates the question? Where does this come from? $\endgroup$ Oct 20, 2019 at 20:32
  • 1
    $\begingroup$ @RodrigodeAzevedo brainstorming potential solution strategies for a programming contest problem I’m writing. I don’t want to be too specific or Googleable. $\endgroup$
    – user7530
    Oct 20, 2019 at 21:33
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 21, 2019 at 18:23

1 Answer 1

4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.