# A curious Hankel determinant

Define the sequence $a_{n}$ by $a_{n}=1$ if $n+1=2^k$ for some $k$ and $a_{n}=0$ else.

Computer experiments suggest that the determinant of the Hankel matrix $$H_{n+1}:=\begin{pmatrix} a_{0} & a_{1} & \dots & a_{n}\\ a_{1} & a_{2} & \dots & a_{n+1}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n} & a_{n+1} & \dots & a_{2n} \end{pmatrix}$$ satisfies $$\det{H_{n+1}}=(-1)^\binom{n+1}{2}.$$ Is there a simple way to prove this?

Edit: Let $H_{n}=(h(i,j)).$ For each $n$ there is a unique permutation of ${(0,1,\dots,n-1)}$ such that the determinant of $H_{n}$ equals $h_{0,p(0)}h_{1,p(1)}\dots h_{n-1,p(n-1)}.$

Let me show this in the following example where for clarity I have set $a(n)=x(n)$ if $n+1$ is a power of $2.$ $$H_{9}=\begin{pmatrix} x(0) & x(1) & 0 & x(3) & 0 & 0 & 0 & x(7)& 0\\ x(1) & 0 & x(3) & 0 & 0 & 0 & x(7) & 0& 0\\ 0 & x(3) & 0 & 0 & 0 & x(7) & 0 & 0& 0\\ x(3) & 0 & 0 & 0 & x(7) & 0 & 0 & 0& 0\\ 0&0&0&x(7)&0&0&0&0&0\\ 0&0&x(7)&0&0&0&0&0&0\\0&x(7)&0&0&0&0&0&0&0\\ x(7) & 0 & 0 & 0 & 0 & 0 & 0 & 0&x(15)\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & x(15)& 0 \end{pmatrix}$$ If we go from right to left we see that $p(8)=7,p(7)=8.$ Then $p(6)=1,p(5)=2,p(4)=3,p(3)=4,p(2)=5,p(1)=6.$ There remains $p(0)=0.$ In general the same procedure works. Thus my question reduces to a proof of the fact that the sign of this permutation is $(-1)^\binom{n}{2}.$

• So let's say that a permutation $\tau$ of $\left\{0,1,\ldots,n-1\right\}$ (for $n \in \mathbb{N}$) is nimble if for each $i \in \left\{0,1,\ldots,n-1\right\}$, the number $i + \tau\left(i\right)$ is a power of $2$. You claim that for each $n \in \mathbb{N}$, there exists a unique nimble permutation $\sigma_n$ of $\left\{0,1,\ldots,n-1\right\}$, and that its sign is $\left(-1\right)^{n\left(n-1\right)/2}$. I believe that this can be proven by strong induction over $n$. In the induction step, let $k \in \mathbb{N}$ be such that $2^k < n \leq 2^{k+1}$, and try to argue that any ... Jan 7, 2018 at 14:10
• ... nimble permutation $\sigma$ of $\left\{0,1,\ldots,n-1\right\}$ must send each $i > 2^{k+1}-n$ to $2^{k+1}-i$. Once this is shown, it will follow immediately that $\sigma$ restricts to an order-reversing permutation of the interval $\left[2^{k+1}-n+1, n\right]$, whereas its restriction to $\left[0, 2^{k+1}-n\right]$ is a nimble permutation of a smaller $n$; this should give a straightforward induction. Jan 7, 2018 at 14:13
• Okay, there are imprecisions in my comments. Read "a power of $2$ minus $1$" instead of "a power of $2$". Some of the strict inequality signs might be weak. But I think the idea is the right one. Jan 7, 2018 at 14:21
• Observation 1: If $i \in \left\{0,1,\ldots,n-1\right\}$ satisfies $i > 2^{k+1}-n$, then both $i$ and $2^{k+1}-i-1$ are elements of $\left\{0,1,\ldots,n-1\right\}$, and at least one of them is $\geq 2^k$. (To prove this, just assume the contrary and get the obvious contradiction.) Jan 7, 2018 at 14:22
• Observation 2: If $\sigma$ is a nimble permutation, then so is $\sigma^{-1}$. (Obvious.) Jan 7, 2018 at 14:22

