Układ Walsha

[mol_ksiazkowy]

Dla dowolnego podzbioru \(\displaystyle{ A}\) zbioru \(\displaystyle{ \{ 1, …, n \}}\) określona jest funkcja \(\displaystyle{ w_A : \{ -1, 1 \}^n \mapsto R}\) że \(\displaystyle{ w_A(x_1,…,x_n)= \prod_{j \in A} x_j}\).
Udowodnić, że dla dowolnej funkcji \(\displaystyle{ f: \{ -1, 1 \}^n \mapsto R}\) istnieją liczby \(\displaystyle{ a_A}\) takie, iż \(\displaystyle{ f = \sum_{A \subset \{1,…,n \}} a_Aw_A}\)

Niech także dla takich \(\displaystyle{ f}\) określone jest \(\displaystyle{ L f(x_1,…,x_n) = \frac{1}{n} (f(-x_1,…,x_n) + f(x_1, -x_2,…,x_n) +…+ f(x_1,…,-x_n))}\).
Udowodnić, że \(\displaystyle{ Lw_A =(1- \frac{2}{n}m(A)) w_A}\)

Uwagi: \(\displaystyle{ m(A)}\) to liczność zbioru \(\displaystyle{ A}\)

[Dasio11]

Ukryta treść:    

Na zbiorze \(\displaystyle{ V}\) wszystkich funkcji \(\displaystyle{ f : \{ -1, 1 \}^n \to \RR}\) w standardowy sposób można zadać strukturę przestrzeni liniowej. Pierwsza część zadania w istocie polega na wykazaniu, że zbiór \(\displaystyle{ \{ w_A : A \subseteq [n] \}}\) generuje \(\displaystyle{ V}\).

Dla \(\displaystyle{ \overline{x} = (x_1, \ldots, x_n) \in \{ -1, 1 \}^n}\) niech

\(\displaystyle{ \delta_{\overline{x}} = \frac{1}{2^n} \sum_{A \subseteq [n]} w_A(\overline{x}) \cdot w_A \in \mathrm{lin} \, \{ w_A : A \subseteq [n] \}.}\)

Ustalmy \(\displaystyle{ \overline{y} = (y_1, \ldots, y_n) \in \{ -1, 1 \}^n}\) i oznaczmy \(\displaystyle{ \overline{z} = (z_1, \ldots, z_n) = (x_1 \cdot y_1, \ldots, x_n \cdot y_n)}\). Wtedy mamy

\(\displaystyle{ \delta_{\overline{x}}(\overline{y}) = \frac{1}{2^n} \sum_{A \subseteq [n]} w_A(\overline{x}) \cdot w_A(\overline{y}) = \frac{1}{2^n} \sum_{A \subseteq [n]} w_A(\overline{z}) = \frac{1}{2^n} \prod_{i=1}^n (1+z_i) = \begin{cases} 1 & \text{gdy } \overline{z} = (1, \ldots, 1) \\ 0 & \text{gdy } \overline{z} \neq (1, \ldots, 1) \end{cases}}\)

czyli

\(\displaystyle{ \delta_{\overline{x}}(\overline{y}) = \begin{cases} 1 & \text{gdy } \overline{y} = \overline{x} \\ 0 & \text{gdy } \overline{y} \neq \overline{x} \end{cases}}\)

Oczywiste jest więc, że \(\displaystyle{ \left\{ \delta_{\overline{x}} : \overline{x} \in \{ -1, 1 \}^n \right\}}\) generuje \(\displaystyle{ V}\), a stąd wprost wynika teza.

Druga część: dla dowolnego \(\displaystyle{ \overline{x}}\) mamy

\(\displaystyle{ \big( w_A - L w_A \big)(\overline{x}) = \frac{1}{n} \sum_{i=1}^n \Big( w_A(x_1, \ldots, x_i, \ldots, x_n) - w_A(x_1, \ldots, -x_i, \ldots, x_n) \Big)}\)

Nietrudno sprawdzić, że dla \(\displaystyle{ i \in A}\) jest

\(\displaystyle{ w_A(x_1, \ldots, -x_i, \ldots, x_n) = -w_A(x_1, \ldots, x_i, \ldots, x_n)}\),

zatem \(\displaystyle{ i}\)-ty składnik w powyższej sumie wynosi \(\displaystyle{ 2w_A(x_1, \ldots, x_n)}\). Dla pozostałych \(\displaystyle{ i}\) zaś

\(\displaystyle{ w_A(x_1, \ldots, -x_i, \ldots, x_n) = w_A(x_1, \ldots, x_i, \ldots, x_n)}\),

przeto \(\displaystyle{ i}\)-ty składnik się zeruje. Stąd natychmiast wynika, że

\(\displaystyle{ \big( w_A - L w_A \big)(\overline{x}) = \frac{2}{n} |A| \cdot w_A(\overline{x})}\),

co po prostych przekształceniach daje tezę.