Верно ли решение (Линал)

[artempalkin]

Задача (это из Putnam 1985 года):

Пусть дано $r$ действительных квадратных матриц $M_i$ $n\times n$, составляющих группу по умножению матриц. Пусть также $\Sigma\limits_{i=1}^r \operatorname{tr}(M_i)=0$. Докажите, что $\Sigma\limits_{i=1}^r M_i=0$.

Я решил, но что-то меня беспокоит в моем решении, не могу понять точно, что... Подскажите, правильно ли? И если да, может, есть путь проще/быстрее?

Пусть $M=\Sigma\limits_{i=1}^r M_i$. Тогда $M_iM=M$, а $M^2=rM$ (потому что эта система матриц является группой).
Пусть $\lambda_k$ ($k=1..n$) - собственные значения матрицы $M$ (возможно, не все они различны). Тогда:

$$M^2=rM$$

$$\operatorname{tr}(M^2)=\operatorname{tr}(rM)$$

$$\Sigma\limits_{k=1}^n \lambda_k^2=r\operatorname{tr}(M)=0,$$

из чего следует, что все $\lambda_k=0$.

Отсюда следует, что матрица $M$ нильпотентна, а это значит, что, во всяком случае, $M^n=0$. Но ведь $M^n=r^{n-1}M$. Значит, $M=0$.

[nnosipov]

artempalkin в сообщении #1480276 писал(а):

из чего следует, что все $\lambda_k=0$

Это верно, если все $\lambda_k$ вещественны. А если среди них есть комплексные?

В целом, идея хорошая, можно дожать до полного решения. Дожимайте.

[artempalkin]

nnosipov в сообщении #1480278 писал(а):

А если среди них есть комплексные?

О, спасибо! Вот интуитивно чувствовал, что что-то не так, но проглядел нюанс...

В таком случае придется использовать более сильное утверждение: поскольку $M^p=r^{p-1}M$ для $\forall p\in \mathbb{N}$, то и между собственными значениями должно быть такое соотношение: $\lambda_k^2=r\lambda_k$. Это возможно только если $\lambda_k=0$ либо $r$. Но $r$ ни одно из них быть равно не может, т.к. в таком случае след $M$ не был бы равен нулю. Тогда все $\lambda_k=0$, и дальше вся логика сохраняется.

[nnosipov]

artempalkin
Да, все верно. Можно было также вывести, что $\sum \lambda_k^p=0$ для $p=1,2,\dots,n$, и затем сделать вывод, что все $\lambda_k$ равны нулю. Но у Вас получилось даже изящней.

[svv]

artempalkin
Отбросим условие $\sum\limits_i\operatorname{tr}M_i=0$. Что вообще можно сказать о сумме матриц, составляющих конечную группу по умножению?

Удобно определить $M$ чуть иначе — как «среднее арифметическое» элементов группы:
$M=\frac 1 r\sum\limits_i M_i$
Тогда $M^2=M$. Пусть $U$ — единица группы (она не обязана быть единичной матрицей $E_n$). Тогда также $U^2=U$. Итак, $U$ и $M$ — идемпотенты. Поэтому они диагонализируемы и, более того, в силу $UM=MU$ они одновременно диагонализируемы некоторым преобразованием подобия.

Чтобы не плодить обозначения, будем считать, что $U$ и $M$ уже приведены к диагональному виду. Преобразование подобия сохраняет собственные значения. Идемпотентные матрицы имеют собственные значения $0$ или $1$ — и это единственные возможные значения диагональных элементов $U$ и $M$.

Дальше надо рассмотреть пары $u_{ii}$ и $m_{ii}$ с одинаковыми значениями индексов и возможные комбинации их значений. Легко видеть, что комбинация $u_{ii}=0,m_{ii}=1$ невозможна. Остальные возможны, как показывает пример группы из двух вырожденных (!) диагональных матриц $3\times 3$:
$M_1=\operatorname{diag}(1,1,0)=U$
$M_2=\operatorname{diag}(-1,1,0)$
Дальнейший анализ в этом направлении позволяет найти условия, при которых диагональные элементы $M$ равны нулю или единице.

