Готовимся к экзамену в ШАД: разбор задач по линейной алгебре последних лет
Автор статьи: Канунников Андрей, к. ф.-м. н., преподаватель ШАДХелпер.
Тематика задач на вступительных экзаменах в Школу Анализа Данных (ШАД) Яндекса год от года несколько меняется. Отчасти это связано с появившейся возможностью использовать СhatGPT. Из важных изменений: в последние год-два стали появляться задачи на жорданову нормальную форму, хотя в программу экзамена она не входит (когда-то составленные программы редко обновляют). Мы разберём одну из таких задач с письменного экзамена. Кстати, на устном собеседовании встречались вопросы типа: сколько может существовать корней из данной матрицы
Приступим к разбор задач письменных экзаменов.
E. В царстве-государстве (2025)
В три-четырнадцать-пятнадцатом царстве в девяноста-два-и-шесть государстве у Царя Симвалта росла дочь-красавица — Азалептина. Чтобы сосватать дочь за самого достойного принца, он спрятал по всему королевству несколько сундуков с сокровищами.
В каждом сундуке лежит по линейному оператору
такому, что многочлен
является зануляющим для него.
Кроме того, известно, что у всех операторов разная ЖНФ и для каждого из них найдётся свой вектор
совпадает со всем пространством
Он выдаст Азалептину замуж только за того принца, который отыщет все сундуки с сокровищами. Царевич Анафронилон знает, что царь хитрый и дочь просто так не отдаст, даже если ты принесёшь ему все матрицы из всех сундуков. Царь обязательно будет утверждать, что ты нашёл не все сокровища. Поэтому надо не просто найти все возможные ЖНФ для таких операторов, а ещё и доказать, что других нет. Помогите царевичу Анафронилону решить такую нелёгкую задачу, а то уж больно ему хочется жениться на Азалептине.
В качестве ответа введите количество сундуков или
Шутливые и, увы, длинные формулировки вообще характерны для задач ШАД последних лет. Для справки:
а) Номер царства восходит к первым цифрам числа
б) Имя Азалептина имеет что-то общее с препаратом азалептин, который применяется для лечения шизофрении. В общем, в тему задачи.
в) ЖНФ — жорданова нормальная форма.
Оценив юмор авторов, переведём задачу с поэтического языка на прозаический, сугубо математический.
Нам нужно найти жордановы нормальные формы всевозможных матриц
(1)
(2)
(3)
Подчеркнём, что ЖНФ вещественной матрицы может быть комплексной.
Решение
Собственные значения любой такой матрицы может иметь (алгебраическую) кратность как 1, так и 2, а остальные значения — корни кратности 1.
Так как
Остаётся понять смысл условия (3). Подпространство вида
1) Если
2) Пусть матрица
Последнее равенство верно, так как указанная линейная оболочка трёхмерна: векторы линейно независимы как столбцы определителя Вандермонда.
Вообще, используя теорему о корневом разложении, несложно показать, что условие (3) равносильно следующему условию:
(4) для каждого собственного значения
В самом деле, пусть
Теперь всё готово для перебора случаев.
Случай 1. В ЖНФ матрицы
Таких матриц две.
Случай 2. ЖНФ матрицы
— три матрицы. Если
Итого, 6 возможных ЖНФ.
Ответ: 6.
F. Три диагонали (2025)
Найдите количество неотрицательных собственных значений матрицы размером 2025 на 2025 следующего вида:
у которой заполнено три диагонали (нулевая, семьдесят четвёртая и минус семьдесят четвёртая), и в первой строке и первом столбце находится по 73 единицы. Все остальные элементы матрицы нулевые.
Решение
Фактически требуется найти сигнатуру квадратичной формы
форма
некоторого размера
то есть
Итак, форма
Ответ:
E. Алгебраично (2024).
Даны матрицы
найдите такую, для которой сумма
Решите задачу в общем виде, а также укажите сумму следа и определителя искомой матрицы в случае, когда
Прежде всего отметим, что образ матрицы — это образ линейного отображения, заданного этой матрицей, то есть линейная оболочка столбцов матрицы.
Решение
Логично начать со случая квадратных матриц:
среди матриц
При этом равенство достигается в точности тогда, когда
Конкретно в случае
Теперь решим задачу в общем виде.
. Столбцы матрицы имеют вид для некоторых столбцов . Отсюда для матрицы . Очевидно. . Аналогично, из условия
получаем, что . Окончательно
. Обозначим , . Это матрицы ортогональных проекторов, так как и . Следовательно, подпространство
имеет вид
причём отображение
является ортогональным проектором с образом
6. Скалярное произведение
не изменится, если
и равенство достигается в точности тогда, когда:
Ответ: