Тыртышников 6.1 задача 4

[Paul Ivanov]

Дано множество $A=\left\lbrace P_1,...,P_n\right\rbrace$ матриц порядка $n$, каждая из которых получена путём перестановки столбцов единичной матрицы. Известно, что $P_1+P_2+...+P_n=E$, где $E$ - это матрица порядка $n$, каждый элемент которой равен $1$ (первое свойство). А также известно, что $P_iP_j=P_jP_i$ для любых $i,j$ (второе свойство). Нужно доказать, что $A$ - это группа относительно операции умножения матриц, то бишь, что
1. единичная матрица входит в $A$
2. $\forall i (P_i \in A \Rightarrow P_i^{-1} \in A)$
3. $\forall i,j (P_iP_j \in A)$
Из всего, что я перепробовал на мой взгляд как-то пригодиться может только переформулировка условия на основе подстановок. Пусть $P_{i(pq)}=1 \Rightarrow q=\sigma_i(p)$, таким образом имеем для каждой матрицы подстановку, отображающую номер строки матрицы в номер единицы в этой строке. Тогда первое свойство равносильно $\forall i,j \ne i,k (\sigma_i(k) \ne \sigma_j(k))$ и второе свойство равносильно $\forall i,j (\sigma_i(\sigma_j)=\sigma_j(\sigma_j))$. И если первое свойство можно легко понять, то расшифровать второе свойство сложнее. Либо тут надо действовать как-то иначе и доказывать, что это группа, по пунктам. Нужны идеи.

[DeBill]

Paul Ivanov
1. С перестановками - вроде, должно сработать. Для этого , правда, придется дать точное описание того, что две перестановки коммутируют (Вы рассмотрели хорошую редукцию - к перестановкам; только надо, конечно, добавить, что Ваша редукция уважает операции: произведение переходит в произведение). Для этого разложите перестановки в произведения циклов - коммутативность перестановок даст некое условие на их циклы...
2. Но можно попробовать иначе...
а) Пусть $P$ - та, у которой слева вверху - единичка. Рассмотрим все ее единички на диагонали: пусть это первые $k<n$ штук. Тогда подпространство, натянутое на них (а также подпространство, натянутое на остальные базисные) - инвариантно относительно $P$ (это следует из свойства 1)). Но известно описание коммутирующих матриц: их инвариантные подпространства совпадают (посмотрите точную формулировку). Однако, это противоречит свойству 1): есть $P_i$, переводящий "остальной" вектор в "неостальной". Значит, $k=n$, так что $P$ - единичная.
б) Домножение списка $P_1,...,P_n$ на $P_i$ сохраняет оба свойства. С учетом а) получим нечто хорошее....
в) а можно домножать и на $P_i^m$, для всех $m$....

[vpb]

(Думаю, тут лучше про пространство и операторы не вспоминать, а сразу брать группы за рога... )

Пусть $\sigma$ --- перестановка символов $1,\ldots,n$. Тогда ей можно сопоставить перестановочную матрицу $P(\sigma)$. Соответствие $\sigma\mapsto P(\sigma)$ --- изоморфизм из $S_n$ на некоторую группу матриц. Подробности в учебниках.

Значит, у вас есть $n$ перестановок $\sigma_1,\ldots,\sigma_n$, и известно что ?
(1) Любые две из них коммутируют, (почему? докажите) и
(2) для любых $i$, $j$ существует ровно одно $k$ такое, что $\sigma_k(i)=j$.
Надо доказать, что $\{\sigma_1,\ldots,\sigma_n\}$ --- это некоторая подгруппа в $S_n$. Покажите, что
(1) если есть какая-то конечная группа, то любая ее подполугруппа --- на самом деле подгруппа,
(2) подполугруппа в $S_n$, порожденная всеми $\sigma_i$ --- абелева подгруппа в $S_n$,
(3) если $A$ --- абелева группа, точно и транзитивно действующая на некотором множестве $\Omega$,
то $|A|=|\Omega|$. Отсюда выведите то, что надо.

[Paul Ivanov]