[artempalkin]

svv в сообщении #1480470 писал(а):

Отбросим условие $\sum\limits_i\operatorname{tr}M_i=0$.

Я так понимаю, что это не имеет отношения к решению задачи, а больше просто размышления на тему? Кстати, тема очень интересная (хотя, наверное, для специалистов теории групп тривиальная и давно исследованная).

svv в сообщении #1480470 писал(а):

Итак, $U$ и $M$ — идемпотенты. Поэтому они диагонализируемы

Хммм, вот этот момент требует некоторого переваривания для меня... Я так понимаю, что если, к примеру, $A^2=A$, то есть матрица идемпотентна, то ее жорданова форма будет обязана состоять из единичных клеток (т.к. неединичная жорданова клетка в квадрате саму себя не даст никак). Правильно я размышляю? Или лучше зайти с другой стороны?

svv в сообщении #1480470 писал(а):

более того, в силу $UM=MU$ они одновременно диагонализируемы некоторым преобразованием подобия.

О да. Вот этот факт интересный. Вообще я, конечно, применял этот факт многократно в квантах, но как его доказать? Я вот навскидку вижу, как доказать, что собственные подпространства одного будут инвариантными подпространствами другого... но дальше... надо подумать...

svv в сообщении #1480470 писал(а):

из двух вырожденных (!)

А почему (!)? :)

svv в сообщении #1480470 писал(а):

Дальнейший анализ в этом направлении позволяет найти условия, при которых диагональные элементы $M$ равны нулю или единице.

Интересен такой вопрос: каковы могут быть кратности этих собственных значений?
И еще такой вопрос: пусть у матрицы $A$ собственные значения 0 и 1, и она диагонализируема. Достаточное ли это условие, чтобы она стала матрицей $M$ из нашей задачи?

-- 16.09.2020, 19:26 --

svv в сообщении #1480470 писал(а):

Тогда также $U^2=U$. Итак, $U$ и $M$ — идемпотенты. Поэтому они диагонализируемы и, более того, в силу $UM=MU$ они одновременно диагонализируемы некоторым преобразованием подобия.

Я вроде бы понял.
Тут два разных утверждения:
1) Пусть $U$ и $M$ операторы простой структуры и при этом $UM=MU$. Тогда эти операторы будут иметь диагональные матрицы в одном и том же базисе. Это доказать несложно.

2) Пусть $U$ - оператор простой структуры, $M$ - оператор общего вида, и $UM=MU$. Тогда собственные подпространства $U$ будут инвариантными подпространствами $M$ (возможно, верно и какое-то чуть более сильное утверждение, но точно нельзя утверждать, что $M$ будет оператором простой структуры).

[svv]

artempalkin в сообщении #1483463 писал(а):

Я так понимаю, что это не имеет отношения к решению задачи, а больше просто размышления на тему?

Отбрасывая одно условие, мы получаем более общую ситуацию, где $\Sigma\limits_i \operatorname{tr}(M_i)=0$ будет частным случаем. Оказалось, что несложно перечислить и исследовать возможные варианты и не опираясь на это условие. Оставшиеся условия уже незыблемы и дают, на мой взгляд, очень естественную постановку вопроса:
Конечное множество матриц образует группу по умножению; что можно сказать о сумме всех матриц группы?

artempalkin в сообщении #1483463 писал(а):

Я так понимаю, что если, к примеру, $A^2=A$, то есть матрица идемпотентна, то ее жорданова форма будет обязана состоять из единичных клеток (т.к. неединичная жорданова клетка в квадрате саму себя не даст никак). Правильно я размышляю?

Да, вполне. Ещё два доказательства см. здесь:
https://math.stackexchange.com/questions/600745/idempotent-matrix-is-diagonalizable
Итак, Идемпотентная матрица диагонализируема, а её собственные значения равны $0$ или $1$.

