Определитель вроде Вандермонда

Ian · Сообщение **Ian** » 29 апр 2020, 07:37

Пусть

x_i,i=1,...n произвольные действительные числа. Определим элементы матрицы nxn

A_{ji}=\cos(jx_i)
Чему равен определитель матрицы А?
Так как

\cos(jx) полином степени j от

\cos x,то весь определитель - полином степени

jn(n+1)/2 от

\cos(x_i),i=1,...n антисимметричный, то есть меняющий знак при нечетной перестановке чисел

x_i и не меняющийся при четной. Отсюда

n(n-1)/2 сомножителей в этом многочлене известны

\prod_{i\ne j} (\cos x_i-\cos x_j) и остается один сомножитель степени n, симметричный, значит выражающийся через симметричные полиномы от

\cos(x_i),i=1,...n, то есть через коэффициенты по t уравнения

\prod_{i=1}^n (t-\cos x_i)=0. Только выяснить как и доказать

zykov · Сообщение **zykov** » 29 апр 2020, 11:26

Ian писал(а):Source of the post Так как cos(jx) полином степени j от cosx,

Да, это полиномы Чебышева первого рода: $T_n(y)=\cos(n \arccos y)$ .
Если $y_i=\cos x_i$ , то $A_{ij}=T_j(y_i)$ .
Вот например:
$n=2$

: $\det A=( y_2-y_1) ( 2 y_1 y_2+1)$
$n=3$

: $\det A=4(y_2-y_1)(y_3-y_1)(y_3-y_2)(2 y_1 y_2 y_3+y_3+y_2+y_1)$
$n=4$

: $\det A=8(y_2-y_1)(y_3-y_1)(y_3-y_2)(y_4-y_1)(y_4-y_2)(y_4-y_3) \times$
$\times (8 y_1 y_2 y_3 y_4+4 y_3 y_4+4 y_2 y_4+4 y_1 y_4+4 y_2 y_3+4 y_1 y_3+4 y_1 y_2+3)$

Ian · Сообщение **Ian** » 29 апр 2020, 11:41

А как считали для n=4? Что-то Вы быстро, вот у меня лежит расчет этого определителя на 10ти страницах. Хотите через файлообменник передам, там рукописно много мег Но результаты совпали так что респект

zykov · Сообщение **zykov** » 29 апр 2020, 11:50

Ian писал(а):Source of the post А как считали для n=4?

Да за меня Maxima считала.
Задал матрицу "m4" руками с полиномами Чебышева. А там команда "determinant(m4),factor" выдаёт это выражение.

Ian · Сообщение **Ian** » 29 апр 2020, 11:57

А для 5ти?
Если обозначить

P(t)=\prod_{i=1}^n (t-\cos x_i)=0, то это довольно близко к P(-1/2) Почему-то)
Ой. еще ближе к

2^{n-1}(P(0,5)+P(-0,5))

zykov · Сообщение **zykov** » 29 апр 2020, 11:59

Вобщем всё это похоже на детерминант Вандермонда.
Только там с 0-ой степени начинается, а у Вас с 1-ой.
Если у Вас тоже сделать с 0-ой степени - $\cos 0=1$ , то тоже будет детерминант Вандермонда умноженный на $2^k$

, где

равно произведению старших коэффициентов в полиномах Чебышева. Т.е. $k=(n-1)(n-2)/2$

.
А Ваш детерминант - это один из миноров этого детерминанта (минор при последней "1" в первом столбце).

Ian · Сообщение **Ian** » 29 апр 2020, 12:03

Да при

x_1=0 хоть бы получить. И он не мой)

zykov · Сообщение **zykov** » 29 апр 2020, 12:13

Если $A_{ij}=\cos(jx_i)$ , где $j=0..n-1$

, то $\det A=2^{(n-1)(n-2)/2} \prod_{1\leq i<j\leq n} (\cos x_j - \cos x_i)$ .

Ian · Сообщение **Ian** » 29 апр 2020, 13:08

Но это совсем не то что будет при

x_1=0. Красиво и просто, но чем поможет

zykov · Сообщение **zykov** » 29 апр 2020, 16:40

Если мы начинаем с $T_0$

, то получается определитель Вандермонда, потому что мы можем привести матрицу к матрице Вандермонда.
Первая строка и так везде 1. Вторая строка и так везде $y_i$

. В третьей строке многчлен второй степени. Но мы можем к ней добавить первую строку (операция не меняет определитель), остается только $2y_i^2$

.
И так далее, в каждой строке от многочлена останется только старшее слагаемое $2^{j-2}y_i^{j-1}$ . Отсюда и определитель равен определителю Вандермонда умноженному на $2^k$

.

