04.10.2025 17:46
Zhestkov 16 19000 Источник

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

Задача 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}\cdot\begin{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=2\begin{pmatrix} 1/2 & -\sqrt3/2 \\\sqrt3/2& 1/2 \end{pmatrix}=2\begin{pmatrix} \cos\frac{\pi}{3} & -\sin\frac{\pi}{3} \\ \sin\frac{\pi}{3}& \cos\frac{\pi}{3} \end{pmatrix}

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

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

C^{1000}=2^{1000}\begin{pmatrix} \cos\frac{1000\pi}{3} & -\sin\frac{1000\pi}{3} \\ \sin\frac{1000\pi}{3}& \cos\frac{1000\pi}{3}\end{pmatrix}

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

C^{1000}=2^{1000}\begin{pmatrix} \cos\frac{4\pi}{3} & -\sin\frac{4\pi}{3} \\ \sin\frac{4\pi}{3}& \cos\frac{4\pi}{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} & \sqrt3\cdot2^{999}\\ 0 &-\sqrt3\cdot2^{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&1\end{pmatrix}\cdot\begin{pmatrix}3^{100}&0\\0&1\end{pmatrix}\cdot\dfrac{1}{2}\begin{pmatrix}1&1\\-1&1\end{pmatrix}=\dfrac{1}{2}\begin{pmatrix}3^{100}+1&3^{100}-1\\3^{100}-1&3^{100}+1\end{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, то есть:

p(A)=-(E+A)^3=0 \Rightarrow (E+A)^3=0

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

A^{100}=(A+E)^3\cdot\text{(что-то)}+остаток=0\cdot\text{(что-то)}+остаток=остаток

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

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

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

a=4950,\,b=9800,\,c=4851

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

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

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

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

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

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

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

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

Комментарии (16)


  1. misha_erementchouk
    04.10.2025 19:51
    #28919556

    Техническое. В третьей задаче финальную часть можно сократить, используя спектральное представление

    A = \lambda_1 P_1 + \lambda_2 P_2,

    где

    P_k = \frac{1}{2} h_k h_k^T

    проекторы на собственные подпространства и множитель 1/2 учитывает нормировку собственных векторов, определенных в тексте. Отсюда сразу получаем ответ

    A^{100} = \frac{3^{100}}{2} \left( \begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix} \right) + \frac{(-1)^{100}}{2} \left( \begin{matrix} 1 & -1 \\ -1 & 1 \end{matrix} \right)

    который, разумеется, совпадает с тем, что в тексте.


    1. Zhestkov Автор
      04.10.2025 19:51
      #28919566

      В самом деле, можно и так :) Здорово, спасибо!


  1. rootdefault
    04.10.2025 19:51
    #28919826

    В первой задаче точно нужно возведение в степень после закрывающей скобки матрицы? )) а то сейчас записанное условие немного отличается от того что мы потом решаем ;)


    1. Zhestkov Автор
      04.10.2025 19:51
      #28920000

      Спасибо! Поправил :)


  1. aamonster
    04.10.2025 19:51
    #28920402

    Спасибо. Вроде всё несложное (кроме последней задачки, теорему Гамильтона-Кэли я не помнил, надо будет с листочком бумаги поискать другое решение), но вспомнить студенческие годы приятно :-)


    1. Zhestkov Автор
      04.10.2025 19:51
      #28922204

      Спасибо за обратную связь!


  1. tarlex2001
    04.10.2025 19:51
    #28921474

    У вас опечатка в последней задаче : а = 4950 .

    И зачем так сложно : записываем первых три члена ряда Тейлора функции x^100 в точке x = -1 и сразу получаем остаток :

    1- 100 ( x + 1 ) + 4950 * ( x + 1 ) ^2


    1. Zhestkov Автор
      04.10.2025 19:51
      #28921826

      Спасибо за обратную связь и замеченную опечатку, поправил! Конечно, можно так. Но и тем способом вышло очень быстро, а на ум пришло первым :)


  1. bk_space
    04.10.2025 19:51
    #28923268

    Коршуны налетели, коршуны


  1. KvanTTT
    04.10.2025 19:51
    #28925096

    Забавно, что все эти примеры скорей всего быстро решаются тупым перемножением матриц в системах компьютерной алгебры. 2000 умножений - это должно быть немного.


    1. Timosha_Kulikov
      04.10.2025 19:51
      #28925216

      Ну как бэ, если в лоб перемножать, то сложность О(n^3)


      1. KvanTTT
        04.10.2025 19:51
        #28925856

        Здесь сложность линейная N, т.к. матрицы фиксированного размера (считаем, что умножение одной матрицы на другую происходит за константу).


    1. bk_space
      04.10.2025 19:51
      #28925310

      Речь же не о решениях в лоб, а о подходах к таким расчётам. Если для человека 1000 - запредельное значение, то для систем компьютерной алгебры это число просто станет другим, скажем, 10^12. Однако сам подход к решению таких задач не поменяется, лишь константы будут другие.

      Калькулятор позволит легко сложить 20 чисел, сформированных по некоторому правилу, в лоб, но это не делает формулу суммы арифметической прогрессии бесполезной)


      1. KvanTTT
        04.10.2025 19:51
        #28925862

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


    1. fshp
      04.10.2025 19:51
      #28926396

      Для возведения в степень 2000 потребуется 15 умножений.


      1. lea
        04.10.2025 19:51
        #28927360

        потребуется 15 умножений

        13 используя addition chain exponentiation (1,2,4,5,10,20,40,50,100,200,400,500,1000,2000)