\documentclass{amsart}
\usepackage{amssymb,amsfonts,latexsym,amsmath}

\begin{document}
\title{Chapter 3 Reflective transformations}

\begin{abstract} A reflective transformation is a one-to-one
transformation of $\mathbf{Q}^{n}$ such that its inverse is
isometrically similar to itself.  After basic properties of
reflective transformations are given in Section 3.1, any
Boolean isometry is proved to be reflective through a Boolean
isometry of order 2.  Then conditions for reflectiveness are
given for [\;]-representations of self-dual transformations.  
Next, reflective circular transformations are described in
Section 3.4.  Finally, methods of constructing reflective
transformations through face copies and orbit modifications are
described.           
\end{abstract}
\maketitle


\section*{3.1 Reflective transformations\label{s:RT}}
A self-dual transformation and a circular transformation of
$\mathbf{Q}^{n}$ discussed in Chapter 2 are defined as trans-
formations $F$ commutative with the complementation $\bar{\neg}$
and
the rotation $\rho $ respectively, that is   
$$
        F = (\bar{\neg})^{-1}F\bar{\neg} \quad \mbox{and} \quad F
= \rho ^{-1}F\rho 
$$
respectively.  On the other hand, there is a class of one-to-one
transformations $F$ such that 
$$
        F^{-1} = T^{-1}FT
\eqno (3.1.1) 
$$
for some Boolean isometry $T$, that is, $F^{-1}$ is isometrically
similar to $F$.  Note that the condition (3.1.1) is equivalent to
$$
        FTF = T. 
\eqno (3.1.2) 
$$
We call such a transformation reflective through $T$.  For
example, a \emph{binary-reflected Gray code} for dimension $n$
introduced by Gray (1953) is the graph of a transformation
reflective through $n^{-}$ and also $(n-1)^{-}$.  One-to-one
\emph{threshold transformations} constructed in the next two
chapters are not only self-dual but also often turn out to be
reflective.  In the next section, we prove that any Boolean
isometry is reflective through some Boolean isometry of order
2.\\

\textbf{Example 3.1.1}  Let $f_{1} = \{  110\}$, $f_{2} = \{ 
110\}$, $f_{3} = \{  111\}$.  Then the graph of $F =
[f_{1},f_{2},f_{3}]$ consists of loops and one 4-cycle, that is
$$
        110 \rightarrow  000 \rightarrow  001 \rightarrow  111
\rightarrow  110.
$$
$F$ is reflective through $\{ 1,2\}^{-}$ and also reflective
through $3^{-}$.\\  

\textbf{Proposition 3.1.2}  Let $F$ be reflective through $T$. 
Then (i) if $F$ is commutative with an isometry $S$, then $F$ is
reflective through $ST$ and $TS$; (ii) if $F$ is reflective
through $S$, then $F$ is commutative with $ST$.

\begin{proof}  (i) $(ST)^{-1}F(ST) = T^{-1}S^{-1}FST = T^{-
1}(S^{-1}SF)T = T^{-1}FT = F^{-1}$. $(TS)^{-1}F(TS) = S^{-1}T^{-
1}FTS = S^{-1}F^{-1}S = (FS)^{-1}S = (SF)^{-1}S = F^{-1}S^{-1}S =
F^{-1}$.  (ii) is similarly proved.
\end{proof}


\textbf{Corollary 3.1.3}  Let $\mathbf{N} = J\cup K$ and $J\cap K
=
\emptyset $.  If $F$ is self-dual and reflective through $J^{-}$
then $F$ is reflective through $K^{-}$. 

\begin{proof}  Let $T = J^{-}$ and $S = \bar{\neg}$ in (i) of
Proposition 3.1.2.
\end{proof}

\textbf{Corollary 3.1.4}  If $F$ is a transformation of
$\mathbf{Q}^{n}$, then the set of all T such that $F$ is
commutative with $T$ or reflective through $T$ is a subgroup of
$O(\mathbf{Q}^{n})$.\\

If $F$ is reflective through $T$, then $U^{-1}FU$ is reflective
through $U^{-1}TU$ for any isometry $U$. If $F$ and $G$ are
reflective through $T$ and $FG = GF$, then $FG$ is reflective
through $T$.  In particular, if $F$ is reflective through $T$,
then $F^{i}$ is reflective through $T$ for every positive integer
$i$.  Since $\mathbf{Q}^{n}$ is a finite set, there exists a
positive integer $k$ such that $F^{k} = I$.  Therefore, $F^{-1} =
F^{k-1}$, hence, if $F$ is reflective through $T$ then $F^{-1}$
is reflective through $T$.  If $F$ is self-dual and reflective
through $T$, then $T^{-1}(\bar{\neg}F)T = \bar{\neg}T^{-1}FT =
\bar{\neg}F^{-1}
= (\bar{\neg}F)^{-1}$, so that $\bar{\neg}F$ is reflective
through $T$.

Assume that $F$ is reflective through $S$, $G$ is reflective
through $T$, $F$ is commutative with $G$ and $T$, and $G$ is
commutative with $S$.  Then by Proposition 3.1.2 (i), $F$ is
reflective through $ST$, and $G$ is reflective through $ST$. 
Further, since $F$ is commutative with $G$, $FG$ is reflective
through $ST$.  Similarly, $FG$ is reflective through $TS$.  If
$F$ is reflective through $T$, and if $S$ is an isometry of order
2 such that $ST = TS$, then $SF$ is reflective through $ST$.

    If F is reflective through $T$, then $(TF)^{2} = T^{2}$.  In
particular, if the order of $T$ is 2, then $F$ is isometrically
equivalent to a transformation whose graph consists of 2-cycles
and loops.  If $F$ is reflective through $T$ then
$\mathrm{Orb}_{\langle F\rangle }(Tx) = T(\mathrm{Orb}_{\langle
F\rangle }x)$ for every $x$.


