определитель тёплицевой матрицы

[maxal]

Вычислите определитель следующей тёплицевой матрицы (как функцию от $x$ и натурального числа $n$):

$$\begin{bmatrix} x & 1 & 2 & 3 & \cdots & n-1 & n\\ 1 & x & 1 & 2 & \cdots & n-2 & n-1\\ 2 & 1 & x & 1 & \cdots & n-3 & n-2\\ 3 & 2 & 1 & x & \cdots & n-4 & n-3\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ n-1 & n-2 & n-3 & n-4 & \cdots & x & 1\\ n & n-1 & n-2 & n-3 & \cdots & 1 &x \end{bmatrix}$$

[lel0lel]

$$\frac{1}{4} \left[2 x^n+\left(x-1-\sqrt{1-2 x}\right)^n+\left(x-1+\sqrt{1-2 x}\right)^n+n\cdot \frac{\left(x-1+\sqrt{1-2 x}\right)^n-\left(x-1-\sqrt{1-2 x}\right)^n}{\sqrt{1-2 x}}\right]$$

[maxal]

lel0lel, да. как?

[Dmitriy40]

Простите, а разве определитель матрицы определён для элементов матрицы не любой величины (из $\mathbb{R}$)? Тут же явное условие $x<0.5$. Противоречие. Это первое.

Второе, пусть даже $x<0.5$, проверим подстановкой, определитель матрицы для $n=2, x=0$ равен
$\det \begin{bmatrix} 0 & 1 & 2 \\ 1 & 0 & 1 \\ 2 & 1 & 0 \end{bmatrix} = 4$
По формуле же из сообщения выше получается число
$\dfrac{1}{4}\left [ 0 + (-2)^2 + (0)^2+2\cdot \dfrac{(0)^2-(-2)^2}{1} \right ] = -1$
Снова противоречие.
Но может это артефакт? Проверим на другой матрице, $n=3, x=-1.5$ (чтобы корень извлёкся), определитель равен $-99.9375$ (если верить онлайн калькуляторам), формула же выдаёт $9.53125$. То же самое противоречие.
Для матрицы $n=4, x=-12$ определитель равен $-140800$, по формуле же $16434$. Снова не работает.

И?

[StaticZero]

Dmitriy40, ещё и наивысшая степень многочлена реального определителя на 1 больше, чем предложено lel0lel (ну, я про лидирующий член в скобках, вы поняли)...

[maxal]

Dmitriy40, $n$ в формуле надо заменить на $n+1$, но я не придираюсь.

-- Mon Sep 14, 2020 17:44:24 --

На всякий случай вот как выглядит формула у меня:

$$\frac{(n+1+\sqrt{1-2x})(x-1+\sqrt{1-2x})^{n+1}-(n+1-\sqrt{1-2x})(x-1-\sqrt{1-2x})^{n+1}}{4\sqrt{1-2x}} + \frac{x^{n+1}}2.$$

[nnosipov]

Dmitriy40 в сообщении #1483236 писал(а):

Тут же явное условие $x<0.5$. Противоречие.

Такое же, как и, например, в формуле Бине для чисел Фибоначчи. Т.е. никакого.

-- Вт сен 15, 2020 07:25:19 --

maxal в сообщении #1483234 писал(а):

как?

Судя по форме ответа, составляется рекуррентное соотношение 2-го порядка, которое затем решается?

[Dmitriy40]

maxal
Может я чего-то не понимаю, но чему равен определитель по Вашей формуле для матрицы $n=2, x=5$? Определитель $\det \begin{bmatrix} 5 & 1 & 2 \\ 1 & 5 & 1 \\ 2 & 1 & 5 \end{bmatrix} = 99$, а что выдаёт Ваша формула? И как Вы это посчитаете?
В области $x<0.5$ похоже Ваша формула даёт правильные результаты, тут согласен, хотя одной лишь заменой $n \to n+1$ и не обошлось. Но что делать с областью $x \geqslant 0.5$, её как считать?
Не то чтобы я хоть что-то в этом понимал, но уж ОДЗ то проверить нетрудно. Или Вы для вычислений выходите в комплексные числа, но получаете всегда гарантированно действительный результат? Я даже могу допустить что при раскрытии скобок все радикалы исчезнут, но это лишь значит что преобразования будут не равносильными.

