2014 dxdy logo

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

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




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


11/01/06
5702
Пусть
$$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
1700
москва
Будем обозначать матрицы заглавными буквами. Найдем сначала:$$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
5487
Нов-ск
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
5702
Мое доказательство представлено в препринте Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations (см. Lemma 1) и основывается на этом свойстве чисел Каталана: topic103028.html

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

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

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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