\section*{3.2 Boolean isometries are reflective\label{s:BIR}} 
We prove here that any Boolean isometry is reflective through
some Boolean isometry of order 2.  For any isometry $T$ of the
real $n$-space, that is, $T \in  O(\mathbf{R}^{n})$, there
exists $U \in  O(\mathbf{R}^{n})$ of order 2 such that $T^{-1}  =
U^{-1}TU$.  This proposition can be proved using the Jordan
canonical form of a matrix representing $T$.  However, in a
finite subgroup $\mathbf{G} \subseteq  O(\mathbf{R}^{n})$, it is
not always true that any element and its inverse are conjugate. 
For example, both the group of the isometries of $\mathbf{Q}^{n}$
and a group of rotation on $\mathbf{R}^{2}$ are reflection groups
(see e.g. Grove \& Benson, 1985), but the latter does not have
this property if the order is greater than 2.\\
 
\textbf{Lemma 3.2.1}  Let $\rho  = (1,2,..,n)$ and $A \subseteq 
\mathbf{N}$.   Then the equation
$$
        X\dot{+}\rho X = A.
\eqno (3.2.1) 
$$
for an unknown subset $X \subseteq  \mathbf{N}$ has a solution
iff $|A|$
is even.  Further, if $X$ is a solution, then $X$ and its
complement $X^{c}$ are the only solutions.

\begin{proof}  Since $X$ and $\rho X$ have the same cardinality,
their symmetric difference must be even (proving the necessity). 
For the sufficiency, if $A  = \emptyset $, then clearly $X =
\emptyset $ and $X = \mathbf{N}$ are the only solutions of
(3.2.1). 
Assume $|A|$ is positive and even.  If $A = \{ i,j\}$
with $i < j$ then $X = \{  i,...,j-1\}$ is a solution.  If $|A|$
is even, then $A$ is the sum ($\dot{+}$) of pairs, so
that by (2.4.5) of Chapter 2 there exists a solution $X$. 
Suppose $Y$ is also a solution.  Then $X\dot{+}\rho X =
Y\dot{+}\rho Y$, so that $(X\dot{+}\rho X)\dot{+}(Y\dot{+}\rho Y)
= \emptyset $, i.e. $(X\dot{+}Y)\dot{+}\rho (X\dot{+}Y) =
\emptyset $.  Therefore, $X\dot{+}Y = \emptyset $ or $X\dot{+}Y =
\mathbf{N}$, i.e. $Y = X$ or $Y = X^{c}$. 
 \end{proof}

\textbf{Theorem 3.2.2} (Ueda,1998)  If $T$ is an isometry of
$\mathbf{Q}^{n}$, then $T$ is reflective through some isometry of
order 2 of $\mathbf{Q}^{n}$.

\begin{proof}  By Proposition 2.1.5 of Chapter 2, any isometry $T
\in  O(\mathbf{Q}^{n})$ can be decomposed as the commutative
product 
$$
        T = \tau _{1}J_{1}^{-}\odot ...\odot \tau _{k}J_{k}^{-
}\cdot \iota J_{k+1}^{-},
$$
where $\tau _{i}$ is a cyclic permutation such that
$\mathrm{Car}\tau_{i}$ and
$\mathrm{Car}\tau_{j}$ are disjoint, $J_{i} \subseteq
\mathrm{Car}\tau{i}$
for every $i = 1,..,k$, and
 $J_{k+1}
\subseteq\mathbf{N}\backslash\bigcup_{i}\mathrm{Car}\tau_{i}$.
It suffices to prove for each component of the disjoint
composition. 
If $\mathbf{N}\backslash\bigcup_{i}\mathrm{Car}\tau_{i}$ is
nonempty,
 then $\iota J_{k+1}^{-}$ is reflective through $\iota
J_{k+1}^{-}$ and 
$\iota
((\mathbf{N}\backslash\bigcup_{i}\mathrm{Car}\tau_{i})\backslash
J_{k+1})^{-}$,
and at least one of them is of order 2.  Therefore, it suffices
to prove for
$T = \tau J^{-}$, where $\mathrm{Car}\tau = \mathbf{N}$ and
$J \subseteq  \mathbf{N}$.  Therefore, it suffices
to prove for $T = \rho A^{-}$, $A \subseteq  \mathbf{N}$, since
$\tau J^{-
}$ is a conjugate of $\rho A^{-}$ for some $A$.

Assume that $\xi$ is an unknown permutation of $\mathbf{N}$ and
$X$ is an unknown subset of $\mathbf{N}$ such that $T$ is
reflective
 through $U = \xi X^{-}$.  Then
$U^{-1}TU = T^{-1}$, i.e. $TUT =U$, i.e., $\rho \xi \rho  = \xi $
and $\rho ^{-1}(\xi ^{-1}A\dot{+}X)\dot{+}A = X$, i.e.
$$
         \rho \xi \rho  = \xi  \; \mbox{and}\;  X\dot{+}\rho X =
\xi
^{-1}A\dot{+}\rho A.
\eqno (3.2.2) 
$$
The solutions of the first equation of (3.2.2) are the linear
permutations $\xi $ of slope $-1$, for any one of which, the
second equation has two solutions $X$ and $X^{c}$ by Lemma 3.2.1,
since $|A\dot{+}B|$ is even for arbitrary sets $A$ and
$B$ of same cardinality modulo 2.  Therefore, $T$ is reflective
through an isometry $U = \xi X^{-}$.  To prove that $U$ is of
order 2, it is sufficient to show that any such $U$ satisfies the
equation
$$
    \xi \xi  = \iota  \; \mbox{and}\;  \xi ^{-1}X\dot{+}X =