artempalkin в сообщении #1483463 писал(а):

svv в сообщении #1480470 писал(а):

более того, в силу $UM=MU$ они одновременно диагонализируемы некоторым преобразованием подобия.

Вот этот факт интересный. Вообще я, конечно, применял этот факт многократно в квантах, но как его доказать?

На всякий случай уточню формулировку: Если $A$ и $B$ диагонализируемы и коммутируют, существует преобразование подобия, диагонализирующее и $A$, и $B$.
Тут тоже могут быть различные доказательства. Одно из них приведено в книге Horn, Johnson. Matrix Analysis, 2013 (2nd edition), Theorem 1.3.12, p.62. Вкратце идея такая. Применим к матрицам $A$ и $B$ преобразование, приводящее $A$ к диагональному виду и группирующее её равные собственные значения вместе (и результат опять обозначим $A$ и $B$ ). Матрица $A$ стала блочно-диагональной, причём $k$-й диагональный блок (квадратный) равен $\lambda_k E_{n_k}$, где $\lambda_k$ — $k$-е собственное значение $A$, $n_k$ — его кратность. Разобъём $B$ на блоки согласованно с $A$. Из $AB=BA$ можно получить, что все недиагональные блоки $B$ нулевые, т.е. матрица $B$ блочно-диагональна. Теперь к каждому из диагональных блоков $B$ применим преобразование, которое его диагонализирует. Это же преобразование, применённое к соответствующему блоку матрицы $A$, его не изменит.

artempalkin в сообщении #1483463 писал(а):

А почему (!)? :)

Я хотел подчеркнуть, что группа может состоять и из вырожденных матриц, например, $\begin{bmatrix}1&0\\0&0\end{bmatrix}$ и $\begin{bmatrix}-1&0\\0&0\end{bmatrix}$. И почему-то подумал, что это может показаться необычным.

artempalkin в сообщении #1483463 писал(а):

Интересен такой вопрос: каковы могут быть кратности этих собственных значений?

Сегодня уже поздно, вынужден прерваться, постараюсь ответить завтра.

[artempalkin]

svv в сообщении #1483508 писал(а):

Да, вполне. Ещё два доказательства см. здесь:
https://math.stackexchange.com/question ... onalizable

Да, первое доказательство очень простое, при этом не требующее каких-то особенных дополнительных утверждений ("школьное" доказательство своего рода).
А вот во втором доказательстве учитывается интересный факт, который я раньше не встречал, кажется: Оператор является диагонализируемым тогда и только тогда, когда его минимальный обнуляющий многочлен раскладывается на различные линейные множители (то есть, по сути, нет кратных корней).
Это очень глубокое утверждение, на самом деле... как бы его так доказать... То есть в сторону "тогда" это понятно (просто рассмотреть полином $(x-\lambda_1)\cdot...\cdot(x-\lambda_k)$, где $\lambda_i$ - собственные значения оператора $A$), то вот "только тогда" куда более интересно.

-- 17.09.2020, 09:16 --

Придумал доказательство, как всегда через жордановы формы, конечно. Мне кажется, такие доказательства какие-то mauvais ton. Но что поделать...
Нам известно, что матрица $A$ является корнем своего минимального многочлена $(x-a_1)...(x-a_l)$, где все множители различны. С другой стороны мы знаем, что она является корнем своего характеристического многочлена. Значит, $a_i$ - это некоторые собственные значения матрицы $A$ (т.к. минимальный многочлен является делителем любого обнуляющего).

Подставим матрицу $A$ в минимальный многочлен: $(A-\lambda_1E)...(A-\lambda_lE)=0$. Приведем матрицу $A$ к жордановой форме (обозначения, конечно, сохраним ). Матрица $A$ является прямой суммой своих жордановых клеток, их произведение можно рассматривать отдельно. Итак, если $K_{\lambda}$ - некоторая жорданова клетка, соответствующая с.з. $\lambda$, то $(K_{\lambda}-\lambda_1E)...(K_{\lambda}-\lambda_lE)=0$.

