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.



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