\emptyset \; 
\mbox{i.e.}\;  \xi X = X.
\eqno (3.2.3) 
$$
The first equation of (3.2.3) is satisfied by any linear
permutation of slope -1.  Further, $\xi X\dot{+}\rho (\xi X) =
\rho \xi \rho X\dot{+}\rho \xi X = \rho \xi (\rho X\dot{+}X) =
\rho \xi (\xi ^{-1}A\dot{+}\rho A) = \rho A\dot{+}\xi A$. 
Therefore, $\xi X$ is also a solution of the second equation of
(3.2.3), so that $\xi X = X$ or $\xi X =X^{c}$.  Suppose the
second case holds.  Then $\xi$ has no fixed point, so that there
exists some $i \in \mathbf{N}$ such
that $\xi i = \rho i = j$.  Clearly $j \notin \xi A\dot{+}\rho
A$.   If $i \in X$, then $j \in
\rho X$ and $j \in \xi X$, i.e. $j \notin  X$.  If $i  \notin X$,
then $j \notin \rho X$ and $j 
\notin \xi X$ i.e. $j \in X$. Therefore, $j \in X\dot{+}\rho X$,
which contradicts the fact
that $X$ is a solution of the second equation of (3.2.3).
\end{proof}    

\section*{3.3 Reflectiveness for 
[\;]-representations\label{s:RR}}
In this section some necessary or sufficient conditions for a
self-dual transformation $F$ to be a reflective transformation
are described, when $F$ is represented as $F = [f_{1},...,f_{n}]$
introduced in Chapter 2.3.\\ 

\textbf{Proposition 3.3.1}  Let $F = [f_{1},...,f_{n}]$ be a
self-
dual transformation of $\mathbf{Q}^{n}$ and $\tau $ be a
permutation of $\mathbf{N}$. $F$ is reflective through $\tau $ if
and
only if $\tau Ff_{i} \subseteq  \bar{\neg}f_{\tau i}$ and $\tau
F(f_{i}\cup \bar{\neg}f_{i})^{c }\cap  \bar{\neg}f_{\tau i} =
\emptyset $
for every $i \in  \mathbf{N}$. 

\begin{proof}  Assume that $F$ is reflective through $\tau $. 
Then $F\tau F = \tau $.  Let $x \in  f_{i}$.  Then $x_{i} = 1$,
$(Fx)_{i} = 0$.  Therefore,
$$
(\tau Fx)_{\tau i} = (\tau ^{-1}(\tau Fx))_{i} = (Fx)_{i} = 0
$$
and
$$
(F(\tau Fx))_{\tau i} = (\tau x)_{\tau i} = (\tau ^{-1}(\tau
x))_{i} = x_{i} = 1,
$$
so that $\tau Fx \in  \bar{\neg}f_{\tau i}$.  Next, let $x \notin 
f_{i}\cup \bar{\neg}f_{i}$.  Then $x_{i} = (Fx)_{i}$, so that
$(F(\tau
Fx))_{\tau i} = (\tau x)_{\tau i} = (\tau Fx)_{\tau i}$. 
Therefore, $\tau Fx \notin  \bar{\neg}f_{\tau i}$.

    Assume $\tau Ff_{i} \subseteq  \bar{\neg}f_{\tau i}$ and
$\tau
F(f_{i}\cup  \bar{\neg}f_{i})^{c }\cap  \bar{\neg}f_{\tau i} =
\emptyset $
for every $i \in  \mathbf{N}$.  To prove that $F$ is reflective
through
$\tau $, we will show $F\tau F = \tau $.  Let $x \in  f_{i}$ for
some $i$.  Then $\tau Fx \in  \bar{\neg}f_{\tau i}$, so that
$(F\tau
Fx)_{\tau i} = 1$.  Also, $x_{i} = 1$, so that $(\tau x)_{\tau i}
=(\tau ^{-1}\tau x)_{i} = 1$.  Therefore, $(F\tau Fx)_{\tau i} =
(\tau x)_{\tau i}$.  If $x \in  \bar{\neg}f_{j}$ for some $j$,
then by the self-duality of $F$ and $\tau $, $(F\tau Fx)_{\tau j}
= (\tau x)_{\tau j}$ also.  Let $x \notin  f_{k}\cup
\bar{\neg}f_{k}$ for some $k$.  Then $\tau Fx \notin 
\bar{\neg}f_{\tau k}\cup f_{\tau \kappa}$, because $\bar{\neg}x
\notin  f_{k}\cup \bar{\neg}f_{k}$.  Therefore,
$$
(F\tau Fx)_{\tau k} = (\tau Fx)_{\tau k} = (Fx)_{k} = x_{k} =
(\tau x)_{\tau k}.
$$
Consequently, $(F\tau F)x = \tau x$ for every $x \in 
\mathbf{Q}^{n}$, so that $F$ is reflective through $\tau $.
\end{proof}

Proposition 3.3.1 can be generalized into the following
proposition.\\

\textbf{Proposition 3.3.2}  Let $F = [f_{1},...,f_{n}]$ be a
self-
dual transformation of $\mathbf{Q}^{n}$ and $T = \tau J^{-}$ be
an isometry of $\mathbf{Q}^{n}$. $F$ is reflective through $T$ if
and only if (i) $TFf_{i} \subseteq  f_{\tau i}$ for every $i \in 
J$, (ii) $TFf_{i} \subseteq  \bar{\neg}f_{\tau i}$ for every $i
\in J^c$, and (iii) $TF(f_{i}\cup \bar{\neg}f_{i})^{c} \cap 
\bar{\neg}f_{\tau i} = \emptyset $ for every $i$.

