Математики играют в морской бой

[xaxam]

Из жизни нильпотентов
Exegi monumentum
Оглядев себя и оценив перспективы свершить революцию в какой-нибудь области, по здравому размышлению решил изъясняться афоризмами. Может, кто и запомнит. В отношении предмета обсуждения в данных двух постах, попробую свои силы.

❝Линейная алгебра - область математики, где решение любого конкретного вопроса сводится к решению системы линейных алгебраических уравнений степени не выше первой. Проблема - в понимании слова "сводится".

Ключевой вопрос линейной алгебры в своей шекспировской простоте предельно прост: Быть иль не быть? Ноль иль не ноль?❞
Пролог
Слово "нильпотент", ясное дело, латинского происхождения, и оно не имеет никакого отношения к сексуальным способностям. Nil - это нуль, potentia на английский переводится как force, power, а английское power на русский переводится как степень. Нильпотент - это объект, который после возведения в некоторую степень даёт нуль. Xn = 0. Слабо решить такое уравнение?

Разумеется, надо уточнить, в каком классе мы собираемся искать решение. Если в каком-нибудь поле - то ничего нетривиального не получится: единственное решение будет нулевое (хоть рациональное, хоть вещественное, хоть комплексное). А в каких ещё классах можно искать решение? Степенная запись подразумевает наличие операции умножения, т.е., за сценой должна быть какая-то группа с операцией умножения. Явное присутствие нуля подразумевает, что где-то рядом есть ещё и операция сложения, для которой ноль - весьма особенный элемент. Множество с двумя операциями (связанными естественными соотношениями) называется кольцом, а если элементы этого множества можно ещё умножать на какие-нибудь числа, - то алгеброй. Много ли мы знаем алгебр? На самом деле, конечно, очень много разных, но одна из этих алгебр имеет самое непосредственное отношение к теме данного рассказа.

Очевидное утверждение.  Для любого векторного пространства V над любым числовым полем F линейные операторы вида А: V → V образуют алгебру, в которой роль умножения играет операция композиции, (AB)v = A(Bv) (напомню: в линейном случае мы не заключаем аргумент в скобки, и даже точку не ставим, если это не требуется явно!). Сложение операторов и умножение на числа определяются естественным образом.

Ахтунг. Умножение в этой алгебре некоммутативно (операция композиции вообще довольно редко бывает коммутативной: равенство AB = BA несёт довольно большую информацию об элементах А и В). Алгебра вообще говоря не является группой по отношению к такому умножению: единичный элемент (тождественный оператор), конечно, наличествует, но далеко не каждый ненулевой элемент в этой алгебре обратим. С другой стороны, критерий обратимости мы уже знаем: оператор А обратим тогда и только тогда, когда det A ≠ 0: в этой ситуации у оператора есть и левый, и правый обратные операторы, и они совпадают.

Заметим в очередной раз: совокупность линейных операторов образует алгебру только при условии, что они действуют из какого-то линейного пространства в него же. В противном случае у нас возникнут проблемы с вычислением композиции операторов (она же "матричное произведение": собственно, неочевидная формула для матричного произведения возникает как раз когда мы вычисляем композицию двух линейных операторов, действующих на одном и том же арифметическом линейном пространстве V = Fn).

Итак, мы "придумали" (обнаружили, конечно) ещё один естественный контекст, в котором уравнение Xn = 0 имеет смысл. Может ли оно иметь нетривиальные решения? Ответ - да, и мы видели такое решение. Пусть V = Fn[ x ] - линейное пространство многочленов степени ≤ n−1 от переменной х, и D - оператор дифференцирования по иксу. Каждое такое дифференцирование уменьшает степень любого полинома f ∈ V на единицу. Значит, Dn−1f обязано быть константой, которую убъёт ещё одно дифференцирование. Таким образом, Dn = 0.

Задача. В приведённом примере степень n уравнения равна размерности пространства. Это случайное совпадение? Ответ: наполовину. Понятно, что если Dm = 0 при каком-то m < n, то и Dn будет нулём. Такое бывает: рассмотрите прямую сумму двух пространств Fn[ x ] и Fm[ x ]. Размерность этой прямой суммы будет n + m, а минимальное значение r, при котором Dr = 0, равно r = max{n,m}.
С другой стороны, ниже мы увидим, что если An ≠ 0 при n = dim V, то уже никакая более высокая степень оператора А не сможет обратиться в нуль.

