Задача по линейной алгебре

[Nomo]

Я пытаюсь решить одну задачу про сходимость марковских цепей и для этого мне требуется диагонализовать матрицу $k * k$ . Значит у нас есть величины $ c_{ij} = e^{- \frac{V_j - V_i}{2}}, $ для $ i \neq j $, а $c_{ii} = - \sum_{j \neq i} c_{ij}$ и $\pi_i = e^{-V_i}/k$, мера $\pi$ обратимая, то есть $\pi_i c_{ij} = \pi_j c_{ji}$. Необходимо привести к диагональному виду матрицу $M = (\pi_x c_{xy})_{xy}$ и найти матрицы перехода к новому базису (так как в общем говоря, мне нужно найти матричную экспоненту). Попытался решить характеристический многочлен для случая k = 3, но забросил попытку как бесперспективную где-то на 6-ой строчке. Также пытался воспользоваться элементарными преобразованиями, чтобы привести матрицу к нужному виду, но тоже далеко. Можете ли вы что-то посоветовать?

[svv]

1) Ввести обозначения $p_i=e^{-\frac{V_i}2}\,,\; s=\sum\limits_i p_i$. Матрица $M$ (после умножения на $k$) примет вид
$\begin{bmatrix}p_1(p_1-s)&p_1p_2&\ldots&p_1p_k\\p_2p_1&p_2(p_2-s)&\ldots&p_2p_k\\ \cdots&\cdots&\cdots&\cdots\\p_kp_1&p_kp_2&\cdots&p_k(p_k-s)\end{bmatrix}=pp^T-s\operatorname{diag}(p_1,p_2,\cdots,p_k)$
Красивая матрица, симметричная, диагонализируемая (с помощью ортогонального преобразования), сумма элементов каждой строки и каждого столбца равна нулю.

2) Для случая $k=3$ вбить матрицу в строку запроса WolframAlpha:
{{-a*b-a*c,a*b,a*c},{b*a,-b*a-b*c,b*c},{c*a,c*b,-c*a-c*b}}

3) Посмотреть на собственные значения и собственные векторы и оставить попытки найти их в общем виде как бесперспективные.

[svv]

Nomo
Может быть, Вы опишете исходную задачу (желательно со ссылкой на условие)? Тут есть хорошие специалисты по теорверу и матстату.

[Nomo]

