Линейная алгебра: четыре разных подхода к одной задаче

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

Задача 1 (Олимпиада УРФУ)

Найти

Что здесь делать? Вспомнить, что у самурая есть только путь. Давайте попробуем хотя бы разок умножить матрицу А саму на себя

Получилась матрица -Е! Таким образом

Оказалось довольно просто, всего за один шаг нащупали закономерность и сразу получили ответ

Задача 2 (Олимпиада Я-Профессионал)

Здесь уже предыдущий трюк так легко не пройдет (хотя попытаться можно, но цепочка здесь будет подлиннее). Попробуем подойти немного иначе. Для начала, скажем, что матрица A – блочно-диагональная:

по свойству умножения матриц:

С левым верхним элементом все понятно – будет три в тысячной, а правее и ниже окажутся нули. Остается возвести матрицу C в тысячную степень

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

И конечно же, перед нами матрица поворота. В нашем случае это поворот на угол π/3.

А что в этом смысле значит возведение в тысячную степень? Это матрица поворота, повторённого тысячу раз, говоря строго – матрица композиции. Получается, что поворот наберется на угол аж 1000π/3

Но это ведь то же самое, что поворот на угол 4π/3. Подставляя этот угол в матрицу поворота, получаем:

Остается собрать ответ:

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

Задача 3 (Олимпиада Сколтех)

В отличие от предыдущей задачи здесь не так легко считывается геометрический смысл. Но это просто повод найти подходящий базис! Мы снова подойдем к матрице из условия как к матрице преобразования и найдем собственные значения и вектора этого преобразования

Ищем собственные вектора:

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

Новая матрица связана с исходной известным соотношением, где S – матрица перехода к новому базису, то есть просто матрица, составленная из собственных векторов:

Отсюда легко выражается интересующая нас матрица A:

И давайте теперь попробуем в таком виде возвести матрицу А в сотую степень. Распишем степень в произведение, и что мы видим? 

Матрица S и обратная к ней внутри сокращаются, будучи взаимно обратными. Остается вот такое выражение:

Матрица B – диагональная, возвести ее в сотую степень – дело проще простого: будет тройка в сотой степени и единичка. Остается найти матрицу, обратную к S (проверку оставлю желающим) и записать ответ:

И немного рефлексии и сути. Если упрощать до бытового уровня то выходит примерно так. Было сложно работать с матрицей в таком виде. Поэтому мы перешли в удобный нам базис, матрица в нем распрекрасная – диагональная, в степень возвелась устно. А затем мы просто вернулись к исходному базису и получили ответ. Здесь тоже легко придать задаче геометрический контекст. Преобразование задает растяжение в три раза вдоль вектора с координатами (1, 1) и отражение относительно перпендикулярного ему вектора (-1, 1). Кто хорошо помнит линейную алгебру, могут вспомнить, что такие преобразования называются самосопряженными

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

Задача 4 (Олимпиада ИТМО)

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

Единственное собственное значение (алгебраической кратности 3) равно минус единице, собственных векторов на базис точно не наберем

Но характеристический многочлен это уже немало! Тут нам приходит на помощь теорема Гамильтона–Кэли: характеристический многочлен является аннулирующим и для самой матрицы A, то есть:

И это здорово! Мы можем теперь представить сотую степень нашей матрицы так:

Все что остается это найти остаток (степень его будет не больше второй). Для удобства перепишем в терминах многочленов

От ответа нас отделяет нахождение коэффициентов a, b, c. Можно действовать так: подставить -1 сначала в исходное равенство, затем в дифференцированное равенство (тоже ведь должно соблюдаться равенство), затем в еще один раз продифференцированное. Так найдется:

Возвращаясь к матрицам (и после нудных вычислений):

Конечно, четыре задачи, которые я разобрал не исчерпывают весь спектр идей при решении подобных задач. Можно встретить здесь и жорданову форму и даже использование… бинома Ньютона! Вот упражнения на подумать (еще больше олимпиадных задач можно найти в моем сборнике, он доступен здесь):

Тем не менее, каждая из разобранных нами задач — напоминание, что линейная алгебра – не про механические действия, а про поиск подходящей точки зрения

Эти и многие другие задачи я подробно разбираю на своем курсе подготовки к ШАД (Школе Анализа Данных) Яндекса. Курс отлично (и где-то даже в большей степени) подойдет и для подготовки к престижным магистратурам и другим похожим образовательным программам. В прошлой статье я уже рассказывал, как самостоятельно выстроить свою подготовку, там же подробно описал как устроен мой курс, сейчас (октябрь/ноябрь) у нас стартует уже восьмой поток

Спасибо, что дочитали! Желаю большой радости познания! 🙂

Автор статьи: Сергей Жестков, ex-преподаватель МФТИ, OTUS; основатель курсов по математике Zhestkov University. Для связи: Телеграм @s_zhestkov

Источник: habr.com