\begin{proof}  Assume that $F$ is reflective through $T$.  Then
$FTF = T$.  Let $x \in  f_{i}$ and $i \in  J$.  Then $x_{i} = 1$
and $(Fx)_{i} = 0$.
$$
(Tfx)_{\tau i} = (\tau ^{-1}(TFx))_{i} = (J^{-}Fx)_{i} = 1,
$$
and
$$
(F(TFx))_{\tau i} = (Tx)_{\tau i} = (\tau ^{-1}(Tx))_{i} = (\tau
^{-1}\tau J^{-}x)_{i} = (J^{-}x)_{i} = 0.
$$
Therefore $TFx \in  f_{\tau i}$.  Next, let $x \in  f_{i}$
and $i \in  J^c$.  Then $x_{i} = 1$ and $(Fx)_{i} = 0$.
$(Tfx)_{\tau i} = (J^{-}Fx)_{i} = 0$. $(F(TFx))_{\tau i} = (J^{-
}x)_{i}  = 1$.  Therefore $TFx \in  \bar{\neg}f_{\tau i}$.  Next,
let
$x \notin  f_{i}\cup \bar{\neg}f_{i}$.  Then $x_{i} = (Fx)_{i}$,
so that
$$
(F(TFx))_{\tau i} = (Tx)_{\tau i} =(J^{-}x)_{i} = (J^{-}Fx)_{i} =
(Tfx)_{\tau i}.
$$
Therefore, $TFx \notin \bar{\neg}f_{\tau i}$.  

    Assume the conditions (i), (ii) and (iii).  To prove that $F$
is reflective through $T$, we will show that $FTF = T$.  Let $x
\in  f_{i}$ for some $i \in  J$.  Then  $TFx \in  f_{\tau i}$, so
that $(FTFx)_{\tau i} = 0$.  Also $x_{i} = 1$, so that
$$
(Tx)_{\tau i} = (\tau ^{-1}(Tx))_{i} = (\tau ^{-1}\tau
 J^{-}x)_{i} = (J^{-}x)_{i} = 0.
$$
 Therefore, $(FTFx)_{\tau i} = (Tx)_{\tau i}$.  If $x \in 
\bar{\neg}f_{j}$ for some $j \in  J$, then
by the self-duality of $F$ and $T$, $(FTFx)_{\tau j} = (Tx)_{\tau
j}$ also.  Let $x \in  f_{i}$ for some $i \in  J^c$.  Then $TFx
\in  \bar{\neg}f_{\tau i}$, so that $(FTFx)_{\tau i} = 1$.  Also
$x_{i} = 1$, so that $(Tx)_{\tau i} = (J^{-}x)_{i} = 1$. 
Therefore, $(FTFx)_{\tau i} = (Tx)_{\tau i}$.  If $x \in 
\bar{\neg}f_{j}$ for some $j \in  J^c$, then by the self-duality
of $F$ and $T$, $(FTFx)_{\tau j} = (Tx)_{\tau j}$ also.  Let $x
\notin f_{k}\cup \bar{\neg}f_{k}$ for some $k$.  Then $TFx \notin
\bar{\neg}f_{\tau k}\cup f_{\tau \kappa }$, because $\bar{\neg}x
\notin f_{k}\cup \bar{\neg}f_{k}$.  Therefore,
$$
(FTFx)_{\tau k} = (Tfx)_{\tau k} = (\tau J^{-}Fx)_{\tau k} =
(J^{-}Fx)_{k} = (J^{-}x)_{k} = (Tx)_{\tau k}.
$$
Consequently, $(FTF)x = Tx$ for every $x \in 
\mathbf{Q}^{n}$, so that $F$ is reflective through $T$. 
\end{proof}


\textbf{Corollary 3.3.3}  Let $F = [f_{1},...,f_{n}]$ be a
self-dual transformation of $\mathbf{Q}^{n}$ and $T = \tau J^{-}$
be an isometry of $\mathbf{Q}^{n}$.  If $F$ is reflective through
$T$,
then $|f_{\tau i}| = |f_{i}|$ for every $i$.\\

\section*{3.4 Circular and skew-circular reflective
transformations\label{s:CSCR}}
In this section, we investigate the properties of some circular
and skew-circular reflective transformations.   First, let us
consider an example of circular reflective transformation.\\

\textbf{Example 3.4.1}  Let $f = p_{1}\cdot p_{2}\cdot p_{3}\cdot
(\neg p_{4})\cdot (\neg p_{5})$ be the transformation of
$\mathbf{Q}^{5}$.  Then the graph of $F = \langle f \rangle $
consists of loops and one 10-cycle, that is 
\begin{eqnarray*}
    11100 &\rightarrow & 01100 \rightarrow  01110 \rightarrow 
00110 \rightarrow  00111 \rightarrow  00011\\
        &\rightarrow & 10011 \rightarrow  10001 \rightarrow 
11001 \rightarrow  11000 \rightarrow  11100.
\end{eqnarray*}
$F$ is reflective through any linear permutation of
$\mathbf{N}_{5}$ of slope $-1$.\\ 

The above example illustrates Proposition 3.1.2.  In fact, If $F$
is circular and reflective through a linear permutation $\tau $
of coefficients $(a,b)$, then $F$ is reflective through any
linear permutation of slope $a$, that is, $\rho ^{j}\tau $ whose
coefficients are $(a,b+j)$, since the coefficients of $\rho ^{j}$
are $(1,j)$.\\

\textbf{Notation} Let $\lambda$ and $\mu \in
\mathrm{SYM}(\mathbf{N})$ denote the
linear permutations of coefficients $(-1,1)$ and $(-1,2)$
respectively, that is, 
\begin{eqnarray*}
\lambda  &=& (1,n)(2,n-1)\cdot \cdot (i,n-i+1)
([n/2],n-[n/2]+1),\\
\mu &=&  (2,n)\cdot(3,n-1)\cdot\cdot (i,n-i+2)\cdot\cdot ([(n-
1)/2]+1,n+1-[(n-1)/2]).
\end{eqnarray*}

