2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 чем степень матрицы нам наследила
Сообщение07.11.2015, 17:41 
Модератор
Аватара пользователя


11/01/06
5710
Пусть
$$A = \begin{bmatrix}
0 & 1 & z & 0\\
y & 0 & 0 & yz\\
y & 0 & 0 & 0\\
0 & 1 & 0 & 0
\end{bmatrix}.$$
Докажите, что для всяких целых $n>1$ и $j\geq 0$, коэффициент при $y^n z^j$ в $\mathrm{tr}(A^{2n})$ равен $\frac{4n}{2n-j}\binom{2n-j}{j}$.

(У этого факта есть замечательная комбинаторная интерпретация.)

 Профиль  
                  
 
 Re: чем степень матрицы нам наследила
Сообщение17.11.2015, 13:44 
Заслуженный участник


03/01/09
1717
москва
Будем обозначать матрицы заглавными буквами. Найдем сначала:$$A^2=y(R+zI)\qquad (1)$$, где $I$-единичная матрица $4\times 4, R=\begin {bmatrix}E&zS\\S&O\end {bmatrix}, S=\begin {bmatrix}0&1\\1&0\end {bmatrix}, E-$единичная матрица $2\times 2, O-$нулевая матрица $2\times 2$.
В свою очередь можно записать $R=B+zQ$, где $B=\begin {bmatrix}E&O\\S&O\end {bmatrix},Q=\begin {bmatrix}O&S\\O&O\end {bmatrix}.$ С помощью (1) получим:$$A^{2n}=y^n\sum \limits _{k=0}^nC^k_nz^kR^{n-k}\qquad (2).$$Таким образом нужный нам коэффициент равен коэффициенту перед $z^j$ в следе суммы в (2). Понятно, что вклад в этот коэффициент дают слагаемые суммы в (2) с $k\leq j$.
Этот вклад равен: $C^k_n\mathrm {tr}T_k$, где $T_k$-это сумма всевозможных произведений $(n-j)$ матриц $B$ и $(j-k)$ матриц $Q$. Отметим следующие свойства матриц $B$ и $Q: B^k=B\qquad (3), Q^k-$нулевая матрица при $k>1\qquad (4), (QB)^k=QB=\begin {bmatrix}E&O\\O&O\end {bmatrix}$. Так как все степени матрицы $Q$ выше первой равны 0, то в сумме $T_k$ останутся лишь те произведения, в которых нет соседних матриц $Q$, т.е. останутся произведения вида: $QB^{k_1}QB^{K_2}\dots QB^{k_m}$. Число таких произведений равно: $C_{n-j+1}^{j-k}$. Среди этих произведений будут иметь нулевой след произведения вида: $QB^{k_1}\dots B^{k_m}Q$, т.к. при взятии следа $Q$ справа можно перенести налево и мы по лучим $Q^2$. Число произведений такого вида равно: $C_{n-j-1}^{j-k-2}.$ Оставшиеся произведения с учетом свойства (3), (4) приводятся к виду: $QB\dots QB=(QB)^{j-k}=QB, \mathrm {tr}(QB)=2$. Таким образом вклад от $k-$ого слагаемого равен: $2C_n^k(C_{n-j+1}^{j-k}-C_{n-j-1}^{j-k-2})\qquad (5)$. Суммируя выражения (5) по $k$ от 0 до $j$ получим, что коэффициент равен: $a_j=2(C_{2n-j+1}^j-C_{2n-j-1}^{j-2})=\dfrac {4n}{2n-j}C_{2n-j}^j$
(при суммировании по $k$ была использована формула $\sum \limits _{k=0}^jC_m^kC_{n-m}^{j-k}=C_n^j$)

 Профиль  
                  
 
 Re: чем степень матрицы нам наследила
Сообщение18.11.2015, 08:41 
Заслуженный участник
Аватара пользователя


23/08/07
5502
Нов-ск
mihiv в сообщении #1074265 писал(а):
Будем обозначать матрицы заглавными буквами. Найдем сначала:$$A^2=y(R+zI)\qquad (1)$$ .........

Можно укоротить это решение. Учитывая "независимость" крайних строк и столбцов матрицы $A^2$ от средних столбцов и строк, получаем
$$tr(A^{2n})= 2y^n tr(P^n)=2y^n tr(Q^{2n})=2y^n tr\left((Q_1 + z Q_2)^{2n}\right)$$
где
$$P=Q^2=\begin {bmatrix}1+z& z \\ 1& z\end {bmatrix}, \; 
Q=\begin {bmatrix}1& z \\ 1&0\end {bmatrix}, \;
Q_1=\begin {bmatrix}1& 0 \\ 1&0\end {bmatrix}, \;
Q_2=\begin {bmatrix}0& 1 \\ 0&0\end {bmatrix}.
$$
Осталось расставить $j$ матриц $Q_2$ на $2n$ мест, чтобы они не стояли рядом (даже циклически), т. е.
$$2(C_{2n-j}^j+C_{2n-j-1}^{j-1})=\dfrac {4n}{2n-j}C_{2n-j}^j$$

 Профиль  
                  
 
 Re: чем степень матрицы нам наследила
Сообщение18.11.2015, 20:19 
Модератор
Аватара пользователя


11/01/06
5710
Мое доказательство представлено в препринте Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations (см. Lemma 1) и основывается на этом свойстве чисел Каталана: topic103028.html

TOTAL в сообщении #1074507 писал(а):
Осталось расставить $j$ матриц $Q_2$ на $2n$ мест, чтобы они не стояли рядом (даже циклически)

Отсюда и до комбинаторной интепретации рукой подать (подробности по ссылке выше).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group