чем степень матрицы нам наследила

[maxal]

Пусть

$$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}$.

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

[mihiv]

Будем обозначать матрицы заглавными буквами. Найдем сначала:

$$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$)

[TOTAL]

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$$

[maxal]

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

TOTAL в сообщении #1074507 писал(а):

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

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