nnosipov
Простите, но в формуле Бине нет корней из отрицательных аргументов (и деления на ноль кстати тоже). А тут есть. И вот это мне непонятно, ибо на мой взгляд это неправомерное сужение области определения.

-- 15.09.2020, 03:53 --

Более того, для $n=2, x=5$ (а вероятно и для других) если формулу рассматривать как функцию от $s=\sqrt{1-2x}$, то она является квадратичной по $s$ и ни при каком значении $s \in \mathbb{R}$ не уходит ниже $166.5$, т.е. никакой модификацией радикала нельзя получить правильное значение $99$.

[maxal]

Dmitriy40 в сообщении #1483244 писал(а):

Может я чего-то не понимаю, но чему равен определитель по Вашей формуле для матрицы $n=2, x=5$? Определитель $\det \begin{bmatrix} 5 & 1 & 2 \\ 1 & 5 & 1 \\ 2 & 1 & 5 \end{bmatrix} = 99$, а что выдаёт Ваша формула? И как Вы это посчитаете?

Я не понимаю, чем именно вам не нравится формула. Вот её реализация на PARI/GP с вычислением вашего примера и значений определителя для $n=1,2,\dots,5$:

? f(n,t=x) = my(r); r=Mod(y,y^2-(1-2*z)); subst( lift( ((n+1+r)*(z-1+r)^(n+1) - (n+1-r)*(z-1-r)^(n+1))/4/r ) + z^(n+1)/2, z, t);
? f(2,5)
%2 = 99
? vector(5,n,f(n))
%3 = [x^2 - 1, x^3 - 6*x + 4, x^4 - 20*x^2 + 32*x - 12, x^5 - 50*x^3 + 140*x^2 - 120*x + 32, x^6 - 105*x^4 + 448*x^3 - 648*x^2 + 384*x - 80]

-- Mon Sep 14, 2020 20:35:00 --

nnosipov в сообщении #1483243 писал(а):

Судя по форме ответа, составляется рекуррентное соотношение 2-го порядка, которое затем решается?

Как это проделать сходу не совсем очевидно. По крайней мере, я на это надеюсь.

[nnosipov]

Dmitriy40 в сообщении #1483244 писал(а):

И вот это мне непонятно

Просто Вы неправильно пользуетесь этой формулой с радикалом $\sqrt{1-2x}$. Это, видите ли, полуфабрикат, который следует упростить, причем символьно (например, средствами компьютерной алгебры). После упрощения получится многочлен.

Вот код на Maple:

> alias(alpha=RootOf(t^2-(1-2*x),t));
> T:=n->evala(((n+1+alpha)*(x-1+alpha)^(n+1)-(n+1-alpha)*(x-1-alpha)^(n+1))/4/alpha+x^(n+1)/2);

И maxal написал то же самое, только на PARI. В общем, здесь рулит компьютерная алгебра.

maxal в сообщении #1483245 писал(а):

Как это проделать сходу не совсем очевидно.

Соглашусь, тем более что я и не пробовал. Собственно, это и есть содержательная часть задачи. (Подумалось, что такая задача могла бы быть в задачниках, где много задач на вычисление определителей. Но, порывшись в задачнике Фаддеева и Соминского, я ее не нашел.)

[maxal]

nnosipov в сообщении #1483246 писал(а):

(Подумалось, что такая задача могла бы быть в задачниках, где много задач на вычисление определителей. Но, порывшись в задачнике Фаддеева и Соминского, я ее не нашел.)

Я тоже не видел её в задачниках, хотя вот вариант с $x=0$ довольно известен - см. A085750.

[nnosipov]

maxal в сообщении #1483248 писал(а):

вариант с $x=0$ довольно известен

То есть, фактически Ваша задача --- это вычисление характеристического многочлена матрицы расстояний.

[lel0lel]

