4
$\begingroup$

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

$\endgroup$
13
  • 1
    $\begingroup$ 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 ... $\endgroup$ Jan 7, 2018 at 14:10
  • 1
    $\begingroup$ ... 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. $\endgroup$ Jan 7, 2018 at 14:13
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 7, 2018 at 14:21
  • $\begingroup$ 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.) $\endgroup$ Jan 7, 2018 at 14:22
  • $\begingroup$ Observation 2: If $\sigma$ is a nimble permutation, then so is $\sigma^{-1}$. (Obvious.) $\endgroup$ Jan 7, 2018 at 14:22

2 Answers 2

3
$\begingroup$

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, \begin{equation} 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. \end{equation} 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 \begin{equation} \sigma\left( i\right) =2^{k}-\underbrace{i}_{\leq n-1}-1\geq2^{k}-\left( n-1\right) -1=2^{k}-n. \end{equation} 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 \begin{equation} 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} \end{equation} 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 \begin{equation} \left( -1\right) ^{\sigma_{2^{k}-n}}=\left( -1\right) ^{\left( 2^{k}-n\right) \left( 2^{k}-n-1\right) /2}. \end{equation}

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 \begin{equation} \left( -1\right) ^{\gamma}=\left( -1\right) ^{\left( 2n-2^{k}\right) \left( 2n-2^{k}-1\right) /2}. \end{equation}

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 \begin{equation} \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 \end{equation} (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).

$\endgroup$
2
  • 1
    $\begingroup$ @ darij: thank you for this very clear and instructive proof! $\endgroup$ Jan 9, 2018 at 12:09
  • $\begingroup$ Very impressive ! $\endgroup$
    – Jean Marie
    Jan 14, 2018 at 8:22
2
$\begingroup$

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)

$\endgroup$
8
  • $\begingroup$ Sorry, I made a mistake which is now corrected. But what you denote by $H_{3}$ is in my notation $H_{8}$. $\endgroup$ Jan 6, 2018 at 12:57
  • $\begingroup$ 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$. $\endgroup$ Jan 6, 2018 at 13:09
  • $\begingroup$ 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). $\endgroup$
    – Jean Marie
    Jan 6, 2018 at 13:52
  • $\begingroup$ 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. $\endgroup$
    – Jean Marie
    Jan 7, 2018 at 8:09
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 7, 2018 at 8:20

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.