Готовимся к экзамену в ШАД: разбор задач по линейной алгебре последних лет / Хабр

Автор статьи: Канунников Андрей, к. ф.-м. н., преподаватель ШАДХелпер.

Тематика задач на вступительных экзаменах в Школу Анализа Данных (ШАД) Яндекса год от года несколько меняется. Отчасти это связано с появившейся возможностью использовать СhatGPT. Из важных изменений: в последние год-два стали появляться задачи на жорданову нормальную форму, хотя в программу экзамена она не входит (когда-то составленные программы редко обновляют). Мы разберём одну из таких задач с письменного экзамена. Кстати, на устном собеседовании встречались вопросы типа: сколько может существовать корней из данной матрицы , то есть решений уравнения . Или при каком условии хотя бы один корень можно извлечь. Тут жорданова форма очень сильно поможет. Для решения задач, как правило, достаточно формулировки основной теоремы. А если вы хотите понять логически простой способ найти жорданов базис, порекомендую учебное пособие Кряквина. Изложенный там метод мне показался гораздо проще, чем доказательства из известных университетских учебников.

Приступим к разбор задач письменных экзаменов.

E. В царстве-государстве (2025)

В три-четырнадцать-пятнадцатом царстве в девяноста-два-и-шесть государстве у Царя Симвалта росла дочь-красавица — Азалептина. Чтобы сосватать дочь за самого достойного принца, он спрятал по всему королевству несколько сундуков с сокровищами.
В каждом сундуке лежит по линейному оператору

$\varphi\colon \mathbb{R}^3 \to \mathbb{R}^3,$

такому, что многочлен

является зануляющим для него.
Кроме того, известно, что у всех операторов разная ЖНФ и для каждого из них найдётся свой вектор $v \in \mathbb{R}^3$ такой, что линейная оболочка

$\langle v, \varphi(v), \varphi^2(v), \ldots \rangle$

совпадает со всем пространством $\mathbb{R}^3$ .

Он выдаст Азалептину замуж только за того принца, который отыщет все сундуки с сокровищами. Царевич Анафронилон знает, что царь хитрый и дочь просто так не отдаст, даже если ты принесёшь ему все матрицы из всех сундуков. Царь обязательно будет утверждать, что ты нашёл не все сокровища. Поэтому надо не просто найти все возможные ЖНФ для таких операторов, а ещё и доказать, что других нет. Помогите царевичу Анафронилону решить такую нелёгкую задачу, а то уж больно ему хочется жениться на Азалептине.

В качестве ответа введите количество сундуков или , если задача не имеет решения.

Шутливые и, увы, длинные формулировки вообще характерны для задач ШАД последних лет. Для справки:

а) Номер царства восходит к первым цифрам числа $\pi=3,1415926\ldots$

б) Имя Азалептина имеет что-то общее с препаратом азалептин, который применяется для лечения шизофрении. В общем, в тему задачи.

в) ЖНФ — жорданова нормальная форма.

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

Нам нужно найти жордановы нормальные формы всевозможных матриц со следующими свойствами:

(1) $A\in \text{M}_3(\mathbb{R})$ ;

(2) для данного многочлена ;

(3) $\exists X\in\mathbb{R}^3\;\;\langle X,AX,A^2X,\ldots\rangle=\mathbb{R}^3$ .

Подчеркнём, что ЖНФ вещественной матрицы может быть комплексной.

Решение

Собственные значения любой такой матрицы содержатся среди корней данного многочлена : $\varepsilon,\overline{\varepsilon},1,2,-1$ , где $\varepsilon=e^{2\pi i/3}$ . При этом значение может иметь (алгебраическую) кратность как 1, так и 2, а остальные значения — корни кратности 1.

Так как — вещественная матрица, то комплексно-сопряжённые числа $\lambda$ и $\overline{\lambda}$ одновременно являются или не являются её собственными значениями.

Остаётся понять смысл условия (3). Подпространство вида $\langle X,AX,A^2X,\ldots\rangle$ называется циклическим, а вектор — циклическим вектором этого подпространства. Когда, спрашивается, существует циклический вектор для всего пространства? Поясним идею на двух примерах.

