On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$

Question

Let $\mathbb F$ be a finite field with characteristic 2 and let $S \in M(2k, 2k, \mathbb F)$ be the matrix defined as follows $$ S=\left[\begin{array}{ccccccc} 0 & \cdots & & & 0 & 1 & s_1 \\ 0 & \cdots & & & 0 & s_1 & s_2 \\ 0 & \cdots & & 1 & s_1 & s_2 & s_3 \\ 0 & \cdots & 0 & s_1 & s_2 & s_3 & s_4 \\ \vdots & & & & & &\vdots \\ 1 & s_1 & & \cdots & & & s_{2k-1} \\ s_1 & s_2 & & \cdots & & &s_{2k} \end{array}\right],$$ with $s_{2i}=s_i^2$ $\;\;\forall \;i=1, \ldots, k$. Show that the rank of $S$ is exactly $k$.

Obviously the rank is at least $k$, since the odd rows (or the columns) are linearly independent.

This problem comes up studying binary BCH codes.

Answer 1

The result is true indeed. Here is a rather technical solution. I work by induction over $k$, thus denoting by $S_k$ the above $(2k)\times(2k)$ matrix. Let us transform the matrix through the following series of row and column operations: $C_{2k} \leftarrow C_{2k}+s_1 C_{2k-1}$ and then, for odd $j$ from $3$ to $2k-3$,
$L_k \leftarrow L_k+s_{k-j}L_j$ for $k$ from $j+1$ to $2k$.

After those operations, the matrix obtained from $S_k$ has the following form: $$S'_k=\begin{bmatrix} 0 & D \\ T & ? \end{bmatrix} $$ where $D=\begin{bmatrix} 1 & 0 \\ s_1 & 0 \end{bmatrix}$, the odd-labelled columns of $T$ are $\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ 0 \\ 1 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, ..., $\begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix}$, and $T$ is equivalent to $S_{k-1}$.

By the induction hypothesis $T$ has rank $k-1$ and hence its column space is spanned by the above vectors. To conclude that $S_k$ has rank $k$ we then need to prove that the even-labelled entries in the last column of $S'_k$ are all zero.

Let $p \in \{2,...,k\}$. By careful examination, one finds that the $(2p,2k)$-entry of $S'_k$ equals $$s_{2p}+\sum_{(i_1,\dots,i_\ell) \in A_p} s_{i_1} s_{i_2}\cdots s_{i_l}$$ where $A_p$ is the set of all lists $(i_1,\dots,i_\ell)$ of positive integers whose sum is $2p$ and in which $i_1$ and $i_\ell$ are odd and the other entries are even. Now, we show by induction that this sum equals $s_{2p}$. First of all, $\theta : (i_1,\dots,i_\ell) \mapsto (i_\ell,\dots,i_1)$ is an involution on $A_p$, and as $\mathbb{F}$ has characteristic $2$ we deduce that $$\sum_{(i_1,\dots,i_\ell) \in A_p} s_{i_1} s_{i_2}\cdots s_{i_l}= \sum_{(i_1,\dots,i_\ell) \in A_p,(i_1,\dots,i_\ell)=(i_\ell,\dots,i_1)} s_{i_1} s_{i_2}\cdots s_{i_l}.$$

Next, if we have a symmetric list $(i_1,\dots,i_{2j})=(i_{2j},\dots,i_1)$ in $A_p$ with an even number of entries and $j \geq 2$, we use equality $s_{i_j}s_{i_{j+1}}=s_{i_j}^2=s_{2i_j}$ to see that it defines the same product has the symmetric list $(i_1,\dots,i_{j-1},2i_j,i_{j+2},\dots,i_{2j})$ with $2j-1$ entries. Pairing lists in this manner and - if $p$ is odd - noting that $s_p^2=s_{2p}$, we find that $$\sum_{(i_1,\dots,i_\ell) \in A_p} s_{i_1} s_{i_2}\cdots s_{i_l}= \begin{cases} s_{2p}+\sum_{(i_1,\dots,i_\ell) \in B_p} s_{i_1} s_{i_2}\cdots s_{i_l} & \text{if $p$ is odd} \\ \sum_{(i_1,\dots,i_\ell) \in B_p} s_{i_1} s_{i_2}\cdots s_{i_l} & \text{if $p$ is even,} \end{cases} $$ where $B_p$ denotes the subset of $A_p$ consisting of the symmetric lists $(i_1,\dots,i_{2j+1})$ in which $i_{j+1}=2t$ for some odd integer $t$. If $p$ is odd then $B_p$ is empty and we are done.

Assume now that $p=2q$ for some integer $q$. Then, $(i_1,...,i_{2j+1}) \mapsto (i_1,...,i_{j-1},i_j,(i_{j+1})/2)$ maps $B_p$ bijectively onto $A_q$, and using $s_{i_{j+1}}=s_{(i_{j+1}/2)}^2$ we deduce that $$\sum_{(i_1,\dots,i_\ell) \in B_p} s_{i_1} s_{i_2}\cdots s_{i_l} =\Bigl(\sum_{(i_1,\dots,i_\ell) \in A_q} s_{i_1} s_{i_2}\cdots s_{i_l}\Bigr)^2.$$ By induction, we deduce that $$\sum_{(i_1,\dots,i_\ell) \in B_p} s_{i_1} s_{i_2}\cdots s_{i_l} =(s_{2q})^2=s_{2p},$$ QED.

Answer 2

A more succinct proof can be given using generating functions. I won't give the details, but it boils down to the identity $$ \frac{\sum_{n\geq 1} s_{2n-1}x^n}{\sum_{n\geq 0} s_{2n}x^n} = \frac{\sum_{n\geq 1} s_{2n}x^{n+1}}{\sum_{n\geq 1} s_{2n-1}x^n}, $$ where $s_0=1$ and the computations are mod 2, of course.

Incidentally, if you expand either side of the above identity as a power series in $x$, then the coefficient of $x^n$ is a polynomial $p_n(s_1,s_3,s_5,\dots)$. It appears that the number of terms of $p_n$ is the number of ways to write $n$ as a sum of powers of 2, without regard to order of the summands. I have not tried to prove this, so perhaps someone can supply a proof. A bijective proof would be especially interesting.

Answer 3

Here is a simplified answer expanding Richard Stanley's remark.

As I have already pointed out in my first answer, the only difficulty is to prove that the last column of the matrix is a linear combination of the odd-labelled columns. To obtain this result, it suffices to prove that, with $s_0:=1$ and the formal power series $A:=\sum_{n \geq 0} s_n x^n$, there is a sequence $(t_n)_{n \geq 0}$ of elements of $\mathbb{F}$ such that $$\frac{1}{x}(A+1)=\sum_{n \geq 0} t_n x^{2n} A.$$ Noting that $A$ is invertible, this amounts to proving that the odd coefficients of the formal power series $\frac{A+1}{xA}$ are all zero. This is obtained by noting that $\sum_{n \geq 0} s_{2n+1}x^{2n+1}=A+A^2$, whence $$\frac{A+1}{xA}=\frac{\sum_{n \geq 0} s_{2n+1}x^{2n}}{A^2} =\frac{\sum_{n \geq 0} s_{2n+1}x^{2n}}{\sum_{n \geq 0} s_{2n}x^{2n}}\cdot$$