Если мы начинаем с $T_1$

, то в нечётных строках мы так же можем привести многочлен к такому же виду - только страшее слагаемое.
В чётных строках мы тоже сможем занулить почти все слагаемые. Но кроме старшего слагаемого останется ещё нулевой порядок (во второй строке "-1", в четвертой "-3", в шестой "-10", в восьмой "-35" и т.д.)
Остается только всё это посчитать...

Ian · Сообщение **Ian** » 29 апр 2020, 17:41

А если например для n=4 положить

y_i равным корням 4-й степени из 3 (четырем разным комплексным), что это нам скажет о значении искомого сомножителя. Ну точнее не из 3 а из того, что обращает строчку в 0 -константа находится

zykov · Сообщение **zykov** » 29 апр 2020, 21:26

А откуда взялась задача?
Может всё-таки должно быть $j=0..n-1$

, а не

?

Ian · Сообщение **Ian** » 30 апр 2020, 00:23

: T.png (87.74 KiB) 28250 просмотра

У последней системы надо доказать существование положительного решения. И у подобных. Для этого главный определитель хорошо бы иметь явно.

zykov · Сообщение **zykov** » 30 апр 2020, 10:17

Там вроде более конкретная матрица возникает $A_{ji}=\cos(x \cdot j \cdot (2i+1))$ .

zykov · Сообщение **zykov** » 01 май 2020, 10:04

Честно говоря, не вижу как формула для определителя поможет доказать положительность решений линейной системы.

Попробовал посчитать - действительно для $n=1..1000$

и

решения получаются положительные.
Но оказалось, что любой $x$

туда не подставить - это просто неверно. Там должен быть именно такой $q$

( $x=2\pi n/q$ ). Если например вместо $q$

подставить $q+1$

, то возникают отрицательные решения при $n=1$

. А если подставить $q+3$

, то и при $n=2$

тоже будут отрицательные.

zykov · Сообщение **zykov** » 01 май 2020, 14:50

Вообще это преобразование похоже на Discrete cosine transform (DCT-II).
Только в фазе есть дополнительный множитель $k(n,p)=\frac{4 n p}{2 n ( p+1) +1}$ , который меняется в пределах от $8/7$

до

(не доходя до $2$

).

zykov · Сообщение **zykov** » 01 май 2020, 16:39

При больших $n$

и

решение выглядит примерно так:
$\gamma_k = \frac{2}{p-5} (1+0.3597 \; \cos \frac{\pi k}{p}-\cos \frac{2\pi k}{p}-0.3308 \; \cos \frac{3\pi k}{p}-0.0209 \; \cos \frac{5\pi k}{p})$
Есть и другие гармоники (в основном нечётные), но с меньшим весом.
Эта аппроксимация в целом положительная. Только в конце немного заходит в минус.
Наверно неравенство при $n$

и

более какого-то порога можно дожать такми путём, выстраивая цепочку неравенств. Правда для $k$

близких к

нужен будет специальный подход.

Есть кстати ещё гипотеза, что может неравенство и неверно.
Вычислительно получается при $n=10^6$

и

, что в конце 20 отрицательных значений (доходит до $-3.5 \cdot 10^{-9}$ ).
Может это просто вычислительная ошибка, а может и само значение отрицательное.
Стоило бы присмотрется аналитически к случаю $n=\infty$ , $p$

большое,

близко к

.

zykov · Сообщение **zykov** » 01 май 2020, 17:08

Там видимо дело в том, что при больших $n$

или при больших $p$

матрица приближается к сингулярной. Отсюда видимо вычислительные ошибки.
Так что случай $n=\infty$ не подходит. Там матрица вырожденная.
Например при $n=\infty$ и $p=3$

будет $A=\begin{pmatrix} -\frac 1 {\sqrt 2} & -\frac 1 {\sqrt 2} \\ 0 & 0 \\ \end{pmatrix}$ .

zykov · Сообщение **zykov** » 07 май 2020, 16:38

По поводу исходного вопроса про определитель матрицы, то у мена такой реультат.

Сначала (как я уже писал) делаем переходим к новой переменной $y_i=\cos x_i$ , тогда $A_{ij}=T_j(y_i)$ .
Где $T_j$

- полиномы Чебышева первого рода.

Если в матрице к одному столбцу добавить другой столбец (с любым множителем), то определитель матрицы не изменится. Таким образом в столбцах можно занулить все слагаемые, кроме самого старшего порядка и нулевого порядка. Например если к столбцу с кубическими многочленами добавить столбец с линейными многочленами умноженный на 3, то там останется только $4x^3$

. А если к столбцу с многочленами 4-ой степени добавить столбец с квадратными многочленами умноженный на 4, то там останется только $8x^4-3$

