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

2025-10-04 в 17:46, admin, рубрики: алгебра, магистратуры, математика, матрицы, олимпиады, ШАД

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

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

Найти

$text{Найти} ,A^{2018}, text{если},, A=begin{pmatrix} 0 & 0 & 1 &0 \0&0&0&1\-1 &0&0&0\0 & -1 &0 &0 end{pmatrix}$

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

$A^2=begin{pmatrix} 0 & 0 & 1 &0 \0&0&0&1\-1 &0&0&0\0 & -1 &0 &0 end{pmatrix}cdotbegin{pmatrix} 0 & 0 & 1 &0 \0&0&0&1\-1 &0&0&0\0 & -1 &0 &0 end{pmatrix}=begin{pmatrix} -1 & 0 & 0 &0 \0&-1&0&0\0&0&-1&0\0 & 0 &0 &-1 end{pmatrix}$

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

$A^{2018}=(A^2)^{1009}=(-E)^{1009}=-E$

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

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

$text{Найти} ,A^{1000}, text{если},, A=begin{pmatrix} -3 & 0 & 0 \0&1&-sqrt3\0 &sqrt3&1 end{pmatrix}$

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

$A=begin{pmatrix} B & 0 \0&C end{pmatrix},,text{где},B=(-3),, C=begin{pmatrix} 1 & -sqrt3 \sqrt3& 1 end{pmatrix}$

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

$A^{1000}=begin{pmatrix} B^{1000} & 0 \0& C^{1000} end{pmatrix}$

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

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

$C=2begin{pmatrix} 1/2 & -sqrt3/2 \sqrt3/2& 1/2 end{pmatrix}=2begin{pmatrix} cosfrac{pi}{3} & -sinfrac{pi}{3} \ sinfrac{pi}{3}& cosfrac{pi}{3} end{pmatrix}$

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

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

$C^{1000}=2^{1000}begin{pmatrix} cosfrac{1000pi}{3} & -sinfrac{1000pi}{3} \ sinfrac{1000pi}{3}& cosfrac{1000pi}{3}end{pmatrix}$

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

$C^{1000}=2^{1000}begin{pmatrix} cosfrac{4pi}{3} & -sinfrac{4pi}{3} \ sinfrac{4pi}{3}& cosfrac{4pi}{3}end{pmatrix}=2^{1000}begin{pmatrix} -1/2 & sqrt3/2 \ -sqrt3/2& -1/2 end{pmatrix}$

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

$A^{1000}=begin{pmatrix} B^{1000} & 0 \0& C^{1000} end{pmatrix}=begin{pmatrix} 3^{1000} & 0 & 0 \0& -2^{999} & sqrt3cdot2^{999}\ 0 &-sqrt3cdot2^{999} & -2^{999} end{pmatrix}$

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

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

$text{Найти} ,A^{100}, text{если},, A=begin{pmatrix} 1 & 2 \2& 1 end{pmatrix}$

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

$det(A-lambda E)=begin{vmatrix} 1-lambda & 2\ 2 & 1-lambda end{vmatrix}=(1-lambda)^2-4=0 ,Leftrightarrow; left[ begin{array}{l} lambda_1=3, \ lambda_2=-1 end{array} right.$

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

$text{Для} ,,lambda_1=3: left( begin{array}{cc|c} -2 & 2 & 0 \ 2 & -2 & 0 end{array} right) ;;Rightarrow;; h_1=begin{pmatrix} 1 \[4pt] 1 end{pmatrix} ,$ $text{Для} ,,lambda_2=-1: left( begin{array}{cc|c} 2 & 2 & 0 \ 2 & 2 & 0 end{array} right) ;;Rightarrow;; h_2=begin{pmatrix} -1 \[4pt] 1 end{pmatrix}$

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

$B=begin{pmatrix} 3 & 0 \0& -1 end{pmatrix}$

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

$B=S^{-1}AS,,,text{где},, S=begin{pmatrix} 1 & -1\ 1 &1 end{pmatrix}$

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

$A=SBS^{-1}$

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

$A^{100}=(SBS^{-1})^{100}=(SBS^{-1})(SBS^{-1})dots(SBS^{-1})(SBS^{-1})$

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

$A^{100}=SB^{100}S^{-1}$

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

$A^{100}=begin{pmatrix}1&-1\1&1end{pmatrix}cdotbegin{pmatrix}3^{100}&0\0&1end{pmatrix}cdotdfrac{1}{2}begin{pmatrix}1&1\-1&1end{pmatrix}=dfrac{1}{2}begin{pmatrix}3^{100}+1&3^{100}-1\3^{100}-1&3^{100}+1end{pmatrix}$

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

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

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

$text{Найти} ,A^{100}, text{если},, A=begin{pmatrix} 1 & 2 & 0 \-3 & -3 &1 \2 & 2& -1 end{pmatrix}$

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

$p(lambda)=det(A-lambda E)=begin{vmatrix} 1-lambda & 2 & 0 \-3 & -3-lambda &1 \2 & 2& -1-lambda end{vmatrix}=-(1+lambda)^3=0$

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

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

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

$A^{100}=(A+E)^3cdottext{(что-то)}+остаток=0cdottext{(что-то)}+остаток=остаток$

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

$x^{100}=(x+1)^3cdot q(x)+ax^2+bx+c$

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

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

$A^{100}=4990A^2+9800A+4851E=begin{pmatrix}-10099&-200& 9900\10200 & 201 & -10000\ -10100 & -200 & 9901end{pmatrix}$

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

$1),text{Найти} ,,A^{101},, text{если} A=begin{pmatrix} -3 & 0 & 0 \0 & -5 &3 \0 & -12& 7 end{pmatrix}\[7pt] 2), Найти lim_{nrightarrowinfty}A^{n}, ,если,, A_n=begin{pmatrix}1 & 2/n & 6/n\ 3/n & 1 & 0\ -1/n& 0& 1end{pmatrix}$

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

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

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

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

Автор: Zhestkov

Источник