\textbf{Proposition 3.4.2}  Let $F = \langle f \rangle $ be a
self-dual circular transformation of $\mathbf{Q}^{n}$.  $F$ is
reflective through any linear permutation of slope -1,
if and only if $\mu Ff \subseteq  \bar{\neg}f$ and $\mu
F(f\cup \bar{\neg}f)^{c} \cap  \bar{\neg}f = \emptyset $. 

\begin{proof} $F = [f,\rho f,..,\rho ^{i-1}f,..,\rho ^{n-1}f]$ by
definition.  Assume $\mu Ff \subseteq  \bar{\neg}f$ and $\mu
F(f\cup bar{\neg}f)^{c} \cap  \bar{\neg}f = \emptyset $.
Let $x \in \rho ^{i-1}f$.  Then $\rho ^{-(i-1)}x \in  f$. 
Therefore, $\mu F\rho ^{-(i-1)}x \in  \bar{\neg}f$.  Therefore,
$$
 \rho ^{i-1}\mu Fx = \mu \rho ^{-(i-1)}Fx = \mu F\rho ^{-(i-1)}x 
\in  \bar{\neg}f,
$$
 so that
$$
\mu Fx \in \rho ^{-(i-1)}\bar{\neg}f
= \rho ^{n-i+1}\bar{\neg}f = \bar{\neg}\rho ^{\mu i-1}f.
$$
Similarly, if $x \notin \rho ^{i-1}f\cup \bar{\neg} \rho ^{i-1}f$
then $\mu Fx \notin  \bar{\neg}\rho ^{\mu i-1}f$. 
Consequently, by Proposition 3.3.1, $F$ is reflective through
$\mu $, so that F is reflective through every linear permutation
of slope -1.  For the converse, apply Proposition 3.3.1 to $\mu$
and $f_1 = f$.
\end{proof}

\textbf{Proposition 3.4.3}  (i) A circular transformation
expressed by $F = (F_{1},..,\rho ^{i-1}F_{1},..,\rho
^{n-1}F_{1})$ is reflective through $\mu $, if and only if
$$
F^{-1} = (\mu F_{1},\rho \mu F_{1},..,\rho ^{n-1}\mu F_{1}).
\eqno (3.4.1) 
$$
(ii) A self-dual circular transformation $\langle f \rangle $ is
reflective through $\mu $, if and only if
$$
        \langle f \rangle ^{-1} = <\mu f>.
\eqno (3.4.2) 
$$

\begin{proof}  (i)
\begin{eqnarray*}
    \mu ^{-1}F\mu  &=& \mu ^{-1}F\mu ^{-1} \\
        &=& \mu ^{-1}(F_{1}\mu ^{-1},..,(\rho ^{i-1}F_{1})\mu ^{-
1},..,(\rho ^{n-1}F_{1})\mu ^{-1})\\
        &=& \mu ^{-1}(\mu F_{1},..,\mu \rho ^{i-1}F_{1},..,\mu
\rho ^{n-1}F_{1})\\
        &=& \mu ^{-1}(\mu F_{1},..,\rho ^{-(i-1)}\mu
F_{1},..,\rho ^{-(n-1)}\mu F_{1})\\
        &=& (\mu F_{1},..,\rho ^{-(\mu i-1)}\mu F_{1},..,\rho ^{-
(\mu n-1)}\mu F_{1})\\
        &=& (\mu F_{1},..,\rho ^{i-1}\mu F_{1},..,\rho ^{n-1}\mu
F_{1}).
\end{eqnarray*}
Therefore, $F$ is reflective through $\mu $, if and only if
(3.4.1) holds.\\
(ii) Note that $\mu ^{-1}F\mu $ is self-dual if $F$ is self-dual. 
Further if $F = \langle f \rangle $, then
$$
p_{1}\cdot \neg (\mu F_{1}) = p_{1}\cdot \bar{\neg}(\mu F_{1}) =
p_{1}\cdot (\mu \bar{\neg}F_{1}) = \mu (p_{1}\cdot
(\bar{\neg}F_{1})) = \mu (p_{1}\cdot \neg F_{1}) = \mu f.
$$
Therefore $\langle f \rangle $ is reflective through $\mu $ if
and only if (3.4.2) holds. 
\end{proof}

\textbf{Example 3.4.4}  $F = \langle\langle f\rangle\rangle $, $f
= p_{1}\cdot \cdot \cdot p_{i}\cdot \cdot \cdot p_{n}$. 
$\mathrm{GRAPH}(F)$ consists of one $2n$-cycle and loops.  As
seen from the graph given in Example 2.5.5, $F$ is reflective
through $\lambda $.\\

If $F$ is skew-circular and reflective through $\lambda $, then
$F$ is reflective through $(\rho n^{-})^{j}\lambda $ for every j,
particularly through $\rho n^{-}\lambda  = \mu 1^{-}$, since $F$
is commutative with  $\rho n^{-}$.

     We used the equation (1.2.4) $\rho \mu  = \mu \rho ^{-1}$ in
the proof of Proposition $3.4.2$.  Similarly we need
$$
          (\rho n^{-})\lambda  = \lambda (\rho n^{-})^{-1}
\eqno (3.4.3)  
$$
in the proof of the next Proposition.  In fact,
\begin{eqnarray*}
     (\rho n^{-})\lambda (x_{1},...,x_{n})
     &=& \rho n^{-}(x_{n},..,x_{1})\\
     &=& \rho (x_{n},..,x_{2},\neg x_{1})\\
     &=& (\neg x_{1},x_{n},..,x_{2})\\
     &=& \lambda (x_{2},..x_{n},\neg x_{1})\\
     &=& \lambda n^{-}(x_{2},...x_{n},x_{1})\\
     &=& \lambda n^{-}\rho ^{-1}(x_{1},...,x_{n})\\
     &=& \lambda (\rho n^{-})^{-1}(x_{1},...,x_{n}).