1) Если — скалярная матрица, то циклического вектора, очевидно, нет, так как любой ненулевой вектор порождает одномерное подпространство.

2) Пусть матрица — диагональная с тремя разными собственными (вещественными) значениями $\lambda_1,\lambda_2,\lambda_3$ и $Ae_i=\lambda_i e_i$ (). Считая векторами стандатного базиса, заключаем, что циклическим вектором является, например, их сумма , поскольку

$\lambda_1,\lambda_2,\lambda_3)^t, (\lambda_1^2,\lambda_2^2,\lambda_3^3)^t\rangle=\mathbb{R}^3.$

Последнее равенство верно, так как указанная линейная оболочка трёхмерна: векторы линейно независимы как столбцы определителя Вандермонда.

Вообще, используя теорему о корневом разложении, несложно показать, что условие (3) равносильно следующему условию:

(4) для каждого собственного значения $\lambda$ матрицы существует ровно одна жорданова клетка со значением $\lambda$ .

В самом деле, пусть — циклический вектор из условия (3). Его проекция на каждое корневое подпространство является циклическим вектором этого подпространства, а это и значит, что корневое подпространство циклическое и задаётся одной жордановой клеткой. Итак, из (3) следует (4). Обратно, если выполнено (4), то в качестве можно взять сумму корневых векторов максимальной высоты, взятых по одному из каждого корневого подпространства, причём в случае комплексно-сопряжённых собственных чисел следует брать комплексно-сопряжённые корневые векторы (чтобы был вещественным).

Теперь всё готово для перебора случаев.

Случай 1. В ЖНФ матрицы есть жорданова клетка размера . Тогда ЖНФ имеет вид

$\begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & \lambda\end{pmatrix}, \text{ где } \lambda\in \{1,2\}.$

Таких матриц две.

Случай 2. ЖНФ матрицы диагональная. Если $\varepsilon$ — собственное значение, то ЖНФ имеет вид

$\begin{pmatrix} \varepsilon & 0 & 0\\ 0 & \overline{\varepsilon} & 0 \\ 0 & 0 & \lambda \end{pmatrix}, \text{ где } \lambda\in \{1,2,-1\}$

— три матрицы. Если $\varepsilon$ не входит в спектр, то ЖНФ есть

$\begin{pmatrix} 1 & 0 & 0\\ 0 & 2 & 0 \\ 0 & 0 & -1\end{pmatrix}.$

Итого, 6 возможных ЖНФ.

Ответ: 6.

F. Три диагонали (2025)

Найдите количество неотрицательных собственных значений матрицы размером 2025 на 2025 следующего вида:

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

Решение

Фактически требуется найти сигнатуру квадратичной формы с данной матрицей. Напомним, это пара положительного и отрицательного индекса инерции. Ответом является число . Пусть — ограничение формы на подпространство $\langle e_2,\ldots,e_{2025}\rangle$ . задаётся матрицей, полученной из данной вычёркиванием первой строки и первого столбца. В перенумерованном базисе

$e_2,e_{76},e_{150},e_{224},\ldots,e_3,e_{77},e_{151},e_{225},\ldots$

форма задаётся блочно-диагональной матрицей, где каждый блок имеет вид

$B_n=\begin{pmatrix} 2 & -1 & 0 & \ldots & 0 & 0 \\ -1 & 2 & -1 & \ldots & 0 & 0 \\0 & -1 & 2 & \ldots & 0 & 0 \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & \ldots & 2 & -1 \\0 & 0 & 0 & \ldots & -1 & 2\end{pmatrix}$

некоторого размера (размеры блоков могут отличаться на 1). Но матрица положительно определена по критерию Сильвестра. Действительно, раскладывая определитель по первой строке, легко получить рекуррентное соотношение

$|B_n|=2|B_{n-1}|-|B_{n-2}| \;\;\Longleftrightarrow\;\; |B_n|-|B_{n-1}|=|B_{n-1}|-|B_{n-2}|,$