С такими обозначениями матрица действительно красивая, чего не скажешь про собственные значения. Попробую тогда сформулировать свою задачу целиком. Она состоит в том, чтобы сравнить скорости схождения к инвариантной мере у марковского процесса и его симметричной части. Если считать, что матрица M это генератор как раз симметричной части процесса с генератором $M'$, то элементы $M'$ будут иметь вид $(\pi_i c_{ij}')_{ij}$, где $c_{ij}' = e^{-\frac{V_j-V_i}{2}}R(i,j), i \neq j$, a $ c_{ii}' = - \sum_{j \neq i} c_{ij}'$, можно считать $R(i,j) = e^{r(i,j)}$, где $R(i,j) + R(j,i)= 2$, откуда $ r(i,i) = 0$. Матрица $M'$ уже не симметрична. Скорость измеряем как предел относительной энтропии, усредненной по всем состояниям марковского процесса, учитывая исходное распределение $\pi$; она [скорость] будет выглядеть следующим образом: $\lim_{t \to 0} h(c) = \lim_{t \to 0}[\frac{1}{t}(\sum_{i,j}\pi(i)(e^{tM})_{ij}\log(e^{tM})_{i,j} - \sum_{j}\pi_j \log\pi_j)]$. Как тогда можно сравнить эти пределы для матриц $M$ и $M'$ (доказать, что один не больше другого для любого k), если не получается выписать элементы матричной экспоненты в явном виде даже для симметричной матрицы?

[svv]

У Вас предел от дроби (со знаменателем $t$). Не равен ли он производной от числителя по $t$ при $t=0$ ?

[svv]

Nomo в сообщении #1516142 писал(а):

$\lim_{t \to 0}[\frac{1}{t}(\sum_{i,j}\pi(i)(e^{tM})_{ij}\log(e^{tM})_{i,j} - \sum_{j}\pi_j \log\pi_j)]$

Чтобы предел был конечным, первая сумма должна при $t\to 0$ стремиться ко второй сумме. Я не понимаю, как это получается. При малых $t$ матрица $e^{tM}\approx E+tM$, значит, $(e^{tM})_{ij}\approx \delta_{ij}+tM_{ij}$. Очевидно, что внедиагональные элементы стремятся к нулю (даже после умножения на логарифм), так что остаётся одно суммирование по индексу, допустим, $j$. А дальше? Откуда берётся $\log\pi_j$ ? Ведь выражение под логарифмом стремится к единице, а сам логарифм — к нулю.

[Nomo]

Виноват, ошибся: t стремится к бесконечности, а иначе действительно получается тривиальный случай, как вы и описали. Если $t \to \infty$, то я могу доказать, что производная средней относительной энтропии, которую будет удобнее записать в виде $\lim_{t \to \infty} \frac{1}{t} h_t(c) = \lim_{t \to \infty}[\frac{1}{t}(\sum_{i,j}\pi_i(e^{tM})_{ij}\log\frac{(e^{tM})_{i,j}}{\pi_j}]$ (можно увидеть, что она эквивалентна предыдущей записи, если применить свойство инвариантности меры $\pi$: $ \sum_i\pi_i (e^{tM})_{ij} = \pi_j$ ), равна самому маленькому ненулевому собственному значению $\lambda_2$ со знаком минус. Чтобы доказать этот факт нужно обратиться к представлению матрицы $ M = UJU^{-1}$, где J диагональная матрица, либо жорданова в случае несимметричной $M'$. Тогда $(e^{tM})_{ij}$ будет представляться в виде линейной комбинации экспонент с собственными значениями в показателе (т.е. $e^{-\lambda_i t}$ ) и с функциями от i,j в качестве коэффициентов. Тогда останется воспользоваться разложением логарифма в ряд и увидеть, что $\lim_{t \to \infty}\frac{1}{t} h_t(c) = - \lambda_2 $. Это конечно очень грубый набросок доказательства. Теперь мы можем заметить, что в пространстве $L_2 (\pi)$, где скалярное произведение определяется так: $<v,w> = \sum_i \pi_i v_i v_j$, верно, что $<Mv,v> = <\frac{M' + (M')^T}{2}v, v> = <M'v,v>$ ($M$ это матрица соответствующая симметричной части процесса с матрицей$M'$, поэтому $M = \frac{M' + (M')^T}{2}$) и что $\lambda_2 (M) = inf(<-M'v,v> : <v,1> = 0, <v,v> =1)$ (Это следует из того, что пространство $ R^k $ раскладывается в прямую сумму циклических подпространств относительно оператора M и того, что $<-Mv,v> \geq \lambda_2(M) <v,v>$, а требование $<v,1> = 0$ нужно, чтобы v не попал в одномерное подпространство, соответствующее нулевому собственному значению). Получается нам необходимо, чтобы система, состоящая из неравенства $\lambda_2 (M') \geq <-M'v,v>$ и уравнений $<v,1> = 0, <v,v> =1 $ имела хотя бы одно решение, то есть, чтобы существовала хотя бы одна такая функция $v$ (или вектор если угодно), удовлетворяющая этим условиям. Тогда производная усредненной энтропии всего процесса будет не больше усредненной энтропии симметричной части процесса. Я пока не очень представляю как доказать существование (или отсутствие) решения в $L_2(\pi)$ со скалярным произведением определенным выше.

[svv]

Nomo в сообщении #1518374 писал(а):

скалярное произведение определяется так: $<v,w> = \sum_i \pi_i v_i v_j$

Уточните, пожалуйста, правую часть, что-то не то с индексами. Да и $w$ куда-то делась.

Есть красивые угловые скобки, пишутся \langle и \rangle:
$\lambda_2 (M) = \inf(\langle -M'v,v\rangle : \langle v,1\rangle = 0, \langle v,v\rangle =1)$
Лучше $\inf$ \inf, чем $inf$ inf.
Матрица $m\times n$ m\times n.

[Nomo]

Да, спасибо. Вот так правильно $\langle v, w \rangle = \sum_i \pi_i v_i w_i$. Также я забыл указать, что теперь нет нужды считать $M = (\pi_x c_{xy})_{xy}$, сейчас это просто $ (M)_{ij} = c_{ij} $

[svv]

Но при таком определении $M$ не будет симметричной:
$c_{12} = e^{- \frac{V_2 - V_1}{2}}$
$c_{21} = e^{- \frac{V_1 - V_2}{2}}$

[ilghiz]

svv в [url=http://dxdy.ru/post1515871.html#p1515871] писал(а):

3) Посмотреть на собственные значения и собственные векторы и оставить попытки найти их в общем виде как бесперспективные.

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

$$\sum_{k=1}^K \frac{p_k^2}{s p_k + l} = 1$$

по $l$, и, каждое решение можно найти делением отрезка пополам между двумя ближайшими по значению $p$, а еще одно - на краю сверху или снизу каким-нибудь быстро сходящимся Ньютоном.

[Nomo]

Цитата:

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

$$\sum_{k=1}^K \frac{p_k^2}{s p_k + l} = 1$$

А можете пояснить откуда берется такое уравнение и что такое $s$ и $l$?

[ilghiz]

Nomo в [url=http://dxdy.ru/post1519628.html#p1519628] писал(а):

А можете пояснить откуда берется такое уравнение и что такое $s$ и $l$?

Если рассматривать обозначения, которые ввел svv выше:

$p_i=e^{-\frac{V_i}2}\,,\; s=\sum\limits_i p_i$
$\begin{bmatrix}p_1(p_1-s)&p_1p_2&\ldots&p_1p_k\\p_2p_1&p_2(p_2-s)&\ldots&p_2p_k\\ \cdots&\cdots&\cdots&\cdots\\p_kp_1&p_kp_2&\cdots&p_k(p_k-s)\end{bmatrix}=pp^T-s\operatorname{diag}(p_1,p_2,\cdots,p_k)$

то, чтобы найти ее собственные значения надо искать такое $l$, которое удовлетворяет условию, что я написал.

Вывод легко осуществить, если положить $x$ - собственным вектором, который соответсвует собственному значению $l$ и решить $pp^Tx-s\operatorname{diag}(p_1,p_2,\cdots,p_k)x = l x$ по $x$.