Yes, there is -- but this is not really about determinants. Let me introduce some notations and state the main result.

Definition. Let $\mathbb{N}$ be the set $\left\{ 0,1,2,\ldots \right\}$. For each $i\in\mathbb{N}$ and $j\in\mathbb{N}$, we let $\left[ i,j\right]$ be the interval $\left\{ i,i+1,\ldots,j\right\}$ of $\mathbb{N}$ (this is empty when $i>j$).

For each $n\in\mathbb{N}$, we let $\left[ n\right] ^{\prime}$ be the interval $\left[ 0,n-1\right] =\left\{ 0,1,\ldots,n-1\right\}$ of $\mathbb{N}$.

Definition. Let $n\in\mathbb{N}$, and let $\sigma$ be a permutation of $\left[ n\right] ^{\prime}$. Then, $\sigma$ is said to be nimble if for each $i\in\left\{ 0,1,\ldots,n-1\right\}$, the number $i+\sigma\left( i\right) +1$ is a power of $2$.

Yes, $1$ counts as a power of $2$. The name "nimble" hints at the game of Nim (and Nim addition), but I don't have the time to figure out the exact connection.

Here is my main claim (which you conjectured):

Theorem 1. Let $n\in\mathbb{N}$.

(a) Then, there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$.

(b) This permutation $\sigma_{n}$ has sign $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$.

This permutation yields your conjecture that $\det\left( H_{n}\right) =\left( -1\right) ^{n\left( n-1\right) /2}$ for each $n\in\mathbb{N}$. Indeed, if we fix $n\in\mathbb{N}$, then the determinant of the matrix $H_{n}=\left( a_{i+j}\right) _{i\in\left[ n\right] ^{\prime};\ j\in\left[ n\right] ^{\prime}}$ rewrites as \begin{align*} \det\left( H_{n}\right) & =\sum_{\sigma\text{ is a permutation of }\left[ n\right] ^{\prime}}\left( -1\right) ^{\sigma}\underbrace{a_{0+\sigma\left( 0\right) }a_{1+\sigma\left( 1\right) }\cdots a_{n-1+\sigma\left( n-1\right) }}_{\substack{= \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\\text{(by the definition of the }a_{k}\text{)}}}\\ & =\sum_{\sigma\text{ is a permutation of }\left[ n\right] ^{\prime} }\left( -1\right) ^{\sigma} \begin{cases} 1, & \text{if }\sigma\text{ is nimble};\\ 0, & \text{if }\sigma\text{ is not nimble} \end{cases} \\ & = \sum_{\sigma\text{ is a nimble permutation of }\left[ n\right] ^{\prime} }\left( -1\right) ^{\sigma} \\ & =\left( -1\right) ^{n\left( n-1\right) /2}\qquad\left( \text{by Theorem 1}\right) . \end{align*} So it remains to prove Theorem 1.

We begin with simple lemmas:

Lemma 2. Let $n$ be a positive integer. Let $k$ be a positive integer such that $2^{k-1}<n\leq2^{k}$. Let $i\in\left[ n\right] ^{\prime}$ be such that $i\geq2^{k}-n$.

(a) Then, both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$, and at least one of them is $\geq2^{k-1}$.

(b) Let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$. Then, $\sigma\left( i\right) =2^{k}-i-1$.

Proof of Lemma 2. (a) From $i\in\left[ n\right] ^{\prime}$, we obtain $i\leq n-1<n\leq2^{k}$, so that $2^{k}-i>0$ and thus $2^{k}-i-1\geq0$. But $i\geq2^{k}-n$, so that $i+n\geq2^{k}$ and thus $2^{k}-i\leq n$. Thus, $\underbrace{2^{k}-i}_{\leq n}-1\leq n-1$. Combining this with $2^{k} -i-1\geq0$, we obtain $2^{k}-i-1\in\left[ 0,n-1\right] =\left[ n\right] ^{\prime}$. Thus, both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$ (since $i\in\left[ n\right] ^{\prime}$ by assumption). It remains to prove that at least one of them is $\geq2^{k-1}$.