Спектр нильпотентных операторов
Мы проделали некоторую часть работы, обсуждая собственные числа (корни характеристического многочлена). Мы поняли, что засада состоит в наличии кратных корней характеристического уравнения. Что дальше? Давайте рассмотрим частный случай, - оператор А, у которого характеристическое уравнение имеет единственный корень. Без ограничения общности можно считать, что этот корень равен нулю: если это не так, то заменим А на В = A − λE.

Теорема.   Оператор А нильпотентный, если и только если его характеристический полином имеет единственный корень λ = 0.

Доказательство. Если есть ненулевой корень характеристического полинома, то есть и ненулевой вектор v и ненулевое число λ такие, что Av = λv. Такое соотношение, сколько ни итерируй, не сможет убить вектор v, значит, все степени А - ненулевые операторы.

В другую сторону, докажем, что оператор с единственным собственным значением λ = 0 нильпотентный, более конкретно, Аn = 0, где n - размерность пространства V, на котором действует оператор.

Рассмотрим образ V1 = АV. Это подпространство, очевидным образом инвариантное для А, и его размерность уменьшилась: dim V1 < dim V, и это неравенство строгое. Почему? да просто потому, что λ = 0 собственное число, и соответствущий собственный вектор будет "убит" оператором А. Тем самым ядро А нетривиальное, а значит, образ А не может иметь ту же размерность, что V.

Это рассуждение может быть итерировано. Рассмотрим образ V2 = АV1 = А2V. Ограничение оператора А на V1 по-прежнему имеет единственное собственное число λ = 0 (откуда бы взяться чему-то ещё?), и ровно по тем же соображениям, что и выше, V2 ⊂ V1 будет инвариантным пространством размерности строго меньше, чем dim V1.

Сколько раз можно повторять эту процедуру? Она даёт нам цепочку убывающих строго вложенных подпространств V = V0 ⊃ V1 ⊃ V2 ⊃ ..., начинающуюся с размерности n. После самое большее n шагов мы спустимся по этой лесенке до нуля, а это и значит, что соответствующая степень оператора А будет тождественным нулём, ЧТД.

Итак, у нас есть эффективный критерий нильпотентности оператора.

Следствие.  Оператор А имеет единственное собственное число, если и только если разность A − λE нильпотентна. Утверждение очевидное, поскольку собственные числа операторов А и A − λE отличаются на λ.

Структура действия нильпотентных операторов
Осталось сравнительно немногое - найти базис, в котором действие нильпотентного оператора будет выглядеть особенно просто. Мы сделаем это, построив возрастающую цепочку подпространств, а для этого зайдём "с другого конца".
Возьмём самую высокая степень оператора А, которая ещё не равна нулю и её образ Z0 ≠ 0. Сравним Z0 с его прообразом Z1 = А−1 Z0. Этот прообраз содержит в себе Z0, но совпадение не исключено.

Пример. Пусть А - тождественно нулевой оператор. Тогда самая высокая, но ещё ненулевая степень А - тождественный оператор E = A0. В этой ситуации оба подпространства совпадают со всем пространством.

Совпадение Z0 и Z1 означает, что все дальнейшие прообразы Zk+1 = А−1 Zk будут совпадать друг с другом (почему?) и в конце концов мы доберёмся до прообраза номер r, где r - "настоящий" показатель нильпотентности, минимальная степень, в которой А равно нулю.

Если Z0 и Z1 - разные подпространства, то это изначает, что есть вектор v, такой, что Av ≠ 0 (можно считать, что это один из базисных векторов в Z0), но A2v = 0. Если подскок размерности между Z0 и Z1 больше единицы, то таких векторов (с точностью до линейной зависимости) будет ровно столько же (это размерность фактор-пространства Z1/Z0). Добавим все такие векторы к выбранному раньше базису в Z1.

На следующем шаге мы построим Z2 = А−1 Z1, и снова поимеем альтернативу: если подскока размерности не произойдёт, то дальнейшая возрастающая цепочка подпространств стабилизируется и стабильным "пределом" будет всё пространство. Если подскок произошёл, то некоторое количество векторов из Z2 оператор А превратит в (ненулевые) базисные векторы в Z1.

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