DeBill, понятия "пространство" и всех прилегающих к нему я ещё не знаю, нужно справиться с этой задачей исключительно с помощью того, что я уже прошёл.
vpb, если я правильно понимаю, то, под подполугруппой группы вы подразумеваете полугруппу, являющуюся подмножеством данной группы, но если полугруппа это множество на котором задано ассоциативное умножение (допустим даже не выводящее за пределы данного множества), то вот вам контрпример: пусть $S_4$ - множество всех подстановок длины 4, тогда оно является группой, рассмотрим следующее его подмножество:

$$\left\lbrace\sigma_1=\begin{bmatrix} 1 & 2 & 3 & 4\\ 2 & 1 & 4 & 3 \end{bmatrix}, \sigma_2=\begin{bmatrix} 1 & 2 & 3 & 4\\ 3 & 4 & 1 & 2 \end{bmatrix}, \sigma_3=\begin{bmatrix} 1 & 2 & 3 & 4\\ 4 & 3 & 2 & 1 \end{bmatrix}\right\rbrace$$

и оно, как нетрудно проверить является подполугруппой $S_4$, однако не является подгруппой. Если же вы под полугруппой понимали полугруппу, являющуюся подгруппой, то в предложенном вами плане доказательства первый пункт - это тождество и его не надо доказывать.
В общем хочу предложить вам то, что за это время удалось установить:
во-первых мне не удалось понять, как переформулировать коммутативность перестановок. Пусть $\sigma_1=\tau_1(\tau_2(...(\tau_h)))$ где $\tau_1, \tau_2, ..., \tau_h$ - независимые циклы (ни один из них не равен единичной или по-другому эквивалентной подстановке), в таком случае $\sigma_2$ такое, что $\sigma_1(\sigma_2)=\sigma_2(\sigma_1)$ подбирается следующим образом: пусть $\tau_i$ и $\tau_j$ - независимые циклы одинаковой длины $k$ и пусть $\sigma_1(p_i)=\tau_i(p_i) \ne p_i$, где $p_i$ - например, наименьшее возможное, и $\sigma_1(q_i)=\tau_j(q_i) \ne q_i$, где $q_i$ - некоторый произвольный параметр, удовлетворяющий этому условию и подбираемый для выбранного цикла $\tau_i$. Тогда

$$\sigma_2(p_i)=q_i \wedge \sigma_1(\sigma_2)=\sigma_2(\sigma_1) \Rightarrow \sigma_2(\tau_i(p_i))=\tau_j(q_i) \Rightarrow ... \Rightarrow \sigma_2(\tau_i^k(p_i))=\tau_j^k(q_i)$$

. Таким образом $\sigma_2$, как нетрудно проверить, отображает изоморфно (если так можно выразиться) цикл $\tau_i$ в цикл $\tau_j$ причём единственная свобода данного отображения заключается в выборе $q_i$ (заметим, что $q_i$ может выбираться из самого цикла $\tau_i$ и тогда будем говорить, что этот цикл отображается в себя). Таким образом свобода изменения $\sigma_2$ полностью ограничивается подбором параметров $q_1, q_2, ..., q_h$ и остальными параметрами, число которых равно числу $x$ таких $r$, что $\sigma_1(r)=r$ (число независимых циклов длины 1). Отсюда непонятно, как выразить $\sigma_2$ через $\tau_1, \tau_2, ..., \tau_h$ используя данные параметры, хотя эти параметры и эти независимые циклы полностью определяют $\sigma_2$. В общем приходится довольствоваться отнюдь не кратким представлением о том, как строится $\sigma_2$ по $\sigma_1$.
Итак, следующий шаг такой, покажем, что длины всех независимых циклов, формирующих $\sigma_1$ равны $k$ (свойство 3). Так как соблюдается свойство 1, то количество полностью различных подстановок равно $n$, но если есть независимые циклы разной длины, то для какой-то выбранной длины $k$ с количеством $m$ циклов данной длины в подстановке $\sigma_1$ существует не более $mk<n$ полностью различных подстановок, противоречие. Следовательно мы имеем $h$ независимых циклов длины $k$, и $hk=n$.
(Всюду далее будем считать, что $A$ - это также и множество всех подстановок соответствующих матрицам из $A$, неприятностей от такого допущения быть не должно).
Далее у меня получилось доказать, что в множестве $A$ есть единичная матрица (и соответствующая ей эквивалентная подстановка (свойство 4), для этого достаточно, используя свойство 3, которое применимо ко всем подстановкам из $A$, показать, что если в некоторой $\sigma$ из $A$ $q_1=p_1$, то $q_2=p_2$ и $q_3=p_3$ и т.д.), а также, что для любой матрицы из $A$, в $A$ есть обратная ей матрица (соответственно для любой подстановки $\sigma_1$ в $A$, в $A$ есть обратная подстановка (свойство 5), для этого также используя свойство 3, достаточно показать, что если в подстановке $\sigma$ хотя бы один цикл из $\sigma_1$, допустим $\tau_1$, отображается как $\tau_1^{-1}$, то есть на теле данного цикла отображение $\sigma$ обратно $\sigma_1$, то автоматически $\sigma=\sigma_1^{-1}$).
Всё это очень громоздко, к сожалению, и используя свойство 3 и даже допустим свойства 4 и 5 непонятно, как доказать свойство 6 (то есть, что операция умножения подстановок не выводит за границы $A$). Нужны ещё идеи.