Assume the contrary. Thus, none of these two numbers is $\geq2^{k-1}$. Hence, they are both $<2^{k-1}$. In other words, $i<2^{k-1}$ and $2^{k}-i-1<2^{k-1}$. From $i<2^{k-1}$, we obtain $i\leq2^{k-1}-1$ (since $i$ and $2^{k-1}$ are integers). Hence, $$2^{k}-1=\underbrace{i}_{\leq2^{k-1}-1}+\underbrace{2^{k}-i-1}_{<2^{k-1} }<2^{k-1}-1+2^{k-1}=\underbrace{2\cdot2^{k-1}}_{=2^{k}}-1=2^{k}-1.$$ This is absurd. This contradiction shows that our assumption was wrong. Hence, the proof of Lemma 2 (a) is complete.

(b) Lemma 2 (a) shows that both numbers $i$ and $2^{k}-i-1$ are elements of $\left[ n\right] ^{\prime}$, and at least one of them is $\geq2^{k-1}$. We are thus in one of the following two cases:

Case 1: We have $i\geq2^{k-1}$.

Case 2: We have $2^{k}-i-1\geq2^{k-1}$.

Let us first consider Case 1. In this case, we have $i\geq2^{k-1}$. But the permutation $\sigma$ is nimble. Hence, the number $i+\sigma\left( i\right) +1$ is a power of $2$ (by the definition of "nimble"). In other words, $i+\sigma\left( i\right) +1=2^{m}$ for some $m\in\mathbb{N}$. Consider this $m$.