Как описать всю эту иерархию? По построению, у некоторых базисных векторов на первом этаже мы выбрали базисные векторы на втором этаже, которые перейдут под действием А в эти первоэтажные векторы. Далее, у некоторых базисных векторов на втором этаже есть базисные прообразы на третьем. Z2 результате все базисные векторы построенного базиса распадаются на цепочки, спускающиеся сверху вниз:

vr ↦ vr−1 ↦ vr−2 ↦ ... ↦ v1 ↦ 0.
Пример. Рассмотрим знакомый нам оператор D дифференцирования на n-мерном пространстве Fn−1[ x ]. Тогда максимальная степень, которая ещё не равна нулю, есть Dn−1, она превращает все такие полиномы в константы: dim Z0 = 1, и базисом в этом одномерном пространстве является константа f1(x) = 1. Соответственно, прообраз D−1Z0 состоит из полиномов степени ≤ 1 базисом в нём является константа 1, поднявшаяся с первого этажа, и какой-нибудь её прообраз, скажем, f2(x) = x (разумеется, можно было бы взять и f2(x) = x + 1, ничего бы не изменилось). Продолжая в том же духе, мы поднимемся на самый высокий этаж, и добавляемые на каждом этаже базисные полиномы можно выбрать мономиальными, fk(x) = xk−1/(k-1)!. В этом примере все базисные векторы "собрались" в одну-единственную цепочку.

Другой пример. Рассмотрим прямую сумму нескольких пространств полиномов, подобных вышеописанному. Такое пространство состоит из строчек какой-то длины, составленных из полиномов от одной и той же переменной. Разница в том, что ограничение на степень полиномов меняется от позиции к позиции в строке, например, первый элемент в строке обязан быть полиномом степени ≤ 0 (т.е., константой), второй - полиномом степени ≤ 9 (десятимерное пространство) и т.д. Ограничения никак не связаны друг с другом, могут повторяться, иметь пропуски - всё дозволено. Оператор дифференцирования D действует и на этом "гибридном" подпространстве очевидным (почленным) образом. Как выглядит в этом случае базис, построенный выше для случая "строчки длиной единица"?

Не надо быть зоотехником, чтобы понять: подпространства, в которых все элементы, кроме одного, фиксированы, а на этот единственный элемент есть только соответствующее ограничение на степень, инвариантны для D. В каждом таком подпространстве базис состоит из единственной цепочки, вдоль которой D действует как сдвиг по этажу вниз и убивая обитателей самого нижнего этажа (константы). Размерности подпространств Zk, как нетрудно сообразить, будут равны числу позиций в строке, где степень k по иксу ещё разрешена ограничениями задачи.