Если среди $\lambda_i$, которые присутствуют в многочлене, нет $\lambda$, то такое произведение нулю никак не может быть равно (заодно мы доказываем, что в этом минимальном многочлене обязательно должны быть все собственные значения). Если же есть, то мы получим произведение некоторого количества верхнетреугольных матриц (причем на диагоналях нет ни одного нулевого элемента) на строго верхнетреугольную (причем на первой наддиагонали стоят единицы). Произведение их нулю равно не будет (строго верхнетреугольная матрица просто "поднимет" диагональ на одну клетку вверх), кроме случая, когда порядок $K_{\lambda}$ равен 1, ч.т.д..

-- 17.09.2020, 09:30 --

svv в сообщении #1483508 писал(а):

Я хотел подчеркнуть, что группа может состоять и из вырожденных матриц,

Ага, ну да, я думал об этом, в процессе решения этой и других задач, и пришел к этому выводу тоже :)

[svv]

artempalkin в сообщении #1483517 писал(а):

Мне кажется, такие доказательства какие-то mauvais ton.

Одно время я тоже так думал (именно про доказательства с помощью жордановой формы), потом решил, что это комплексы.

artempalkin в сообщении #1483517 писал(а):

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

Интуитивно понятно (хотя утверждение действительно глубокое). Допустим, минимальный многочлен содержит кратные множители, например, $(\mathsf A-\lambda)^n$. Тогда в корневом подпространстве $V_\lambda$ существует вектор $v$, который аннулируется оператором $(\mathsf A-\lambda)^n$, но не аннулируется оператором $\mathsf A-\lambda$, т.е. он корневой (высоты $n>1$), но не собственный. Если бы оператор был диагонализируемым, любой такой вектор «убивался» бы с одного раза. Вы говорили о том же, только в терминах ЖНФ.

Вернёмся к нашим матрицам. Итак, можно перейти к базису, в котором обе матрицы, $U$ и $M=\frac 1 r\sum\limits_i M_i$, диагональны, и все их элементы равны $1$ либо $0$. Причём можно считать, что сначала идут все единицы, а потом все нули. В том же базисе рассматриваем и все $M_i$.

Пусть $U$ содержит на диагонали $s$ единиц и $n-s$ нулей. Так как $UM_i=M_iU=M_i$, то у любой $M_i$ последние $n-s$ строк и последние $n-s$ столбцов нулевые. Значит, такова же и $M$ (стало быть, при $u_{kk}=0$ невозможно $m_{kk}=1$). Ясно, что такое «обрамление» из нулевых строк и столбцов у всех $M_i$ представляет собой тривиальную и неинтересную часть, поэтому отбросим («обдерём╗) эти строки и столбцы и будем считать, что матрица $U=E$.

Подходим к самому интересному вопросу: чем определяется (уже после «обдирания») количество единиц и нулей на диагонали $M$?

[artempalkin]

svv в сообщении #1483538 писал(а):

отбросим («обдерём╗) эти строки и столбцы и будем считать, что матрица $U=E$.

В таком случае, получается, мы доказали, что любая группа матриц, у которой единица - вырожденная матрица, изоморфна группе матриц, у которых единица - это единичная матрица. Более того, в нашей группе все матрицы невырождены. Прекрасно.

svv в сообщении #1483538 писал(а):

Подходим к самому интересному вопросу: чем определяется (уже после «обдирания») количество единиц и нулей на диагонали $M$?

Ну, во-первых, если рассмотреть тривиальную группу из одной лишь единицы, то нулей в $M$ не будет вообще
В любой другой группе у $M$ будет хотя бы один ноль (это следует из того, что она должна быть вырождена, т.к., к примеру, $M_1\cdot M=M$, где $M_1$ - любая не-единица из группы).