From $2^{m}=\underbrace{i}_{\geq2^{k-1}}+\underbrace{\sigma\left( i\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$, we obtain $m>k-1$. Thus, $m\geq k$ (since $m$ and $k$ are integers).

On the other hand, $i\leq n-1$ (since $i\in\left[ n\right] ^{\prime}$) and $\sigma\left( i\right) \leq n-1$ (since $i\in\left[ n\right] ^{\prime}$). Hence, \begin{align*} 2^{m} & =\underbrace{i}_{\leq n-1}+\underbrace{\sigma\left( i\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Hence, $m<k+1$, so that $m\leq k$ (since $m$ and $k$ are integers). Combining this with $m\geq k$, we obtain $m=k$. Hence, $2^{m}=2^{k}$, so that $i+\sigma\left( i\right) +1=2^{m}=2^{k}$ and thus $\sigma\left( i\right) =2^{k}-i-1$. This proves Lemma 2 (b) in Case 1.

Now, let us consider case 2. In this case, we have $2^{k}-i-1\geq2^{k-1}$. But we know that $2^{k}-i-1$ is an element of $\left[ n\right] ^{\prime}$. Hence, there exists some $j\in\left[ n\right] ^{\prime}$ such that $\sigma\left( j\right) =2^{k}-i-1$ (since $\sigma$ is a permutation of $\left[ n\right] ^{\prime}$). Consider this $j$. We have $\sigma\left( j\right) =2^{k}-i-1\geq2^{k-1}$. But the permutation $\sigma$ is nimble. Hence, the number $j+\sigma\left( j\right) +1$ is a power of $2$ (by the definition of "nimble"). In other words, $j+\sigma\left( j\right) +1=2^{m}$ for some $m\in\mathbb{N}$. Consider this $m$.

From $2^{m}=\underbrace{j}_{\geq2^{k-1}}+\underbrace{\sigma\left( j\right) }_{\geq0}+\underbrace{1}_{>0}>2^{k-1}$, we obtain $m>k-1$. Thus, $m\geq k$ (since $m$ and $k$ are integers).

On the other hand, $j\leq n-1$ (since $j\in\left[ n\right] ^{\prime}$) and $\sigma\left( j\right) \leq n-1$ (since $j\in\left[ n\right] ^{\prime}$). Hence, \begin{align*} 2^{m} & =\underbrace{j}_{\leq n-1}+\underbrace{\sigma\left( j\right) }_{\leq n-1}+1\leq\left( n-1\right) +\left( n-1\right) +1=2\underbrace{n} _{\leq2^{k}}-1\\ & \leq2\cdot2^{k}-1<2\cdot2^{k}=2^{k+1}. \end{align*} Hence, $m<k+1$, so that $m\leq k$ (since $m$ and $k$ are integers). Combining this with $m\geq k$, we obtain $m=k$. Hence, $2^{m}=2^{k}$, so that $j+\sigma\left( j\right) +1=2^{m}=2^{k}$ and thus $\sigma\left( j\right) =2^{k}-j-1$. Comparing this with $\sigma\left( j\right) =2^{k}-i-1$, we find $2^{k}-i-1=2^{k}-j-1$. Hence, $i=j$. Thus, $\sigma\left( i\right) =\sigma\left( j\right) =2^{k}-i-1$. This proves Lemma 2 (b) in Case 2.

We have now proven Lemma 2 (b) in both Cases 1 and 2. Thus, Lemma 2 (b) always holds.

Lemma 3. Let $n$ be a positive integer. Let $k$ be a positive integer such that $2^{k-1}<n\leq2^{k}$. Let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$.

(a) We have $2^{k}-n<n$.

(b) The map $\sigma$ preserves the two subsets $\left[ 2^{k} -n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right]$ of $\left[ n\right] ^{\prime}$ (in other words, it maps each of these two subsets into itself).

(c) Let $\alpha$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n\right] ^{\prime}$, regarded as a map $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$. Then, $\alpha$ is a nimble permutation of $\left[ 2^{k}-n\right] ^{\prime}$.

(d) Let $\beta$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n,n-1\right]$, regarded as a map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right]$. Then, $\beta$ is the unique order-reversing permutation of this subset (i.e., it is strictly decreasing as a map).

Proof of Lemma 3. (a) We have $2^{k}=2\cdot\underbrace{2^{k-1}} _{<n}<2n=n+n$, so that $2^{k}-n<n$. This proves Lemma 3 (a).

(b) Let $i\in\left[ 2^{k}-n,n-1\right]$. Hence, $2^{k}-n\leq i\leq n-1$. Thus, $i\in\left[ n\right] ^{\prime}$ and $i\geq2^{k}-n$. Thus, Lemma 2 (b) shows that $$\sigma\left( i\right) =2^{k}-\underbrace{i}_{\leq n-1}-1\geq2^{k}-\left( n-1\right) -1=2^{k}-n.$$ Combining this with $\sigma\left( i\right) =2^{k}-\underbrace{i}_{\geq 2^{k}-n}-1\leq2^{k}-\left( 2^{k}-n\right) -1=n-1$, we obtain $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right]$.

Now, forget that we fixed $i$. We thus have shown that $\sigma\left( i\right) \in\left[ 2^{k}-n,n-1\right]$ for each $i\in\left[ 2^{k}-n,n-1\right]$. In other words, the map $\sigma$ preserves the subset $\left[ 2^{k}-n,n-1\right]$ of $\left[ n\right] ^{\prime}$. Since $\sigma$ is a permutation of $\left[ n\right] ^{\prime}$, we thus conclude that $\sigma$ also preserves the complementary subset $\left[ n\right] ^{\prime}\setminus\left[ 2^{k}-n,n-1\right] =\left[ 2^{k}-n\right] ^{\prime}$ of $\left[ n\right] ^{\prime}$. Thus, Lemma 3 (b) is proven.

(c) Lemma 3 (b) shows that the permutation $\sigma$ of $\left[ n\right] ^{\prime}$ preserves the subset $\left[ 2^{k}-n\right] ^{\prime}$ of $\left[ n\right] ^{\prime}$. Hence, it restricts to a permutation of this subset $\left[ 2^{k}-n\right] ^{\prime}$. Thus, $\alpha$ is a well-defined permutation of $\left[ 2^{k}-n\right] ^{\prime}$. It remains to show that $\alpha$ is nimble. But this is clear, because $\alpha$ is a restriction of the nimble permutation $\sigma$. Thus, Lemma 3 (c) is proven.

