- Регистрация
- 23 Август 2023
- Сообщения
- 3 041
- Лучшие ответы
- 0
- Реакции
- 0
- Баллы
- 51
Offline
В этой статье разберем четыре задачи из студенческих олимпиад по математике. Условие везде такое: возвести матрицу в какую-то большую степень. Но вместе с этим мы увидим, что в зависимости от того под каким углом посмотреть на задачу актуальными оказываются самые разные разделы линейной алгебры. Поехали
Задача 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
Задача 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