6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there any conditions on $s_1$, $s_3$, ..., $s_{2k-1}$ or are they just general members of the field? $\endgroup$ – David E Speyer Jan 17 '14 at 19:25
  • $\begingroup$ Checked by computer up to $k=5$ (with $s_1$, $s_2$, ..., $s_{2k-1}$) treated as independent elements of the field. $\endgroup$ – David E Speyer Jan 17 '14 at 20:01
  • 1
    $\begingroup$ @David Speyer. No, the $s_i$ are just generic elements of the field $\mathbb F$. The only condition is $s_{2i}=s_i^2$. $\endgroup$ – Sfarla Jan 18 '14 at 16:46
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I've just read the proof and it works. There is only a detail i think is not correct. The set that we can map bijectively into $A_q$ is not $C_p$ but $B_p$ through the map $(i_1, \ldots, i_j, 2t, i_{j+2}, \ldots, i_{2j+1}) \rightarrow (i_1, \ldots, i_j, t)$. But the proof is correct. Thank you very much. $\endgroup$ – Sfarla Jan 18 '14 at 21:23
  • $\begingroup$ You are right. I have corrected the proof. $\endgroup$ – Clément de Seguins Pazzis Jan 18 '14 at 23:03
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice remark!! $\endgroup$ – Clément de Seguins Pazzis Jan 20 '14 at 8:57
  • 1
    $\begingroup$ I tried to use generating function but the only thing that i found is that, namely $S(x)= \sum_{i=0}^n s_nx^n$, then $xS'(x)=S(x)+S^2(x)$ (where $S'(x)$ is the formal derivative of $S(x)$), but i don't know if it's useful. Could you explain better what are you trying to do and how did you obtain the identity above? $\endgroup$ – Sfarla Jan 20 '14 at 18:10
  • 1
    $\begingroup$ The big sum over $A_p$ in my proof is the coefficient of index $2p$ in the formal power series $\Bigl(\sum_{n \geq 1} s_{2n-1}x^{2n-1}\Bigr)^2\sum_{k \geq 0} \Bigl(\sum_{i\geq 1} s_{2i} x^{2i}\Bigr)^k$. $\endgroup$ – Clément de Seguins Pazzis Jan 20 '14 at 21:23
  • 1
    $\begingroup$ Ok I've just completed the proof using generating functions. It's quite easy to show the identity $\left(\sum_{n\geq 1}s_{2n-1}x^{2n-1}\right)^2\sum_{k\geq 0}\left(\sum_{i\geq 1}s_{2i}x^{2i}\right)^k=\sum_{p\geq 1}s_{2p}x^{2p}$. Thank you very much. $\endgroup$ – Sfarla Jan 20 '14 at 23:20
1
$\begingroup$

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

$\endgroup$

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.