(d) Lemma 3 (b) shows that the permutation $\sigma$ of $\left[ n\right] ^{\prime}$ preserves the subset $\left[ 2^{k}-n,n-1\right]$ of $\left[ n\right] ^{\prime}$. Hence, it restricts to a permutation of this subset $\left[ 2^{k}-n,n-1\right]$. Thus, $\beta$ is a well-defined permutation of $\left[ 2^{k}-n,n-1\right]$. Each $i\in\left[ 2^{k}-n,n-1\right]$ satisfies \begin{align*} \beta\left( i\right) & =\sigma\left( i\right) \qquad\left( \text{since }\beta\text{ is a restriction of }\sigma\right) \\ & =2^{k}-i-1 \end{align*} (by Lemma 2 (b), since $i\geq2^{k}-n$); therefore, $\beta$ is the permutation of $\left[ 2^{k}-n,n-1\right]$ sending each $i$ to $2^{k}-i-1$. In other words, $\beta$ is the unique order-reversing permutation of this subset (i.e., it is strictly decreasing as a map). Thus, Lemma 3 (d) is proven.

Definition. Let $A$ and $B$ be two disjoint sets. Let $\alpha$ be a permutation of $A$. Let $\beta$ be a permutation of $B$. Then, the map $$A\cup B\rightarrow A\cup B,\qquad x\mapsto \begin{cases} \alpha\left( x\right) , & \text{if }x\in A;\\ \beta\left( x\right) , & \text{if }x\in B \end{cases}$$ is a permutation of the set $A\cup B$. This permutation is called the union of $\alpha$ and $\beta$, and is denoted by $\alpha\cup\beta$.

We are now ready to prove Theorem 1:

Proof of Theorem 1. (a) We shall prove Theorem 1 (a) by strong induction on $n$:

Fix $n\in\mathbb{N}$. Assume (as the induction hypothesis) that for each $g\in\mathbb{N}$ satisfying $g<n$, there is a unique nimble permutation $\sigma_{g}$ of $\left[ g\right] ^{\prime}$. We want to prove that there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$.

If $n\leq1$, then this is obvious (because there is a unique permutation of $\left[ n\right] ^{\prime}$ in this case, and its nimbleness is trivially verified). Thus, WLOG assume that $n>1$. Thus, there exists a unique positive integer $k$ satisfying $2^{k-1}<n\leq2^{k}$ (namely, this $k$ is the smallest positive integer $\ell$ satisfying $2^{\ell}\geq n$). Consider this $k$. We have $2^{k}-n<n$ (this is proven as in Lemma 3 (a)). Hence, the induction hypothesis (applied to $g=2^{k}-n$) shows that there is a unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$. Consider this $\sigma_{2^{k}-n}$.

Let $\gamma$ be the unique order-reversing permutation of the interval $\left[ 2^{k}-n,n-1\right]$ (that is, the unique strictly decreasing map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right]$). Explicitly, $\gamma$ is given by $\gamma\left( i\right) =2^{k}-i-1$ for each $i\in\left[ 2^{k}-n,n-1\right]$.

The permutations $\sigma_{2^{k}-n}$ and $\gamma$ are permutations of two complementary subsets of $\left[ n\right] ^{\prime}$ (namely, of the subsets $\left[ 2^{k}-n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right]$, respectively). Hence, their union $\sigma_{2^{k}-n}\cup\gamma$ is a well-defined permutation of $\left[ n\right] ^{\prime}$. Furthermore, this permutation $\sigma_{2^{k}-n}\cup\gamma$ is nimble.

