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

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

Свойства

Если $P(a)$ — инволюция, то

1. $\forall a,P^{-1}(a)=P(a)$
2. $\forall a,P(P(a))=a$
3. $\forall x,\exists y:P(x)=y,P(y)=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$ определяется по формулам
    1. рекуррентная формула: $a(0)=1,\ a(1)=1,\ a(n)=a(n-1)+(n-1)a(n-2),\ n>1.$
    2. $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, 35696, 140152, … (последовательность A000085 в OEIS).

Применения

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