Motzkin numbers as a convergent of iterative matrix inversion

I have here left out the indices of the elements for easier typing but hopefully this can still be understood.

{A=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ x&1&0&0&0&0&0&0\\ x&x&1&0&0&0&0&0\\ x&x&x&1&0&0&0&0\\ x&x&x&x&1&0&0&0\\ x&x&x&x&x&1&0&0\\ x&x&x&x&x&x&1&0\\ x&x&x&x&x&x&x&1\end{array}\right)

Shift down the elements in matrix {A} two steps to get matrix {B}.

{B=}\left(\begin{array}{cccccccc}0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ x&1&0&0&0&0&0&0\\ x&x&1&0&0&0&0&0\\ x&x&x&1&0&0&0&0\\ x&x&x&x&1&0&0&0\\ x&x&x&x&x&1&0&0\end{array}\right)

Add two diagonals of ones to the main diagonal (where row index = column index) and to the diagonal below (where row index = column index + 1) in matrix {B} to get matrix {C}.

{C=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&1&1&0&0&0&0&0\\ x&1&1&1&0&0&0&0\\ x&x&1&1&1&0&0&0\\ x&x&x&1&1&1&0&0\\ x&x&x&x&1&1&1&0\\ x&x&x&x&x&1&1&1\end{array}\right)

Change the sign of all the elements below the main diagonal in matrix {C} so that you get matrix {D}.

{D=}\left(\begin{array}{cccccccc}1&0&0&0&0&0&0&0\\ -1&1&0&0&0&0&0&0\\ -1&-1&1&0&0&0&0&0\\ -x&-1&-1&1&0&0&0&0\\ -x&-x&-1&-1&1&0&0&0\\ -x&-x&-x&-1&-1&1&0&0\\ -x&-x&-x&-x&-1&-1&1&0\\ -x&-x&-x&-x&-x&-1&-1&1\end{array}\right)

Calculate the matrix inverse of matrix {D} to get matrix {E}

Iterate by replacing matrix {A} with matrix {E}.

Matrix {E} should then converge to the Motzkin numbers in all columns.

Keywords: Matrix inversion, Motzkin numbers, iteration.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.