[Proof. Let $i\in\left[ n\right] ^{\prime}$. We must prove that the number $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1$ is a power of $2$.

If $i\in\left[ 2^{k}-n\right] ^{\prime}$, then $\left( \sigma_{2^{k}-n} \cup\gamma\right) \left( i\right) =\sigma\left( i\right)$ and thus $i+\underbrace{\sigma\left( i\right) }_{=\sigma_{2^{k}-n}\left( i\right) }+1=i+\sigma_{2^{k}-n}\left( i\right) +1$ is a power of $2$ (since $\sigma_{2^{k}-n}$ is nimble). Thus, if $i\in\left[ 2^{k}-n\right] ^{\prime }$, then we are done. Hence, we WLOG assume that $i\notin\left[ 2^{k}-n\right] ^{\prime}$. Hence, $i\in\left[ n\right] ^{\prime} \setminus\left[ 2^{k}-n\right] ^{\prime}=\left[ 2^{k}-n,n-1\right]$. Therefore, $\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) =\gamma\left( i\right) =2^{k}-i-1$ (by the definition of $\gamma$), so that $i+\left( \sigma_{2^{k}-n}\cup\gamma\right) \left( i\right) +1=2^{k}$ is a power of $2$. This completes this proof.]

Thus, there exists at least one nimble permutation of $\left[ n\right] ^{\prime}$ (namely, $\sigma_{2^{k}-n}\cup\gamma$).

Now, let $\sigma$ be a nimble permutation of $\left[ n\right] ^{\prime}$.

Lemma 3 (b) shows that the map $\sigma$ preserves the two subsets $\left[ 2^{k}-n\right] ^{\prime}$ and $\left[ 2^{k}-n,n-1\right]$ of $\left[ n\right] ^{\prime}$.

Let $\alpha$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n\right] ^{\prime}$, regarded as a map $\left[ 2^{k}-n\right] ^{\prime}\rightarrow\left[ 2^{k}-n\right] ^{\prime}$. Lemma 3 (c) shows that $\alpha$ is a nimble permutation of $\left[ 2^{k}-n\right] ^{\prime}$. Thus, $\alpha=\sigma_{2^{k}-n}$ (since $\sigma_{2^{k}-n}$ is the unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$).

Let $\beta$ be the restriction of $\sigma$ to the subset $\left[ 2^{k}-n,n-1\right]$, regarded as a map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right]$. Lemma 3 (d) shows that $\beta$ is the unique order-reversing permutation of this subset. Thus, $\beta=\gamma$ (since the unique order-reversing permutation of this subset is $\gamma$).

The permutation $\sigma$ is the union of the permutations $\alpha$ and $\beta$ (since $\alpha$ and $\beta$ are the restrictions of $\sigma$ to two complementary subsets). In other words, $\sigma=\alpha\cup\beta$. In view of $\alpha=\sigma_{2^{k}-n}$ and $\beta=\gamma$, this rewrites as $\sigma =\sigma_{2^{k}-n}\cup\gamma$.

Now, forget that we fixed $\sigma$. We thus have shown that each nimble permutation $\sigma$ of $\left[ n\right] ^{\prime}$ satisfies $\sigma =\sigma_{2^{k}-n}\cup\gamma$. Hence, there exists at most one nimble permutation of $\left[ n\right] ^{\prime}$. Since we already know that there exists at least one such permutation, we thus conclude that there exists exactly one such permutation. In other words, there is a unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$. This completes the induction step. Hence, Theorem 1 (a) is proven.

(b) We shall prove Theorem 1 (b) by strong induction on $n$:

Fix $n\in\mathbb{N}$. Assume (as the induction hypothesis) that for each $g\in\mathbb{N}$ satisfying $g<n$, the unique nimble permutation $\sigma_{g}$ of $\left[ g\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{g} }=\left( -1\right) ^{g\left( g-1\right) /2}$. We want to prove that the unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$.

If $n\leq1$, then this is obvious. Hence, WLOG assume that $n>1$. Thus, there exists a unique positive integer $k$ satisfying $2^{k-1}<n\leq2^{k}$ (namely, this $k$ is the smallest positive integer $\ell$ satisfying $2^{\ell}\geq n$). Consider this $k$. Notice that $k$ is positive; thus, $2^{k}$ is even.

We have $2^{k}-n<n$ (this is proven as in Lemma 3 (a)). Hence, the induction hypothesis (applied to $g=2^{k}-n$) shows that the unique nimble permutation $\sigma_{2^{k}-n}$ of $\left[ 2^{k}-n\right] ^{\prime}$ has sign $$\left( -1\right) ^{\sigma_{2^{k}-n}}=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}.$$