то есть — арифметическая прогрессия. Из начальных членов и получаем, что .

Итак, форма положительно определена. Это значит, что положительный индекс инерции исходной формы не меньше 2024, так как — это максимальная размерность подпространства, на котором положительно определена. Но поскольку $Q(e_1,e_1)=a_{11}=-1$ , то отрицательный индекс инерции не меньше 1. Следовательно, и .

Ответ: .

E. Алгебраично (2024).

Даны матрицы $A\in \text{M}_{n\times r}(\mathbb{R})$ , $B\in \text{M}_{m\times r}(\mathbb{R})$ , $C\in \text{M}_{n\times m}(\mathbb{R})$ , причём $A^\textsf{T} A=B^\textsf{T} B=E$ . Среди матриц $X\in \text{M}_{n\times m}(\mathbb{R})$ , таких, что

$\Im X\subseteq \Im A,\quad \Im (X^\textsf{T})\subseteq \Im B,\;\quad \sum_{i,j} X_{ij}^2=1,$

найдите такую, для которой сумма $\sum_{i,j}X_{ij}C_{ij}$ максимальна.

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

Прежде всего отметим, что образ матрицы — это образ линейного отображения, заданного этой матрицей, то есть линейная оболочка столбцов матрицы.

Решение

Логично начать со случая квадратных матриц: , тем более что численный ответ от нас хотят именно в таком случае. Легко видеть, что тогда матрицы и обратимые, поэтому условия $\Im X\subseteq A$ и $\Im(X^\textsf{T})\subseteq \Im B$ выполнены автоматически. Тем самым, при фиксированной матрице $C\in \text{M}_n(\mathbb{R})$ максимизировать скалярное произведение

$\sum_{i,j}X_{ij}C_{ij}=(X,C)=\text{tr}(X^\textsf{T} C)$

среди матриц единичной длины. Геометрически ясно, что в качестве следует взять отнормированную матрицу , то есть $X=C/\lVert C\rVert$ , так как скалярное произведение — это произведение длин векторов на косинус углам между ними, причём на длины мы влиять не можем, а косинус можем сделать равным 1. Формально это всё обосновывается с помощью неравенства Коши-Буняковского (которое и позволяет корректно определить угол), в данном случае принимающего вид:

$|(X,C)|\leq \lVert X\rVert \lVert C\rVert.$

При этом равенство достигается в точности тогда, когда и пропорциональны, причём чтобы убрать модуль в левой части, коэффициент пропорциональности должен быть положительным. Чтобы была единичной длины, этот коэффициент должен быть равен $1/\lVert C\rVert$ , если только $C\ne 0$ . В тривиальном случае ясно, что — любая матрица длины 1.

Конкретно в случае и получаем
$X=\dfrac 12 E$ , откуда $\text{tr} X+\det X=2+\dfrac{1}{16}=2,0625$ .

Теперь решим задачу в общем виде.

$\Im X\subseteq \Im A \iff \exists Y\in \text{M}_{r\times m}(\mathbb{R})\;X=AY$ .
$\Rightarrow$ Столбцы $X_1,\ldots,X_m$ матрицы имеют вид $AY_1,\ldots,AY_m$ для некоторых столбцов $Y_1,\ldots,Y_m\in \mathbb{R}^n$ . Отсюда для матрицы $Y=(Y_1\ldots Y_m)$ . $\Leftarrow$ Очевидно.
$X=AY \Rightarrow A^\textsf{T} X=A^\textsf{T} AY=Y\Rightarrow X=AY=AA^\textsf{T} X$ .
Аналогично, из условия $\Im(X^\textsf{T}) \subseteq \Im B$ получаем, что $X=XBB^\textsf{T}$ .
Окончательно $X=AA^\textsf{T} XBB^\textsf{T}$ . Обозначим $AA^\textsf{T} =P$ , $BB^\textsf{T} =Q$ . Это матрицы ортогональных проекторов, так как $P^2=P=P^\textsf{T}$ и $Q^2=Q=Q^\textsf{T}$ .
Следовательно, подпространство