Инволюция (математика)

Инволю́ция (от лат. involutio — свёртывание, завиток) — нетождественное преобразование, которое является обратным самому себе, то есть своей собственной инверсией. Это унарная операция.

Формально, функция $f$ называется инволюцией, если $f(f(x))=x$ для всякого $x$ из области определения функции $f$. Иногда пишут: $f\circ f={f}^{2}=id$, где $id$ обозначает тождественное преобразование. Вместо $id(x)$ используют запись: $e(x)=x$.

Таким образом, двойное применение функции $f$ даёт исходное значение.

Любая инволюция — это биекция.

Если преобразование $f$ инволютивное, то для любого выражения $A$ и его образа $B=f(A)$ имеем $f(B)=A$. В самом деле, $f(B)=f(f(A))=id(A)={id}_{A}=A$.

Критерий инволюции. Функция $f$ является инволюцией тогда и только тогда, когда для всякого выражения $A$ существует такое выражение $B$, что $f(A)=B\neq A$ и $f(B)=A$. Другими словами, преобразование является инволюцией в том и только в том случае, когда оно меняет местами какие-либо два выражения.

Если $f$ — инволюция, то имеют место следующие соотношения:

• $\forall a\in D_{f}:f^{-1}(a)=f(a)$ [основное свойство]
• $D_{f}=E_{f^{-1}}$ и $D_{f^{-1}}=E_{f}$
• $\forall a:f(f(a))=a$
• $\forall a,\exists b:f(a)=b\land f(b)=a$ [критерий]

Примеры инволюций:

• $f(x)=-x$, заданная на множестве целых $\mathbb {Z}$, рациональных $\mathbb {Q}$ или вещественных чисел $\mathbb {R}$;
• простейшие инволюции на множестве вещественных чисел $\mathbb {R}$:

  ${\dfrac {a}{x}}$, $a-x$, ${\dfrac {x}{x-1}}$, ${\dfrac {x-1}{x}}$, ${\dfrac {x+1}{x-1}}$, ${\dfrac {x-1}{x+1}}$;

• $f(x)={\bar {x}}$ — дополнение множества, заданная для подмножеств некоторого универсального множества $U$;
• $f(x)=\neg x$ — логическое отрицание булевой алгебры;
• симметрии: центральная, осевая, зеркальная;
• инверсия;
• комплексное сопряжение;
• преобразование Лежандра.

Функция вида $f={h^{-1}}\circ {g}\circ {h}$ будет инволюцией в том и только в том случае, если функция $g$ — инволюция; например, в положительных числах:

$ln\left({\dfrac {e^{x}+1}{e^{x}-1}}\right)$.

Композиция ${f}\circ {g}$ двух инволюций $f$ и $g$ является инволюцией тогда и только тогда, когда они коммутируют: ${f}\circ {g}=g\circ f$.

Доказательство
Пусть дана композиция ${f}\circ {g}$, в которой $f$, $g$ — инволюции. Это означает, что $f=f^{-1}$ и $g=g^{-1}$, а также ${f}\circ {g}={\left({f}\circ {g}\right)}^{-1}$. Имеем: ${f}\circ {g}={\left({f}\circ {g}\right)}^{-1}={g^{-1}}\circ {f^{-1}}={g}\circ {f}$. Если ${f}\circ {g}$ — инволюция, то двигаемся слева направо. Обратно, если выполняется равенство, то — справа налево.

'Следствие'. Если ${f}\circ {g}$ — инволюция двух инволютивных функций $f$ и $g$, то

Аналогично, если $f={g}\circ {h}\circ {k}={k}\circ {h}\circ {g}$ и $g$, $h$, $k$ — инволюции, то и $f$ — инволюция; например:

$k(x)=-x$, $h(x)={\dfrac {x+1}{x-1}}$, $g(x)={\dfrac {1}{x}}$.

Перестановка $\tau$ является инволюцией, если $\tau \circ \tau =id$, каждая инволюция является произведением непересекающихся транспозиций, например:

${\begin{pmatrix}1&2&3&4&5&6&7&8\\5&7&4&3&1&8&2&6\end{pmatrix}}=(1,5)(2,7)(3,4)(6,8)$.

Число инволюций в группе перестановок порядка $n$ определяется по формулам:

• $a(0)=1,\ a(1)=1,\ a(n)=a(n-1)+(n-1)a(n-2),\ n>1$ (рекуррентная формула),
• $a(n)=\sum _{k=0}^{[n/2]}{\frac {n!}{2^{k}\cdot (n-2k)!\cdot k!}}$,

(первые значения $a(n)$: 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35 696, 140 152).

Свойства инволюции обеспечивают ей широкое применение в различных приложения, например, инволютивные преобразования над пространством булевых векторов используются в различных схемах построения симметричных криптоалгоритмов, таких как сети Фейстеля и подстановочно-перестановочные сети.