Let $\gamma$ be the unique order-reversing permutation of the interval $\left[ 2^{k}-n,n-1\right]$ (that is, the unique strictly decreasing map $\left[ 2^{k}-n,n-1\right] \rightarrow\left[ 2^{k}-n,n-1\right]$). Explicitly, $\gamma$ is given by $\gamma\left( i\right) =2^{k}-i-1$ for each $i\in\left[ 2^{k}-n,n-1\right]$.

A well-known fact says the following: If $m\in\mathbb{N}$, and if $M$ is an $m$-element set of integers, then the unique order-reversing permutation of the set $M$ has sign $\left( -1\right) ^{m\left( m-1\right) /2}$. Applying this to $m=2n-2^{k}$ and $M=\left[ 2^{k}-n,n-1\right]$, we conclude that the unique order-reversing permutation of the set $\left[ 2^{k}-n,n-1\right]$ has $\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k} -1\right) /2}$. Since this permutation is $\gamma$, we thus have proven that $$\left( -1\right) ^{\gamma}=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}.$$

In the proof of Theorem 1 (a), we have shown that each nimble permutation $\sigma$ of $\left[ n\right] ^{\prime}$ satisfies $\sigma=\sigma_{2^{k} -n}\cup\gamma$. Applying this to $\sigma=\sigma_{n}$, we conclude that $\sigma_{n}$ satisfies $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$.

But if $A$ and $B$ are two disjoint finite sets, and if $\alpha$ and $\beta$ are permutations of $A$ and $B$ (respectively), then the union $\alpha \cup\beta$ of $\alpha$ and $\beta$ has sign $\left( -1\right) ^{\alpha \cup\beta}=\left( -1\right) ^{\alpha}\left( -1\right) ^{\beta}$. Applying this to $A=\left[ 2^{k}-n\right] ^{\prime}$, $B=\left[ 2^{k}-n,n-1\right]$, $\alpha=\sigma_{2^{k}-n}$ and $\beta=\gamma$, we conclude that the union $\sigma_{2^{k}-n}\cup\gamma$ has sign \begin{align*} \left( -1\right) ^{\sigma_{2^{k}-n}\cup\gamma} & =\underbrace{\left( -1\right) ^{\sigma_{2^{k}-n}}}_{=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}}\underbrace{\left( -1\right) ^{\gamma} }_{=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}\\ & =\left( -1\right) ^{n\left( n-1\right) /2} \end{align*} (since $$\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2\equiv n\left( n-1\right) /2\operatorname{mod}2$$ (because \begin{align*} & \left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2+\left( 2n-2^{k} \right) \left( 2n-2^{k}-1\right) /2-n\left( n-1\right) /2\\ & =\left( n-2^{k}\right) \underbrace{\left( 2n-2^{k}\right) }_{\substack{\equiv0\operatorname{mod}2\\\text{(since }2^{k}\text{ is even)} }}\equiv0\operatorname{mod}2 \end{align*} )). In view of $\sigma_{n}=\sigma_{2^{k}-n}\cup\gamma$, this rewrites as $\left( -1\right) ^{\sigma_{n}}=\left( -1\right) ^{n\left( n-1\right) /2}$. So we have proven that the unique nimble permutation $\sigma_{n}$ of $\left[ n\right] ^{\prime}$ has sign $\left( -1\right) ^{\sigma_{n} }=\left( -1\right) ^{n\left( n-1\right) /2}$. This completes the induction step. Hence, Theorem 1 (b) is proven.

Remark. Our recursive proof of Theorem 1 (a) can be used to show that the permutation $\sigma_{n}$ is an involution (i.e., it equals its own inverse) and has no fixed points except possibly $1$ (because the permutation $\gamma$ is an order-reversing permutation of a set of even size, and such permutations never have fixed points). Thus, the cycle type of $\sigma_{n}$ is $\left( \underbrace{2,2,\ldots,2}_{n/2\text{ times}}\right)$ when $n$ is even, and $\left( \underbrace{2,2,\ldots,2}_{\left(n-1\right)/2\text{ times}},1\right)$ otherwise. This gives another way of computing the sign of $\sigma_{n}$, and thus of proving Theorem 1 (b).