Хорошо, что эта тема заинтересовала участников.
Вчера я начал решать эту задачку. Пытаясь найти рекуррентное соотношение, я переставлял строки и столбцы матрицы, чтобы блоки матрицы были симметричными, это позволяет выразить определитель матрицы через произведение определителей матриц меньшего порядка. На этом пути удаётся факторизовать получающийся в результате вычисления исходного определителя полином, но для определителей меньшего порядка по-прежнему требуется искать рекуррентные соотношения. Также я использовал дополнение Шура исходной матрицы -- этот путь кажется разумным, но, к сожалению, у меня стало заканчиваться свободное время и я решил сделать ставку на то, что последовательность определителей это линейная рекурсия с постоянными коэффициентами. Если это так, то найти рекуррентную формулу очень просто -- нужно составить линейную систему уравнений, число которых больше порядка предполагаемой рекурсии. Например, если мы предполагаем что последовательность определителей $\{D_k\}$ это рекурсия порядка три, то система уравнений для нахождения коэффициентов имеет вид
\begin{gather}\nonumber D_{3}=c_1 D_{2}+c_2 D_{1}+c_3 D_{0},\\ \nonumber D_{4}=c_1 D_{3}+c_2 D_{2}+c_3 D_{1},\\ \nonumber D_{5}=c_1 D_{4}+c_2 D_{3}+c_3 D_{2},\\ \nonumber D_{6}=c_1 D_{5}+c_2 D_{4}+c_3 D_{3},\\ \nonumber \cdots \end{gather}
Уравнений должно быть любое число большее трёх. Если система имеет решение, то вероятно имеем дело с рекурсией третьего порядка, но вообще говоря требуется дополнительная проверка что это действительно так. Если система несовместна, то значит либо порядок рекурсии выше, либо это вообще не есть линейная рекурсия с постоянными коэффициентами.

В своё время я использовал программу в которую можно скопировать последовательность из OEIS, а на выходе получить рекуррентные коэффициенты, ну или не получить ничего если коэффициенты не находятся. Очень удобная вещь и написать её легко. В этой задаче получается следующая формула

$$D_{k+5} - (5 x-4) D_{k+4} + 2 ( 5 x^2- 6 x+2 ) D_{k+3} - 2 x (5 x^2- 6 x+2) D_{k+2} + x^3(5 x-4) D_{k+1} - x^5 D_{k} = 0.$$

Далее как предписывает классическая наука -- решаем характеристическое уравнение, есть кратные корни, находим формулу $n$-го члена последовательности $\{D_k\}$.

Я понимаю, что этот способ не является олимпиадным, зато во многих задачах, когда получить рекуррентную формулу непросто (мне встречались рекурсии 10-го и более высоких порядков), он очень прост и удобен.

Dmitriy40 в сообщении #1483244 писал(а):

Ваша формула даёт правильные результаты, тут согласен, хотя одной лишь заменой $n \to n+1$ и не обошлось

Как раз обошлось лишь одной заменой, сейчас специально перепроверил.

[maxal]

lel0lel в сообщении #1483327 писал(а):

я решил сделать ставку на то, что последовательность определителей это линейная рекурсия с постоянными коэффициентами

Метод хороший, но полученную таким образом формулу нельзя считать доказанной. Другими словами, вы угадали ответ, но не доказали его.

[lel0lel]

Согласен. Нужно доказывать, что найденная формула справедлива для любого $k$, а не только тех, которые использованы в системе, иначе, как вы верно заметили, это угадывание. В качестве примера можно построить интерполяционный полином, который на первой тысяче натуральных чисел ведёт себя как рекурсия второго порядка, а на второй тысяче как рекурсия третьего порядка; ясно, что поиск формулы подобным методом -- занятие бессмысленное. Если бы в некоторой задаче требовалось продолжить загаданную последовательность, то ответ полученный с помощью подобного метода не стоил бы и гроша, как и любой другой ответ. Другое дело если рассматривается простоопределённая последовательность определителей; в этом случае, нахождение рекуррентной формулы, которой удовлетворяют $N$ членов последовательности и $N$ много больше порядка найденной формулы, с большой вероятностью указывает на то, что формула верна для всей последовательности. Понимаю что это не теорема, но попробовать доказать её для объектов типа определитель стоит попробовать. Возможно также, что это вовсе неверное предположение и есть пример, в котором первые тысяча членов некоторой простоопределённой последовательности определителей ведут себя как рекурсия второго порядка, а затем как-то иначе.

Касательно самой задачи: удалось найти её A203993, там приведена рекуррентная формула и формула $n$-го члена.

Можно предложить следующее обобщение исходной задачи: найдите характеристический полином симметричной матрицы $A$ размерности $n\times n$ определённой с помощью $A_{i,j}=|i-j|^p$. В OEIS ответ не гуглится, будет что-то новое. Впрочем, это может выглядеть несколько неуместно -- не решив исходную задачу переходить к угадыванию ответа в другой, нужно дождаться решения по этому вопросу maxal.