[Otta]

Paul Ivanov в сообщении #1358238 писал(а):

и оно, как нетрудно проверить является подполугруппой $S_4$,

$\sigma_1^2=?$

[Paul Ivanov]

Согласен, моя ошибка. Тогда следующий вопрос:

vpb в сообщении #1358028 писал(а):

(2) подполугруппа в $S_n$, порожденная всеми $\sigma_i$ --- абелева подгруппа в $S_n$,

как доказать, что множество всех $\sigma_i$ - это подполугруппа? Или я чего то не понял?

[DeBill]

Paul Ivanov в сообщении #1358238 писал(а):

у меня получилось доказать, что в множестве $A$ есть единичная матрица

Ну и хорошо - т.е., Вы сумели получить это без использования критерия коммутативности матриц (прошли п. а)).
Далее можно таки использовать п. б) и в) того же плана

-- 03.12.2018, 01:30 --

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

[Paul Ivanov]

DeBill

DeBill в сообщении #1358299 писал(а):

Ну и хорошо - т.е., Вы сумели получить это без использования критерия коммутативности матриц (прошли п. а)).

Как же без использования коммутативности? Я её использовал самым прямым образом

DeBill в сообщении #1358299 писал(а):

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

Легко можно придумать пример, когда набор не состоит из степеней одной из матриц. Один из таких примеров получается, если к моим трём подстановкам из моего неправильного контрпримера добавить единичную (эквивалентную) подстановку в качестве четвёртой. Тогда ни одна из матриц не будет той самой, для которой верно, что набор состоит из её степеней.
Всё ещё жду конкретных идей...

[vpb]

Paul Ivanov в сообщении #1358316 писал(а):

Легко можно придумать пример, когда набор не состоит из степеней одной из матриц. Один из таких примеров получается, если к моим трём подстановкам из моего неправильного контрпримера добавить единичную (эквивалентную) подстановку в качестве четвёртой. Тогда ни одна из матриц не будет той самой, для которой верно, что набор состоит из её степеней

Да, это правильно (а коллега ошибся; таки ж не алгебраист, похоже).

-- 02.12.2018, 23:29 --

Paul Ivanov в сообщении #1358316 писал(а):

Всё ещё жду конкретных идей...

Знаете, нетерпеливый вы наш, у меня есть для вас хорошая идея: взять Кострикина 1-й том и начать его читать систематически. Иными словами, Вам следует приобрести общие знания алгебры. Ваш длинный пост показывает полное незнание, увы (во всяком случае, мне там ничего не понятно). (Я, извините, даже не буду указывать на ошибки, т.к. у Вас их слишком уж много). При такой ситуации обсуждать дальше задачу из Тыртышникова не вижу возможности.

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

[DeBill]

Paul Ivanov в сообщении #1358316 писал(а):

Как же без использования коммутативности? Я её использовал самым прямым образом

Я не говорил этого. Я говорил об использовании КРИТЕРИЯ коммутативности матриц.

Paul Ivanov в сообщении #1358316 писал(а):

Тогда ни одна из матриц не будет той самой, для которой верно, что набор состоит из её степеней.