[Пример из жизни]Самый, наверное, доступный для понимания пример того, что делает нильпотентный оператор - игра в "Морской бой". Оператор стреляет в акваторию 10×10, где находится вражеский флот: линкоры (5 клеточек), крейсера (4 клеточки).... катера (одна клеточка). Каждый выстрел "убийственный" для той клеточки, куда прилетел выстрел, но не обязательно для всего корабля. Если "накрыло" одноклеточный катер, - пипец, катер "убит", потоплен. Но если выстрел поразил линкор - он превращается в крейсер и у него ещё четыре "жизни" осталось (стрелок получает сигнал "ранен", но в нашей упрощённой игре это несущественно, а в "настоящей" игре в морской бой стрелок примерно понимает, как может быть расположен линкор, и дальше бьёт осмысленно, экономя снаряды. В нашей игре нет никаких линкоров, но зато бить два раза по одной клеточке не имеет смысла, поэтому рано или поздно потопит каждый стрелок потопит весь вражеский флот (если только не потеряет свой флот сам: смысл салонной игры - экономия выстрелов, а нам важен только гарантированный конечный результат. Алгоритм выбора базисов есть, собственно, протокол вражеских потерь: мы записываем только удачные попадания, и каждая цепочка базисных векторов состоит из выстрелов, которые последовательно поражали корабль, прежде чем его полностью потопить.

Жорданова форма нильпотентных матриц.
Несмотря на все мои заклинания о том, что правильные слова объясняют математику лучше замысловатых формул, всегда найдутся желающие "выписать ответ". Как выглядит матрица нильпотентного оператора в построенном базисе?

Ответ. Если все базисные вектора собрались в одну цепочку, т.е., в последовательности подпространств

Z1 ⊆ Z2 ⊆ Z3 ⊆  ...  ⊆  Zn−1 ⊆ V

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

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



Каждый такой нуль на самом деле - пограничный столбик, разделяющий два разных блока (контрольный вопрос: сколько и каких блоков есть у матрицы на картинке?). Разумеется, блоки могут идти в произвольном порядке. Нетрудно сообразить, что общее число разных жордановых клеток равно числу разных собственных векторов с нулевым собственным числом. Если единиц нет вовсе, это означает, что все жордановы клетки на самом деле одномерны и сводятся к собственным векторам. Такое бывает в единственном случае, - когда нильпотентный оператор на самом деле тождественно нулевой. Чему тут удивляться? Если единицы могут быть только на единственной наддиагонали, а по факту их и там нет вовсе, значит, все элементы матрицы - нули.

Случай, если оператор А имеет единственное собственное значение λ сводится к нильпотентному заменой А на A − λE. Соответственно, матрица такого оператора имеет главную верхнюю наддиагональ как описано, а на главной диагонали расположено одно и то же число. Если все жордановы клетки одномерны, то все векторы - собственные для А с одним и тем же собственным числом λ. Такие операторы называются скалярными, потому что являются операторами умножения на константу λ.

А что же делать в общем случае?

Что делать в случае, если у оператора А есть два и больше разных собственных значений? Ответ дали ещё римляне: Divide et impera.

Пусть λ - одно из нескольких собственных значений. Рассмотрим разность Bλ = A −λE: по определению, это вырожденный (необратимый) оператор и у него есть ядро, вектор такой, что Bλv = 0. Но мы, обогащённые знакомством с нильпотентными операторами, рассмотрим корневое пространство Vλ, как максимальное подпространство, на котором оператор B = Bλ
нильпотентен. Для этого надо просто рассмотреть степени оператора В и их ядра (нулевые подпространства). Это возрастающая цепочка подпространств Xkλ(ср. выше), и она обязана в какой-то момент стабилизироваться (т.е., рост прекратится). Это "предельное" подпространство и называется корневым.

Совсем не трудно видеть, что корневые подпространства Vλ, соответствующие разным собственным значениям λ, инвариантны, не пересекаются между собой и вместе дают разложение всего пространства в прямую сумму. Проверку этих утверждений я, пожалуй, оставлю въедлому™ читателю в качестве поучительного упражнения.

Поскольку по построению ограничение А на каждое корневое пространство имеет единственное собственное число, мы уже всё про него знаем. Сформулируйте сами, как выглядит матрица оператора в такой жордановой нормальной форме.

Несколько замечаний (будет добавлено, не извольте беспокоиться)
Предположим, все собственные значения оператора попарно различны (и их ровно n штук, кратных там нет). Тогда вся бодяга с жордановой нормальной формой оказывается излишней: оператор имеет ровно n собственных векторов, все они линейно независимы друг с другом (докажите уж, чтоб закрепить навыки), образуют базис в линейном пространстве. В этом базисе оператор имеет диагональную матрицу, проще которой может быть только скалярная матрица. Каков шанс, что в интересующем вас конкретном случае вам таки-придётся разбираться с разными нильпотентами? Ответ: нулевой.

Если считать, что вы взяли квадратную таблицу и наугад заполнили её случайными числами, скажем, из отрезка [0,1], то вероятность получить недиагонализируемую матрицу равна нулю. Более того, очевидно, что если вам случайно не повезло, можно всегда изменить какие-то матричные элементы на сколь угодно малую величину, и корни характеристического момента станут простыми.

Так что, вся возня с исследованием жордановой формы - исключительно повод математикам разогнать скуку, и нильпотентных операторов не существует? Что, и дифференцирования в природе нет? Ну-ну.

Кроме того, есть ещё одно обстоятельство. Математические объекты, описывающие реальный мир, как правило зависят от многих параметров, значения которых могут меняться. Например, рассмотрим многочлен f(x) = x2 − μ, где μ - числовой параметр. При "случайном" злачении μ многочлен имеет два разных корня, которые сливаются в один двукратный корень при μ = 0, что означает, что в однопараметрических семействах появление кратных корней и, соответственно, нетривиальных жордановых клеток просто неизбежно.