. Вобщем для нечётных остается только старшее слагаемое, для чётных будет два слагаемых - старшее и нулевой порядок.

Т.е. будет $\det A = \det B$ , где будет матрица $B_{ij}=2^{j-1} y_i^j - d_j$ .
Для нечётных $j$

будет

.
Для чётных $j$

можно определить $d_j$

рекурсивно через предыдущие $d_j$

и коэффициенты полиномов Чебышева.
Для $j=2, 4, 6, 8$

будет

.
Для коэффициентов полиномов Чебышева есть прямая формула через факториалы.
Таким образом для чётных $j$

можно тоже получить прямую формулу $d_j=C_{j-1}^{j/2}$ в виде биномиального коэффициента.

Если какой-то столбец в матрице разлагается на сумму (у нас это сумма старшего слагаемого и нулевого порядка), то определитель матрицы равен сумме определителей для матрицы с первым слагаемым и со вторым слагаемым. Т.е. $\det B$ можно предстваить как сумму определителей нескольких матриц, где в каждом столбце только одно слагаемое. Если количество столбцов с чётными многочленами было $n_{even}$ , то количество матриц будет $2^{n_{even}}$ . Но если матрица содержит более одного столбца нулевого порядка, то её определитель просто равен нулю. Значит останется одно слагаемое, где нет столбцов нулевого порядка, и $n_{even}$ слагаемых, где на месте одного из столбцов с чётным многочленом стоит столбец нулевого порядка.

Обозначим как $v$

определитель Вандермонда $v=\prod_{1\leq i<j\leq n} (y_j - y_i)$ .
Обозначим единичные симметричные однородные многочлены порядка $i$

от

как

.
Например
$$s_0=1$$

равен сумме произведений всех возможных выборок размера $2$

из

. Например при $n=3$

будет

.
И так далее. В конце будет $s_n=y_1 y_2 ... y_n$

.

Ещё обозначим $k=n(n-1)/2$

, так что произведение старших коэффициентов первых $n$

многочленов Чебышева равно $2^k$

.

Первая матрица (которая без столбцов нулевого порядка) - это почти матрица Вандермонда, только начинается с первого порядка, а не с нулевого. И ещё столбцы имеют множители равные старшим коэффициентам многочленов Чебышева. Все эти коэффициенты можно вынести из определителя - получится множитель равный произведению этих коэффициентов. Так же из каждой строки можно вынести $y_i$

. Тогда останется только матрица Вандермонда (начинающаяся с нулевого порядка).
Таким образом определитель первой матрицы равен $2^k v s_n$

.

Остальные матрицы такие же, как и первая, только для чётного $j$

вместо столбца порядка $j$

будет столбец нулевого порядка не со старшим коэффициентом полинома Чебышева, а с коэффициентом $d_j$

.
Если все коэффициенты вынести из определителя, то получится множитель $C_{j-1}^{j/2} \frac{2^k}{2^{j-1}}$ .
Если оставшийся единичный столбец нулевого порядка переставить в начало, то получится почти матрица Вандермонда. Она начинается с нулевого порядка, но порядок $j$

пропущен. Вместо него идёт порядок $j+1$

и далее порядки идут по очереди до $n$

.
Определитель этой матрицы равен $v s_{n-j}$ .
Отсюда кстати видно, что определитель первой матрицы соответствовал $j=0$

, что логично, так как там как раз был пропущен столбец нулевого порядка.

Вобщем в итоге ответ такой:
$\det A = v(2^k s_n + \sum_{0 < j \leq n/2} 2^{k+1-2j} C_{2j-1}^{j} s_{n-2j})$

zykov · Сообщение **zykov** » 07 май 2020, 16:56

Например
при $n=2$

будет $\det A = v(2^1 s_2 + 2^0 C_1^1 s_0)=v(2s_2+s_0)$
при $n=3$

будет $\det A = v(2^3 s_3 + 2^2 C_1^1 s_1)=v(8s_3+4s_1)$
при $n=4$

будет $\det A = v(2^6 s_4 + 2^5 C_1^1 s_2 + 2^3 C_3^2 s_0)=v(64s_4+32s_2+24s_0)$
при $n=5$

будет $\det A = v(2^{10} s_5 + 2^9 C_1^1 s_3 + 2^7 C_3^2 s_1)=v(1024s_5+512s_3+384s_1)$
при $n=6$

будет $\det A = v(2^{15} s_6 + 2^{14} C_1^1 s_4 + 2^{12} C_3^2 s_2 + 2^{10} C_5^3 s_0)=$
$=v(32768s_6+16384s_4+12288s_2+10240s_0)$

и т.д.

Портал Естественных Наук, версия 1.1