\end{eqnarray*}

\textbf{Proposition 3.4.5}  Let $F = \langle\langle
f\rangle\rangle $ be a self-dual skew-circular transformation of
$\mathbf{Q}^{n}$.  $F$ is reflective through
 $(\rho n^{-})^{j}\lambda $ for every $j$, if and only if
$\lambda Ff \subseteq  \bar{\neg}(\rho n^{-})^{n-1}f$ and
$\lambda F(f\cup \bar{\neg}f)^{c} \cap  \bar{\neg}(\rho n^{-
})^{n-1}f = \emptyset $. 

\begin{proof}  $F = [f,\rho n^{-}f,..,(\rho n^{-})^{i-
1}f,..,(\rho n^{-})^{n-1}f]$ by Proposition 2.5.4.  Assume
$\lambda Ff \subseteq  \bar{\neg}(\rho n^{-})^{n-1}f$ and
$\lambda F(f\cup \bar{\neg}f)^{c} \cap  \bar{\neg}(\rho n^{-
})^{n-1}f = \emptyset $.  Let $x \in  (\rho n^{-})^{i-1}f$.  Then
$(\rho n^{-})^{-(i-1)}x \in  f$.  Therefore, $\lambda F(\rho n^{-
})^{-(i-1)}x \in  \bar{\neg}(\rho n^{-})^{n-1}f$.  Therefore,
$$
(\rho n^{-})^{i-1}\lambda Fx = \lambda (\rho n^{-})^{-(i-1)}Fx =
\lambda F(\rho n^{-})^{-(i-1)}x \in  \bar{\neg}(\rho n^{-})^{n-
1}f,
$$
so that 
$$
\lambda Fx \in  (\rho n^{-})^{-(i-1)}\bar{\neg}(\rho n^{-})^{n-
1}f = \bar{\neg}(\rho n^{-})^{n-i}f = \bar{\neg}
(\rho n^{-})^{\lambda i-1}f.
$$
  Similarly, if $x \notin  \rho ^{i-1}f\cup \bar{\neg}\rho ^{i-
1}f$ then $\lambda Fx \notin  \bar{\neg}\rho ^{\lambda i-1}f$. 
Consequently, by Proposition 3.3.1, $F$ is reflective through
$\lambda $, so that $F$ is reflective through $(\rho n^{-
})^{j}\lambda $ for every $j$.
For the converse, apply Proposition 3.3.1 to $\lambda $ and
$f_{1} = f$.
\end{proof}

\textbf{Proposition 3.4.6}  (i) A skew-circular transformation
expressed by
$$
F = (F_{1},..,(\rho n^{-})^{i-1}F_{1},..,(\rho n^{-
})^{n-1}F_{1})
$$
is reflective through $T = \mu 1^{-}$, if and only if
$$
    F^{-1} = (\bar{\neg}TF_{1},\rho
n^{-}\bar{\neg}TF_{1},..,(\rho n^{-
})^{n-1}\bar{\neg}TF_{1}).
\eqno (3.4.3) 
$$
(ii) A skew-circular transformation $\langle\langle
f\rangle\rangle $ is reflective through $T = \mu 1^{-}$, if and
only if
$$
        \langle\langle f\rangle\rangle ^{-1} = \langle\langle
\bar{\neg}Tf\rangle\rangle .
\eqno (3.4.4)
$$

\begin{proof}  (i) $T^{-1}FT = T^{-1}FT^{-1}$ 
\begin{eqnarray*}
   &=& T^{-1}(F_{1}T^{-1},..,((\rho n^{-})^{i-1}F_{1})T^{-
1},..,((\rho n^{-})^{n-1}F_{1})T^{-1})\\
   &=& T^{-1}(TF_{1},..,T((\rho n^{-})^{i-1}F_{1}),..,T((\rho
n^{-})^{n-1}F_{1}))\\
   &=& T^{-1}(TF_{1},..,(\rho ^{-1}1^{-})^{i-1}TF_{1},..,(\rho
^{-1}1^{-})^{n-1}TF_{1})\\
&=& T^{-1}(TF_{1},..,\rho ^{-(i-1)}\{1,..,i-1\}^{-}TF_{1},..,\rho
^{-(n-1)}\{1,..,n-1\}^{-}TF_{1})\\
&=& (\neg TF_{1},..,\rho ^{-(\mu i-1)}\{1,..,\mu i-1\}^{-
}TF_{1},..,\rho ^{-1}1^{-}TF_{1})\\
&=& (\neg TF_{1},..,\rho ^{i-1}\{1,..,n-i+1\}^{-}TF_{1},..,\rho
^{-1}1^{-}TF_{1})\\
&=& (\bar{\neg}TF_{1},..,\rho ^{i-1}\{n-i+2,..,n\}^{-}\bar{\neg}
TF_{1},..,\rho ^{-1}\{2,..,n\}^{-}\bar{\neg}TF_{1})\\
&=& (\bar{\neg}TF_{1},..,(\rho
n^{-})^{i-1}\bar{\neg}TF_{1},..,(\rho n^{-
})^{n-1}\bar{\neg}TF_{1}).
\end{eqnarray*}
Therefore, $F$ is reflective through $T$, if and only if (3.4.3)
holds.
(ii)  If $F = \langle\langle f\rangle\rangle $, then
$$
p_{1}\cdot \neg (\bar{\neg}TF_{1}) = (\bar{\neg}Tp_{1})\cdot
(\bar{\neg}T(\neg
F_{1})) = \bar{\neg}T (p_{1}\cdot \neg F_{1}) = \bar{\neg}Tf.
$$
Therefore $\langle\langle f\rangle\rangle $ is reflective through
$T$ if and only if (3.4.4) holds.
\end{proof}


