Consider a symmetric tridiagonal matrix $A\in \mathbb{R}^{n \times n}$:
$$A=\begin{bmatrix}
a_1 & b_1 & 0 & \cdots & 0\\
b_1 & a_2 & b_2 && \vdots \\
0 & \ddots & \ddots & \ddots & 0 \\
\vdots && b_{n-2} & a_{n-1} & b_{n-1}\\
0 & \cdots & 0 & b_{n-1} & a_n
\end{bmatrix}$$
Now consider the powers of this matrix: $A^2, A^3, \dots, A^k$ for $k \in \mathbb{N}$.
Is there a simple way to write out the general $A^k$?
Specifically, I want to show that the number of nonzero entries in the first row is $k$ for $k=2,\dots,n$, ie. increases by one for each power. Is there any way to show this?
I have tried writing the multiplication out in summation form, but this gets messy fast. Since this is a sparse matrix, is there a neat way to put it?
Best Answer
To see that $A^k$ has "one diagonal more" than $A^{k-1}$, write the column $j$ of the equation $A^k=A^{k-1}\cdot A$, which gives $$ (A^k)_{:,j}=A^{k-1}\cdot (A)_{:,j}=a_{j-1,j}(A^{k-1})_{:,j-1}+a_{j,j}(A^{k-1})_{:,j}+a_{j+1,j}(A^{k-1})_{:,j+1}. $$ So the column $(A^k)_{:,j}$ of $A^k$ is combined from the corresponding column of $A^{k-1}$ and the columns $j-1$ and $j+1$. Since $(A^{k-1})_{:,j-1}$ has one nonzero more below the last nonzero position of $(A^{k-1})_{:,j}$ and $(A^{k-1})_{:,j+1}$ has one nonzero more above the last nonzero position of $(A^{k-1})_{:,j}$, the nonzero pattern of the column $(A^k)_{:,j}$ grows by one both up and down.
Formally, you can use the induction in the same spirit.