On the rank of a matrix $S$ with coefficients in $\mathbb F_{2^m}$ 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.
 A: 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.
A: 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.
A: 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$$