Вообще же, конечно, тяжело быть матрицей $M$. При умножении на любую матрицу из группы она оставляет либо несколько ее первых столбцов, либо первые несколько строк (в зависимости от того, с какой стороны домножать), и при этом все равно должна получаться эта самая матрица $M$! Получается, все матрицы в группе имеют квазидиагональный вид, где верхний левый блок - это часть с единицами от $M$, а главное содержание их будет в нижнем правом блоке. Эти нижние правые блоки, если рассмотреть их отдельно:

1) составляют группу по операции умножения матриц
2) невырождены
3) в сумме дают нулевую матрицу

-- 17.09.2020, 17:45 --

Получается, что матричные группы, сумма матриц в которых равна нулю, являются своего рода "прагруппами", на их основе строятся все те группы, в которых сумма равна чему-то другому.
Получается, что принципиальным является количество не единиц в матрице $M$, а нулей. Вопрос формулируется так: представим себе группу из матриц; для каких порядков матриц возможно, чтобы сумма этих матриц была равна нулевой матрице?

-- 17.09.2020, 18:05 --

Рассмотрим множество диагональных квадратных матриц порядка $n$ таких, что на диагоналях стоят только $1$ и $-1$. Это множество, очевидно, будет группой, и в сумме будет давать нулевую матрицу для любого $n$. Итого для каждого $n$ можно придумать такую группу матриц, что их сумма будет равна 0.

Это все в свою очередь означает, что любая идемпотентная матрица будет матрицей $M$ для некоторой группы матриц.

[svv]

artempalkin в сообщении #1483549 писал(а):

Вообще же, конечно, тяжело быть матрицей $M$. При умножении на любую матрицу из группы она оставляет либо несколько ее первых столбцов, либо первые несколько строк (в зависимости от того, с какой стороны домножать), и при этом все равно должна получаться эта самая матрица $M$! Получается, все матрицы в группе имеют квазидиагональный вид, где верхний левый блок - это часть с единицами от $M$, а главное содержание их будет в нижнем правом блоке.

Вы совершенно правы. Представим в блочном виде $M$ и какую-нибудь из $M_i$ (с согласованным разбиением на блоки):
$M=\begin{bmatrix}E&O\\O&O\end{bmatrix}, \quad M_i=\begin{bmatrix}A&B\\C&D\end{bmatrix}$
Тогда $MM_i=M_iM=M$ запишется как
$\begin{bmatrix}E&O\\O&O\end{bmatrix}\begin{bmatrix}A&B\\C&D\end{bmatrix}=\begin{bmatrix}A&B\\C&D\end{bmatrix}\begin{bmatrix}E&O\\O&O\end{bmatrix}=\begin{bmatrix}E&O\\O&O\end{bmatrix}$
Отсюда $A=E, B=C=O$, и $M_i$ (т.е. любая матрица группы) имеет вид $\begin{bmatrix}E&O\\O&D\end{bmatrix}$

Выходит, что в $M$ лишь в тех строках/столбцах могут быть единицы на диагонали, в которых все элементы группы имеют вот такую тривиальную структуру: $\begin{bmatrix}E&O\\O&\ldots\end{bmatrix}$
В тех же строках/столбцах, в которых хоть один элемент группы отступает от этой структуры, $M$ имеет лишь нулевые элементы на диагонали.

Пожалуй, это всё, что я хотел сообщить.

-- Пт сен 18, 2020 03:18:35 --

artempalkin в сообщении #1483549 писал(а):

Рассмотрим множество диагональных квадратных матриц порядка $n$ таких, что на диагоналях стоят только $1$ и $-1$. Это множество, очевидно, будет группой, и в сумме будет давать нулевую матрицу для любого $n$. Итого для каждого $n$ можно придумать такую группу матриц, что их сумма будет равна 0.

Это все в свою очередь означает, что любая идемпотентная матрица будет матрицей $M$ для некоторой группы матриц.

Да, согласен.