<s>[INST] How to show $\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}^n = 2^{n-1}\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}$? Initial note: I'm interested in the combinatorics aspect of the following problem, not how to proof the relation in general.

The idea is to show the following relationship:
$$
\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}^n = 2^{n-1}{\underbrace{\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}}_{\equiv M}}
$$
by decomposing the matrix $M = A + B + C + D$ into the four individual matrices
$$
A = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} \qquad
B = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \qquad
C = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} \qquad
D = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}
$$
and noting the following relationships for matrix multiplication:




$\ast$
$A$
$B$
$C$
$D$




$\bf{A}$
$A$
$B$
$0$
$0$


$\bf{B}$
$0$
$0$
$A$
$B$


$\bf{C}$
$C$
$D$
$0$
$0$


$\bf{D}$
$0$
$0$
$C$
$D$




If these matrix products were commutative, one could use the multinomial theorem in order to compute the coefficients for the resulting polynomial $(A+B+C+D)^n$. Since they are not, one needs to consider all possible combinations for the matrices $A,B,C,D$ (like for this question):
$$
\sum_{combinations} X_1X_2\dots X_n \qquad, \quad \mathrm{where} \; X_i \in \{A,B,C,D\}
$$
However due to the above relations, each pair of matrices $X_iX_{i+1}$ can be reduced to either zero or another matrix of the set $\{A,B,C,D\}$ (which means the contribution of the whole expression $X_1X_2\dots X_n$ will reduce to either $0$ or $1$). So I'm wondering whether by applying this knowledge it is possible to combine the various permutations for a given term $A^{k_1}B^{k_2}C^{k_3}D^{k_4}$ in order to determine how many nonzero permutations there are. Together with the multinomial coefficients this could then be used to calculate the result.
At this point I'm struggling to find the number of nonzero permutations for a given set of powers $\{k_1,k_2,k_3,k_4 | k_i \geq 0\}$ in the expression $A^{k_1}B^{k_2}C^{k_3}D^{k_4}$. Is there are way to determine this?
 [/INST] Some more aspects regarding OPs approach. When looking at the matrix $M$ in the form
\begin{align*}
M=A+B+C+D
\end{align*}
we can associate certain walks in the graph $G(M)$ given below. The graph consists of two nodes $1$ and $2$ and directed edges corresponding to the entries of $M$. We recall Theorem 1.1. from Algebraic Combinatorics by R. P. Stanley:

*

*Theorem: For any integer $n\geq 1$, the $(i,j)$-entry of the matrix $M^n$ is equal to the number of walks from node $i$ to node $j$ of length $n$.

                                                   
This means that $A,B,C,D$ can be represented as subgraphs of $G(M)$ whereby

*

*$A= \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ has a path from node $1$ to $1$


*$B= \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ has a path from node $1$ to $2$


*$C= \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$ has a path from node $2$ to $1$


*$D= \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$ has a path from node $2$ to $2$
We want to show that
\begin{align*}
\color{blue}{M^n=\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}^n=2^{n-1}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}}\tag{1}
\end{align*}
by counting paths via $A,B,C$ and $D$ of length $n$.
Paths of length $n$ from node $1$ to $1$:

*

*In order to get a path of length $n$ from node $1$ to $1$ we can take zero or more times $A$. We can also take zero or more times $BC$, noting that whenver we go via $B$ from node $1$ to $2$ we also have to go back via $C$ from $2$ to $1$. Whenever we are going from $1$ to $1$ via $BC$ we can insert zero or more times $D$ walking the loop from $2$ to $2$.


*This means we have building blocks
\begin{align*}
\color{blue}{\{A,BC,BDC,BD^2C,\ldots\}}\tag{2}
\end{align*}
which can be used to build all paths of length $n$. For instance all $2^3=8$ paths of length $4$ from node $1$ to $1$ are given by
\begin{align*}
&A^4,\\
&A^2(BC),A(BC)A,(BC)A^2,\\
&A(BCD),(BCD)A,\\
&(BC^2D),\\
&(BC)(BC)
\end{align*}
To better see the building blocks, those containing $B$ are written in parentheses. Note that no two building blocks have the same length. This is an essential property which we'll use in order to prove (1).
Paths of length $n$ from node $2$ to $2$:
The building blocks of paths from node $2$ to $2$ are due to symmetry according to (2)
\begin{align*}
\color{blue}{\{D,CB,CAB,CA^2B,\ldots\}}\tag{3}
\end{align*}
Paths of length $n$ from node $1$ to $2$:
We can use the building blocks from (2) and (3). We can either start with $B$, walk from $1$ to $2$ and append all paths of length $n-1$ from node $2$ to $2$. We can otherwise take all paths of length $n-1$ from $1$ to $1$ and append $B$ from $1$ to $2$ as last step. We obtain
\begin{align*}
\color{blue}{\{BD,BCB,BCAB,BCA^2B,\ldots\}\cup \{AB,BCB,BDCB,BD^2CB,\ldots\}}\tag{3}
\end{align*}
Paths of length $n$ from node $2$ to $1$:
Due to symmetry we have according to (3) the building blocks
\begin{align*}
\color{blue}{\{DC,CBC,CABC,CA^2BC,\ldots\}\cup \{CA,CBC,CBDC,CBD^2C,\ldots\}}\tag{4}
\end{align*}

We are now ready to prove (1). We start with counting the number of paths of length $n$ from node $1$ to $1$.We observe that the length of the building blocks (2) is unique. We consider the lengths
\begin{align*}
&\{\overline{A},\overline{BC},\overline{BDC},\overline{BD^2C},\overline{BD^3C},\ldots\}=\{1,2,3,4,5,\ldots\}\\
\end{align*}
Example: $n=4$. We consider a small example to better see what's going on. The $2^3=8$ paths of length $4$ from node $1$ to $1$ are:
\begin{align*}
\begin{array}{ll}
1+1+1+1&\qquad\qquad A^4\\
1+1+2&\qquad\qquad A^2(BC)\\
1+2+1&\qquad\qquad A(BC)A\\
2+1+1&\qquad \qquad(BC)A^2\\
2+2&\qquad\qquad (BC)^2\\
1+3&\qquad\qquad A(BDC)\\
3+1&\qquad \qquad(BDC)A\\
4&\qquad\qquad (BDDC)
\end{array}
\end{align*}

*

*We observe the number $\alpha_n$ of paths of length $n$ from node $1$ to node $1$ is equal to the number of compositions to $n$, and this number is known to be $$\color{blue}{\alpha_n=2^{n-1}}$$


*In the same way we we find the number $\delta_n$ of paths of length $n$ from node $2$ to $2$ is $$\color{blue}{\delta_n=2^{n-1}}$$


*The number $\beta_n$ of paths of length $n$ from node $1$ to $2$ is calculated according to the derivation above as
\begin{align*}
\color{blue}{\beta_n}=\alpha_{n-1}+\delta_{n-1}=2\cdot 2^{n-2}\color{blue}{=2^{n-1}}
\end{align*}
and analogously we have $$\color{blue}{\gamma_n}=\alpha_{n-1}+\delta_{n-1}\color{blue}{=2^{n-1}}$$
We conclude
\begin{align*}
\color{blue}{M^n}=\begin{pmatrix}
\alpha_n&\beta_n\\
\gamma_n&\delta_n\\
\end{pmatrix}
=\begin{pmatrix}
2^{n-1}&2^{n-1}\\
2^{n-1}&2^{n-1}\\
\end{pmatrix}
\color{blue}{=2^{n-1}\begin{pmatrix}
1&1\\
1&1\\
\end{pmatrix}}
\end{align*}
showing the claim is valid.

</s>