Let $A$ be a matrix sized $p\times p$, where $2\le p$. Using recurrence relations, describe $A^k$.

Question

Let $A$ be a matrix sized $p\times p$, Where $2\le p$. The matrix values in the main diagonal are $0$ and the rest are $1$'s.

Example for $A$ where $p=5$: $$\begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \\ \end{bmatrix} $$

Using reccurences relations, describe $A^k$.

Answer 1

HINT: Calculating a few powers of such matrices quickly suggests that $A^k$ always has just two distinct entries, one appearing on the diagonal, and the other appearing off the diagonal. You might try proving this by induction: the induction step, if it works, is likely to tell you what the recurrences actually are.

Let the $(i,j)$-entry of $A^k$ be $a_{ij}^k$, and suppose that $a_{ii}^k=b_k$ for $i=1,\dots,n$ and $a_{ij}^k=c_k$ when $i\ne j$. Then

$$a_{ii}^{k+1}=\sum_{j=1}^{i-1}c_k+\sum_{j=i+1}^nc_k=(n-1)c_k\;;$$

why? This is independent of $i$, so all of the diagonal entries of $A^{k+1}$ are equal to $b_{k+1}(n-1)c_k$. See if you can finish it by dealing with the off-diagonal elements.

Answer 2

Let $B$ be the matrix with all entries equal to $1$. Then $B^n=p^{n-1}B$ for $n\geq1$. We have $A=B-I$. So $$ A^n=(B-I)^n=(-1)^nI+\sum_{k=1}^n\,{n\choose k}\,B^k\,(-1)^{n-k}=(-1)^nI+\sum_{k=1}^n\,{n\choose k}\,p^{k-1}B\,(-1)^{n-k}\\ =(-1)^nI+B\,\sum_{k=1}^n\,{n\choose k}\,p^{k-1}\,(-1)^{n-k}=(-1)^nI+B\,\frac1p\,\sum_{k=1}^n\,{n\choose k}\,p^{k}\,(-1)^{n-k}\\ =(-1)^nI+B\,\frac1p\,[(p-1)^n-(-1)^n]. $$ Using that $B=A+I$, we get $$ A^n=(-1)^nI+\frac1p\,[(p-1)^n-(-1)^n]\,(A+I). $$