• @ darij: thank you for this very clear and instructive proof! Jan 9, 2018 at 12:09
• Very impressive ! Jan 14, 2018 at 8:22

Edit: following our exchange, I modify the presentation of what is now a partial result.

I will stick to your notations. For example $$H_8$$ is the $$2^3 \times 2^3$$ Hankel matrix:

$$H_{8}:=\begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \vdots &\vdots & \vdots & \vdots & \vdots\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$

We are going to prove a restricted version of your result, i.e., we will prove that, for $$k\geq 2$$:

$$\det(H_{2^k})=1$$

complying with formula $$(-1)^{\binom{2^k}{2}}=(-1)^{\tfrac{2^k(2^k-1)}{2}}=1.$$

Let us set, for notational convenience, $$K_n=H_{2^n}$$.

$$K_n$$ possesses a recursive structure with the form :

$$\tag{1}K_{n+1}= \begin{pmatrix}K_{n} & J_{n}\\J_{n} & 0_{n}\end{pmatrix}$$

where $$J_n$$ is the anti-diagonal matrix (with ones on the secondary diagonal) and $$0_{n}$$ is the all-zero matrix, both of size $$2^n \times 2^n$$.

Now (1) allows to work by recursion for obtaining $$\det(K_n)$$ by using the Schur formula for $$2 \times 2$$ block-defined matrices :

$$M=\begin{pmatrix}A & B\\C & D\end{pmatrix} \ \ \implies \ \ \det(M)=\det(A)det(D-CA^{-1}B)$$

giving here:

$$det(K_{n+1})=\det(K_n)\det(-JK_{n}^{-1}J)=\det(K_n)\det(-I)\det(J)\det(K_{n}^{-1})\det(J)=$$

$$det(-I)det(J_n^2)\det(K_nK_{n}^{-1})=(-1)^{2^n}=\begin{cases}-1 & (n=0)\\+1& (n>0) \end{cases}$$

(where $$I$$ denotes the identity matrix with $$2^n \times 2^n$$ elements).

Explanations: $$\det(J_n^2)=\det(I)=1$$ and $$\det(-I_k)=(-1)^k$$.

A Matlab program for the recursive generation of matrix $$K_{2^p}$$ (here with $$p=2$$):

p=2;
K=[1];J=[1];Z=[0];
for k=1:p
K=[K,J;J,Z]
J=[Z,J;J,Z];
Z=[Z,Z;Z,Z];
end;
K


Edit : I wonder if a simple solution couldn't be achieved by using [Lucas Theorem] (https://en.wikipedia.org/wiki/Lucas%27s_theorem)

• Sorry, I made a mistake which is now corrected. But what you denote by $H_{3}$ is in my notation $H_{8}$. Jan 6, 2018 at 12:57
• For example $\det{H_{2}}= \det\begin{pmatrix} 1 & 1 \\1 & 0 \end{pmatrix}= -1$ and $\det{H_{3}}= \det\begin{pmatrix} 1 & 1&0 \\1 & 0 &1\\0 &1&0 \end{pmatrix}= -1$. Jan 6, 2018 at 13:09
• I see. I thought the matrices were $2^n \times 2^n$. My method should still be applicable (the $2 \times 2$ block formulation I give with the Schur determinant formula does not necessitate to have $B$ and $C$ square. Only $A$ and $D$ must be square). Jan 6, 2018 at 13:52
• I have modified my text in order to comply with your objectives. I confirm also the signs checked on a large number of simulations. I haven't found till now how to tackle the general case. Jan 7, 2018 at 8:09
• Thank you for your interesting computation of $H_{2^n}$. This special case is also almost obvious from the usual definition of a determinant $detA=\sum{a_{1,p(1)}a_{2,p(2)}\dots a_{n,p(n)}}$ over all permutations $p$, because in this case we have ones in the secondary diagonal. The sign of the corresponding permutation is $\binom{n}{2}.$ It seems that also in the general case only one permutation is possible, but I cannot give a precise proof of this fact. Jan 7, 2018 at 8:20