Это - да, это я погорячился: этого не получится. Дык этого от нас и не требовали.
Однако, я не понимаю, чем Вам не нравится уже описанный план:
1. Вы умеете доказывать, что из свойств 1) и 2) следует: в списке есть единичная матрица.
2. Если для набора $P_1,...,P_n$ выполняются свойства 1) и 2), то они же выполняются для набора $P_iP_1,...,P_iP_n$
3. Из 1. и 2. следует: в наборе есть обратная к каждой из $P_i$
4. Применяя 2. дважды, получим: есть и обратная к $P_iP_j$. Тогда их 3 следует: есть и $P_iP_j$
И - да, я не алгебраист.

[vpb]

Может быть, так тоже задачу можно решить (правда, не знаю точно).

[Paul Ivanov]

DeBill
Спасибо, вы очень помогли. Чем дольше сидишь над одной и той же задачей, тем, к сожалению, меньше шанс найти творческое решение.

[vpb]

Вот решение. Может быть, в книжке что-то похожее имелось в виду.

Напомним, что перестановочная матрица --- это матрица, имеющая в каждой строке и каждом столбце одну единицу, а остальные элементы соответствующей строки или столбца --- нули. Эквивалентно, это матрица вида $P(\sigma)$, имеющая $1$ на местах $(\sigma(i),i)$, $i=1,\ldots,n$ (а остальные --- нули), где $\sigma\in S_n$ --- некоторая перестановка.

Пусть $C_i$, $i=1,\ldots,n$ --- координатные столбцы, т.е. $C_i$ --- столбец, имеющий $1$ на $i$-м месте, и нули в остальных местах. Если $X$ --- любая перестановочная матрица, то $XC_i$ --- всегда тоже координатный столбец. Более точно, $P(\sigma)C_i=C_{\sigma(i)}$.

Обратимся собственно к задаче. Довольно ясно, что все $P_i$ --- перестановочные матрицы. Перенумеруем их так, чтобы у $P_i$ в первом столбце было $1$ на $i$-м месте, т.е. чтобы первый столбец в $P_i$ был равен $C_i$. Определим бинарную операцию $\ast$ на множестве $\{1,\ldots,n\}$ следующим условием: $P_iC_j=C_{x\ast j}$. Иначе говоря, $i\ast j$ --- это место единицы в $j$-м столбце матрицы $P_i$.

Из того, что $P_i$ --- перестановочные матрицы, следует, что при данном $i$ правило $j\mapsto i\ast j$ определяет перестановку на $1,\ldots,n$. А из того, что $P_1+\ldots+P_n=E$, следует, что правило $i\mapsto i\ast j$ --- также перестановка для каждого $j$.

Поскольку $C_j$ --- это первый столбец в матрице $P_j$, то $C_{i\ast j}=P_iC_j$ --- первый столбец в матрице $P_iP_j$. Теперь из того, что $P_iP_j=P_jP_i$, следует, что $C_{i\ast j}=C_{j\ast i}$, значит $i\ast j=j\ast i$. Т.е. операция $\ast$ коммутативна.

Затем, $P_iP_jC_k=P_iC_{j\ast k}=C_{i\ast(j\ast k)}$. Но $P_iP_jC_k=P_jP_iC_k$, значит $i\ast(j\ast k)=j\ast(i\ast k)$, для любых $i,j,k$. Отсюда $i\ast(k\ast j)=(i\ast k)\ast j$, значит операция $\ast$ ассоциативна.

Наконец, $1\ast1=1$, отсюда $(x\ast1)\ast1=x\ast(1\ast1)=x\ast1$. Поскольку $x\ast1$ пробегает все $1,\ldots,n$, то $y\ast1=y$ для любого $y$, значит $1$ --- правая единица относительно $\ast$. Аналогично показывается, что
$1$ является и левой единицей. Теперь из того, что $i\mapsto i\ast x$ --- перестановка для каждого $i$, следует, что $\{1,\ldots,n\}$ --- абелева группа относительно $\ast$. А отсюда уже нетрудно получить и то, что $\{P_1,\ldots,P_n\}$ --- абелева группа.

(Оффтоп)

(Только возможность того, что студент 1-го семестра найдет доказательство такого типа, или вообще правильно решит задачу, представляется весьма сомнительной.)