Несколько задач о перестановках

[Sdy]

Некоторые задачи из семинарских листков мехмата по алгебре (тема -- перестановки) идут крайне плохо, хотел бы их обсудить.

$\# 7.$
Пусть $\sigma \in S_n$, $\tau \in S_m$. Выразите через $\operatorname{sgn}\sigma$ и $\operatorname{sgn}\tau$ знаки перестановок :

a) $\xi = \left(\begin{array}{lllllll}1 & 2 & \ldots & m & m+1 & \ldots & m+n \\ \sigma(1) & \sigma(2) & \ldots & \sigma(m) & m+\tau(1) & \ldots & m+\tau(n) \end{array}\right)$

Вообще в изначальной постановке вместо $\sigma(i)$ написано $\sigma_i$, но мне кажется, что подразумевалось именно действие перестановки на элементе.

Покажем, что чётность перестановок $\tau = \left(\begin{array}{lll}1 & \ldots & n \\ \tau(1) & \ldots & \tau(n) \end{array}\right)$ и $\pi = \left(\begin{array}{llllllll}1 & 2 & 3 & \ldots & m & m+1 & \ldots & m+n \\ 1 & 2 & 3 & \ldots & m & m+\tau(1) & \ldots & m+\tau(n) \end{array}\right)$ совпадает. Если определять чётность через число инверсий, то если пара индексов $s, t$ образует инверсию в первой перестановке, то она образует её и во второй перестановке и наоборот : $s < t ~ : ~ \tau(s) > \tau(t) \iff m+\tau(t) > m+\tau(s)$, а та часть перестановки $\pi$, которая оставляет элементы на месте инверсий не добавляет. Значит чётность $\tau$ совпадает с чётностью $\pi$, тогда $\operatorname{sgn}\tau = \operatorname{sgn}\pi$.

Аналогично и чётность перестановок $\sigma = \left(\begin{array}{lll}1 & \ldots & m \\ \sigma(1) & \ldots & \sigma(m) \end{array}\right)$ и $\delta = \left(\begin{array}{llllll}1 & \ldots & m & m+1 & \ldots & m+n \\ \sigma(1) & \ldots & \sigma(m) & m+1 & \ldots & m+n \end{array}\right)$ совпадает, значит совпадают и их знаки.
Тогда

$$\xi = \delta \cdot \pi$$

Проверяем это равенство как равенство двух функций.

Действительно, если $1 \leq k \leq m$, то $(\delta \cdot \pi)(k) = \delta(\pi(k)) = \delta(k) =\sigma(k)$, но и $\xi(k) = \sigma(k)$.

При $1 \leq k \leq n$, $\xi(m+k) = m +\tau(k)$, но и $(\delta \cdot \pi)(m+k)=\delta(\pi(m+k))=\delta(m+\tau(k))=m+\tau(k)$.

Отсюда

$$\operatorname{sgn}\xi = \operatorname{sgn}\delta \cdot \operatorname{sgn}\pi=\operatorname{sgn}\sigma \cdot \operatorname{sgn}\tau$$

Верны ли мои рассуждения? Искал в задачниках с ответами что-то похожее, чтобы себя проверять, но ничего не нашёл.

[mihaild]

Вроде бы всё правильно. У Вас есть беспокойство по какому-то конкретному пункту?

[Sdy]

mihaild,
изначально у меня в доказательстве фигурировали подстановки $\sigma = \left(\begin{array}{lll}1 & \ldots & m \\ \sigma(1) & \ldots & \sigma(m) \end{array}\right)$ и $\pi = \left(\begin{array}{lll} m+1 & \ldots & m+n \\ m+\tau(1) & \ldots & m+\tau(n) \end{array}\right)$ и я доказывал, что $\xi = \sigma \cdot \pi$. Но меня смущало, что $\xi \in S_{n+m}$, $\sigma \in S_m$, а $\pi$ это вообще перестановка множества $\{m+1, \ldots, m+n\}$ и какое-то неправильное функциональное равенство получается, слева функция с одной областью отправления, а справа вообще композиция двух функций, обе из которых заданы на разных множествах.

Но пока я набирал сообщение и искал опечатки, мне в голову пришло то решение, что я выше изложил и вроде как оно лишено этой проблемы.

Спасибо за проверку.

[Sdy]

Вопрос про часть б).
Пусть $\sigma \in S_m$, $\tau \in S_n$. Выразите через $\operatorname{sgn}\sigma$ и $\operatorname{sgn}\tau$ знак перестановки :
б) $\chi = \left(\begin{array}{lllllll}1 & 2 & \ldots & m & m+1 & \ldots & m+n \\ n+\sigma(1) & n+\sigma(2) & \ldots & n+\sigma(m) & \tau(1) & \ldots & \tau(n) \end{array}\right)$

Если обозначить количество инверсий в перестановке $\sigma$ как $\operatorname{Inv}(\sigma)$, то у меня получается, что $\operatorname{Inv}(\chi) = \operatorname{Inv}(\sigma) + \operatorname{Inv}(\tau) + mn$.
Собственно говоря, пока что не получается понять, как отсюда убрать зависимость от $m$ и $n$, потом что насколько я знаю, чётность перестановки от её длины не зависит. Ошибся ли я в вычислениях или можно как-то с этим ответом ещё поработать?

[KhAl]

Sdy, ответ верный.

Sdy писал(а):

чётность перестановки от её длины не зависит

попробуйте придать строгий смысл этой фразе, и поймёте, что не так.

[Sdy]

KhAl в сообщении #1618213 писал(а):

попробуйте придать строгий смысл этой фразе, и поймёте, что не так.

Определим чётность перестановки как чётность числа инверсий в ней. Понятно, что число инверсий связано с длиной перестановки, т.к. если перестановка $\sigma \in S_n$, то $ 0 \leq \operatorname{Inv}(\sigma) \leq \frac{(n-1)n}{2}$. Наверное, слово "длина перестановки" вообще не очень удачное, длиной цикла обычно называют количество элементов в его орбите, а не то что я имел в виду.
Я имел ввиду, что если у нас есть перестановка из $S_n$, то там есть как чётные перестановки (тождественная, например), так и нечётные (всякая транспозиция). Ну и тогда по $m$ я не могу что-то сказать о $\operatorname{sgn}\sigma$, а по $n$ что-то сказать о $\operatorname{sgn}\tau$.

И вот здесь у меня опечатка :

Sdy в сообщении #1618212 писал(а):

Пусть $\sigma \in S_n$, $\tau \in S_m$.

Должно быть $\sigma \in S_m$, $\tau \in S_n$.

[KhAl]

Sdy, а, ну, парадокса здесь нет — потому что сама перестановка $\xi$ явно зависит от $m$ и $n$.

[Sdy]

KhAl,
то есть здесь у меня не получится выписать выражение, которое будет зависеть только от $\operatorname{sgn}\sigma$ и $\operatorname{sgn}\tau ?$ В первой задаче просто красиво получилось, я думал тут тоже предполагается как-то хитро привести к соответствующему виду. Но у меня всё сводится к перебору вариантов чётности $m$ и $n$ и самих перестановок, не сильно большое упрощение ответа.

[KhAl]

Sdy, $\operatorname{sgn} (\sigma) \operatorname{sgn} (\tau) (-1)^{mn}$. Лучше не выйдет, подробнее незачем.

[Sdy]

KhAl,
понял, спасибо за помощь.