How to show $\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}^n = 2^{n-1}\begin{pmatrix}1&1 \\ 1&1\end{pmatrix}$?

Question

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?

Answer 1

One nitpick; you say that

which means the contribution of the whole expression ... will be reduced to zero or one.

This is not correct. Instead, the entire expression is reduced to either $0,A,B,C$ or $D$.

---

I think a better term is to say you are summing over all sequences of $A,B,C$ and $D$. Many of these sequences will contribute $0$ to the final summation; for example, if $AC$ occurs consecutively anywhere in the sequence, then $AC=0$, so the entire product is $0$.

In fact, for every matrix, there are exactly $2$ matrices which can follow it while allowing the entire product to be nonzero. $A$ can be followed by only $A$ or $B$, $B$ can be followed by only $C$ or $D$, etc. This means that once the first matrix in the sequence is determined, there are exactly $2^{n-1}$ ways to complete the sequence. With $4$ ways to choose the initial matrix, there are $4\cdot 2^{n-1}$ nonzero products.

Each of these products reduces down, using your multiplication table, to a single matrix, either $A,B,C$ or $D$. As long as we can show that each of these results appears equally, we would be done, since then the final result would be $$ 2^{n-1}\cdot (A+B+C+D)=2^{n-1}M. $$ This equi-distribution is not hard to prove if you look at things in the correct way. Let $N_A,N_B,N_C,$ and $N_D$ be the number of nonzero products which evaluate to $A,B,C$ and $D$ respectively.

• We can prove $N_A=N_B$ as follows. Given a sequence which evaluates to $A$, then changing the last factor via the rule $$A\leftrightarrow B,\qquad C\leftrightarrow D$$will result in a sequence whose product is $B$. This operation is a bijection, so $N_A=N_B$.

• The same bijection in the previous bullet proves $N_C=N_D$.

• Finally, if you instead apply this substitution to the first element of a nonzero sequence, you can prove $N_A=N_C$ and $N_B=N_D$:$$A\leftrightarrow C,\qquad B\leftrightarrow D$$

Therefore, all of the nonzero products appear equally, and we are done.

Answer 2

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.