\textbf{Theorem 3.4.7}  Let $F$ be circular and self-dual.  If
$F$ is reflective through a linear permutation $\tau $ of slope
$-1$, then $F$ is isometrically equivalent to a transformation
which is minimal, circular, self-dual, and reflective through
$\tau $.  If $F$ is not reflective through a linear permutation
$\tau $ of slope $-1$, then $F$ is isometrically equivalent to a
transformation which is minimal, circular, self-dual, and not
reflective through $\tau $.

\begin{proof}  If $F$ is circular, and self-dual, then $F$ is
isometrically equivalent to a minimal circular self-dual
transformation $G$ by Theorem 2.5.2 of Chapter 2.  More
specifically, in the proof of that theorem, it was shown that
there exists a Boolean isometry $T$ such that $G = TF$, and $T$
is a product of transformations selected from $\rho $ and
$\bar{\neg}$, so that $T$ and $F$ are commutative.  Therefore, if
$F$ is reflective through a linear permutation $\tau $ of slope
$-1$, then $G$ is also reflective through $\tau $; and if $F$ is
not reflective through a linear permutation $\tau $ of slope
$-1$, then $G$ is not reflective through $\tau $.
\end{proof} 
 
\section*{3.5 Reflectiveness of orbit modifications\label{s:ROM}}
 Let $F$ be a transformation of $\mathbf{Q}^{n}$, $M = \{ 
n+1,n+2,.., n+m\}$, and
$C \subseteq \mathbf{Q}^{M}$.  Then the direct product $F\times I
|C$ can be
extended to the transformation $(F\times I|C)^{\sim }$ of
$\mathbf{Q}^{\mathbf{N}_{n+m}}$ by defining
$$
(F\times I|C)^{\sim }x = \left\{
       \begin{array}{ll}
         (F\times I|C)x & \mbox{if}\;  P_{M}x \in  C, \\
           x & \mbox{if}\;  P_{M}x \notin  C.
       \end{array}         
          \right.
$$
$(F\times I|C )^{\sim }$ is the disjoint composition of
$|C|$ transformations
$(F\times I|\{ c\} )^{\sim }$ for $c \in C$.  As in Chapter 2.3,
a subset $C$ of $\mathbf{Q}^{M}$ is called \emph{complete} if
$\bar{\neg}C = C$.  If $C \subseteq \mathbf{Q}^{M}$ is complete,
the restriction $\bar{neg}\mid C$ to $C$ is a transformation of
$C$.  If $F$ is self-dual and represented as
$F = [f_{1},...,f_{n}]$, and $C$ is complete, then
$(F\times I \mid C)^{\sim }$ is self-dual and can be expressed as
$$
     (F\times I \mid C)^{\sim } = [f_{1}\cdot 1_{C},..,f_{n}\cdot
1_{C},\emptyset ,..,\emptyset ],
$$
where $1_{C}x = 1$ if and only if $x \in  C$.  If $C =
\mathbf{Q}^{M}$, we call $F\times I$ the
$(n+1,...,n+m)$th \emph{face copies} of $F$.

    The following propositions are easily proved using the basic
properties of reflective transformations described in Section
3.1.  In particular, the method of constructing a new Boolean
transformation $G$ from $F$ as shown in Propositions 3.5.3 and
3.5.4
is called \emph{orbit modification}.

\textbf{Proposition 3.5.1}  Let $F$ be a reflective
transformation
of $\mathbf{Q}^{n}$ through $T$, and let $C \subseteq 
\mathbf{Q}^{M}$, where $M = \{ n+1, n+2,..,n+m\}$.  Then, (i)
$(F\times I|C)^{\sim }$ is reflective through $T\times
I$; (ii) $(F\times I|C)^{\sim }$ is reflective
through $T\times \bar{\neg}$, if $C$ is complete.\\

\textbf{Proposition 3.5.2}  Let $F$ be any transformation of
$\mathbf{Q}^{n}$, and let $C \subseteq  \mathbf{Q}^{M}$, such
that $C\cap \bar{\neg}C = \emptyset $, where $M = \{  n+1,n+2,..,
n+m\}$.  Then, $(F\times I|C)^{\sim }\odot (F^{-1}
\times I|\bar{\neg}C)^{\sim }$ is reflective through $M^{-}$.\\
  
\textbf{Proposition 3.5.3}  Let $F$ be a reflective
transformation
of $\mathbf{Q}^{n}$ through $T$ of order 2.  Assume that $F$ has
two cycles $C$ and $D$ such that $T\mathbf{C} = \mathbf{D}$.
 Let $c \in  \mathbf{C}$ and $d \in \mathbf{D}$. 
 Define the transformation $G$ by 
\begin{eqnarray*}
    c &\rightarrow & Tc \rightarrow  FTc \rightarrow  F^{2}Tc
\rightarrow  ...\\
     & &\rightarrow  d \rightarrow  Td \rightarrow  FTd
\rightarrow  F^{2}Td \rightarrow  ... \rightarrow  c,\\ 
Gx &=& x \; \mbox{for any other points}\;  x \in \mathbf{C}\cup
\mathbf{D},\\
Gx &=& Fx \; \mbox{for any points}\;  x \in  (\mathbf{C}\cup
\mathbf{D})^c.
\end{eqnarray*}
Then $G$ is reflective through $T$.\\

\textbf{Proposition 3.5.4}  Let a transformation $F$ of
$\mathbf{Q}^{n}$ be reflective through $T$ of order 2.  Assume
that $F$ has
two cycles $C$ and $D$ such that $T\mathbf{C} = \mathbf{C}$ and
$T\mathbf{D} =
\mathbf{D}$.  Let $c \in \mathbf{C}$ and $d \in \mathbf{D}$. 
Define the transformation
$G$ by 
\begin{eqnarray*}
    c &\rightarrow & d \rightarrow  Fd \rightarrow  F^{2}d
\rightarrow  ...\\
     & &    \rightarrow  Td \rightarrow  Tc \rightarrow  FTc
\rightarrow  F^{2}Tc \rightarrow  ... \rightarrow  c,\\
    Gx &=& x \quad \mbox{for any other points}\;
  x \in \mathbf{C}\cup \mathbf{D},\\
    Gx &=& Fx \quad \mbox{for any points}\;
  x \in  (\mathbf{C}\cup \mathbf{D})^c.
\end{eqnarray*}
Then $G$ is reflective through $T$.\\

\textbf{Example 3.5.5}  The transformation $F^(1): 1 \rightarrow 
0
\rightarrow  1$ for $\mathbf{Q}^{1}$ is reflective through
$I_{\mathbf{Q}^{1}}$.  Therefoe, the 2nd face copies
$F^{(1)\prime }$
of $F^{(1)}$:
$$
         11 \rightarrow  01 \rightarrow  11, 10 \rightarrow  00
\rightarrow  10
$$
are reflective through $2^{-}$ by Proposition 3.5.1 (ii).  Let $c
=
11$, and define $F^{(2)}$ by orbit modification as
\begin{eqnarray*}
    c &=& 11 \rightarrow  2^{-}c = 10 \rightarrow  F^{(1)\prime
}2^{-}c = 00 = \{  1,2\}^{-}c\\
     & & \rightarrow  2^{-}(\{1,2\}^{-}c) = 01 \rightarrow 
F^{(1)\prime }2^{-}(\{1,2\}^{-}c) =11.
\end{eqnarray*}
Then $F^{(2)}$ is reflective through $2^{-}$ by proposition
3.5.3. 
Then the 3rd face copies of $F^{(2)}$:
$$
111 \rightarrow  101 \rightarrow  001 \rightarrow  011
\rightarrow  111, 110 \rightarrow  100 \rightarrow  000
\rightarrow  010 \rightarrow  110
$$
are reflective through $\{ 2,3\}^{-}$ by Proposition 3.5.1 (ii). 
Define $F^{(3)}$ by orbit modification as
\begin{eqnarray*}
111 &\rightarrow & \{  2,3\}^{-}(111) = 100 \rightarrow  000
\rightarrow  \{  2,3\}^{-}(000) = 011 \rightarrow  111,\\
    101 &\rightarrow & 101, 001 \rightarrow  001, 110 \rightarrow 
110, 010 \rightarrow  010.
\end{eqnarray*}
In this way, for $\mathbf{Q}^{n}$, we obtain a reflective
transformation $F^{(n)}$ through $\{ 2,3,...,n\}^{-}$. 
$\mathrm{GRAPH}(F^{(n)})$ consists of loops and one 4-cycle, that
is,
$$
    11\cdot \cdot \cdot 1 \rightarrow  100\cdot \cdot \cdot 0
\rightarrow  00\cdot \cdot \cdot 0 \rightarrow  011\cdot \cdot
\cdot 1 \rightarrow  11\cdot \cdot \cdot 1.
$$

\textbf{Example 3.5.6} (Binary-reflected Gray code. Gray, 1953)
(i)
$$
        G^{(1)}:  0 \rightarrow  1 \rightarrow  0. 
$$
(ii)  Construct $G^{(n)}$ from the face copies 
\begin{eqnarray*}
   G^{(n-1)}\times I_{\{0\}}&:& 00\cdot \cdot \cdot 00
\rightarrow  ... \rightarrow   00\cdot \cdot \cdot 010
\rightarrow  00\cdot \cdot \cdot 00\\
  (G^{(n-1)})^{-1}\times I_{\{1\}}&:& 00\cdot \cdot \cdot 01
\leftarrow  ... \leftarrow  00\cdot \cdot \cdot 011 \leftarrow 
00\cdot \cdot \cdot 01
\end{eqnarray*}
by orbit modification as
$$
     G^{(n)}:
   \left.\begin{array}{ccccc}
 00\cdot \cdot \cdot 00 & \rightarrow & ...& \rightarrow &
00\cdot \cdot \cdot 010 \\
 \uparrow & & & & \downarrow \\
 00\cdot \cdot \cdot 01 & \leftarrow & ... & \leftarrow & 00\cdot
\cdot \cdot 011 \\
         \end{array}
    \right.
$$
From Proposition 3.5.2, $(G^{(n-1)}\times I_{\{0\}})^{\sim }\odot
((G^{(n-1)})^{-1}\times I_{\{1\}})^{\sim }$ is reflective through
$n^{-}$ for every $n$.  Therefore, $G^{(n)}$ is reflective
through $n^{-}$ for every $n$ by Proposition 3.5.3.

    Therefore, $G^{(n-1)}$ is reflective through $(n-1)^{-}$ for
every $n$, and hence
$(G^{(n-1)})^{-1}$ is also reflective through $(n-1)^{-}$. 
Therefore, both $(G^{(n-1)}\times I_{\{0\}})^{\sim }$ and
$((G^{(n-1)})^{-1}\times I_{\{1\}})^{\sim }$ are reflective
through $(n-1)^{-}$.  Therefore, $(G^{(n-1)}\times
I_{\{0\}})^{\sim }\odot ((G^{(n-1)})^{-1}\times I_{\{1\}})$ is
reflective through $(n-1)^{-}$.  Therefore, $G^{(n)}$ is
reflective through $(n-1)^{-}$ for every $n$ by Proposition
3.5.4. 
Consequently, $G^{(n)}$ is commutative with $\{ n-1,n\}^{-}$ by
Proposition 3.1.2 (ii). $\mathrm{GRAPH}(G^{(n)})$ consists of one
$2^{n}$-cycle, i.e. a Hamiltonian cycle.\\

\end{document}