# Is $F(F(A)) = A$ for every k-hypercube where k is odd?

Suppose we have a k-hypercube $$(Q_k)$$ where $$k$$ is an odd integer.

Define $$F(A)$$ for $$A \subseteq V$$ as the set of all vertices such that has odd number of edges to the set $$A$$.

Is it true that $$F(F(A)) = A$$?

Yes, let $$M$$ be the adjacency matrix of $$Q_k$$ over $$F_2$$, $$V$$ be the $$F_2$$-vector space with basis $$(v_u)$$ indexed by the vertex set of $$Q_k$$, denote $$v_A=\sum_{u\in A}v_u$$. We see that $$Mv_A=v_{F(A)}$$ so $$v_{F(F(A))}=M^2v_A$$, we just need to prove that $$M^2$$ is an identify matrix. The $$(u,w)$$ entry of $$M^2$$ is the number of walks of length $$2$$ from $$u$$ to $$w$$, when in $$F_2$$, it is $$0$$ if there are an even number of such walks and $$1$$ if otherwise:

-If $$u=w$$, there is $$k$$ walks of length $$2$$, go from $$u$$ to one of the adjacency vertex of $$u$$, and go back to $$u$$, because $$k$$ is odd, the $$(u,u)$$ entry is $$1$$.

-If $$d(u,w)=1$$ or $$d(u,w)>2$$, there is no walks of length $$2$$ from $$u$$ to $$w$$, so the $$(u,w)$$ entry is $$0$$.

-If $$d(u,w)=2$$, there are $$2$$ walks of length $$2$$ from $$u$$ to $$w$$, so the $$(u,w)$$ entry is also $$0$$.

So $$M^2$$ is the identify matrix as we want.

• A simpler (in my opinion) way to see that $M^2 = I$: notice that $M = M_1 + \cdots + M_k$ where $M_i$ sends a vertex om the hypercube to the adjacent vertex in the $e_i$-direction. Then modulo $2$ we have $M^2 = M_1^2 + \cdots + M_k^2 = I$ because it is easy to see that $M_i^2 = I$. Apr 22, 2023 at 15:13
• Lemma 1: $$\space F(U \Delta V) = F(U) \Delta F(V)$$.

Prove: By using $$S_1 = S_2 \iff S_1 \subseteq S_2 \land S_2 \subseteq S_1$$ we can prove this equality.

1. Suppose $$c \in F(U \Delta V)$$, we know $$c$$ has odd number of neighbors in $$U \Delta V$$ by the definition of $$F$$. By parity and the definition of symmetric difference we know $$c$$ has odd number of neighbors to exactly one of the $$U \setminus V$$ and $$V \setminus U$$; It means $$c$$ has odd number of neighbors in exactly one of the $$U$$ and $$V$$ which implies that $$c \in F(U) \Delta F(V)$$. This proves $$F(U \Delta V) \subseteq F(U) \Delta F(V)$$.
2. Suppose $$w \in F(U) \Delta F(V)$$, we know $$w$$ has odd number of neighbors in exactly one of the $$U$$ and $$V$$ by the definition of $$F$$ and symmetric difference; It means $$w$$ has odd number of neighbors in exactly one of the $$U \setminus V$$ and $$V \setminus U$$ which implies that $$w \in F(U \Delta V)$$. This proves $$F(U) \Delta F(V) \subseteq F(U \Delta V)$$.

By combining these two together we will have $$F(U \Delta V) = F(U) \Delta F(V)$$.

• Lemma 2: $$F(F(\{x\})) = \{x\}$$.
Prove: It's easy to prove by using the definition of $$F$$ and using the fact that $$k$$ is odd which tell us that $$deg(x)$$ is odd.

Suppose $$A = \{ a_i \} _{i=1}^n$$. By using lemmas we proved and also applying easy induction on Lemma 1 to get the general form of that (for more than two sets) we will have: $$F(F(A)) = F(F(\{ a_i \} _{i=1}^n)) = F(F(\Delta_{i=1}^n a_i)) = F(\Delta_{i=1}^n F(a_i)) = \Delta_{i=1}^n F(F(a_i)) = \Delta_{i=1}^n a_i = \{ a_i \} _{i=1}^n = A$$ And done we proved $$F(F(A)) = A$$. $$\tag*{\blacksquare}$$