TAOCP 7.2.1.1 Exercise 35

Let $x \in [0,1)$ and write its dyadic expansion x = 0.

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.1.1: Generating All n-Tuples

Exercise 35. [HM23] [HM23] The 2n × 2n Paley matrix Pn is obtained from Paley functions just as the Walsh matrix Wn is obtained from Walsh functions. (See (20).) Find interesting relations between Pn, Wn, and the Hadamard matrix Hn. Prove that all three matrices are symmetric.

Verified: no
Solve time: 5m

Solution

Let $x \in [0,1)$ and write its dyadic expansion

$$ x = 0.x_1 x_2 x_3 \ldots,\qquad x_j \in {0,1}. $$

Let $r_j(x)$ denote the $j$-th Rademacher function,

$$ r_j(x) = (-1)^{x_j}. $$

Let $k$ have binary expansion

$$ k = (b_m \cdots b_1 b_0)_2,\qquad b_j \in {0,1}, $$

and let the Walsh function be defined by

$$ w_k(x) = \prod_{j \ge 0} r_{j+1}(x)^{b_j}. $$

Transformation under $x \mapsto 1-x$

For dyadic expansions, replacing $x$ by $1-x$ flips every binary digit in the sense that each Rademacher function changes sign:

$$ r_j(1-x) = -r_j(x), $$

since the $j$-th binary digit is complemented under $x \mapsto 1-x$ in the dyadic system, hence $(-1)^{(1-x_j)} = -(-1)^{x_j}$.

Applying this to $w_k$,

$$ w_k(1-x) = \prod_{j \ge 0} r_{j+1}(1-x)^{b_j} = \prod_{j \ge 0} (-r_{j+1}(x))^{b_j}. $$

Each factor contributes a sign $-1$ exactly when $b_j = 1$, hence

$$ w_k(1-x) = (-1)^{\sum_{j \ge 0} b_j} \prod_{j \ge 0} r_{j+1}(x)^{b_j}. $$

Let $\nu(k) = \sum_{j \ge 0} b_j$ be the number of $1$-bits in the binary expansion of $k$. Then

$$ w_k(1-x) = (-1)^{\nu(k)} w_k(x). $$

Comparison with the claimed identity

The statement to test is

$$ w_k(-x) = (-1)^k w_k(x). $$

Since Walsh functions are typically defined on $[0,1)$ and extended periodically, $-x$ corresponds to $1-x$ in this setting. The derived identity shows that the correct exponent depends on the Hamming weight $\nu(k)$, not on $k$ itself.

To disprove the claim, take $k=2$. Then $k=(10)_2$, so $\nu(k)=1$. The identity above gives

$$ w_2(1-x) = -w_2(x), $$

while

$$ (-1)^k = (-1)^2 = 1. $$

Hence

$$ w_2(1-x) \ne (-1)^k w_2(x) $$

for all $x$ where $w_2(x) \ne 0$.

The claimed identity fails.

$$ \boxed{\text{False}} $$