Determining the primitive order of a binary matrix

Question

Let ${\bf A}_n$ be an $2n \times 2n$ matrix that is defined as follows

$$ {\bf A}_n=\left( \begin{array}{c} 0&0&\cdots&0&0&0&0&1&1\\ 0&0&\cdots&0&0&1&0&0&0\\ 0&0&\cdots&0&0&1&1&0&0\\ 0&0&\cdots&1&0&0&0&0&0\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ 1&1&\cdots&0&0&0&0&0&0\\ 0&0&\cdots&0&0&0&0&1&0\\ \end{array} \right). $$

For instance, the matrix ${\bf A}_5$ is given by

$$ {\bf A}_5=\left( \begin{array}{cccccccccc} 0&0&0&0&0&0&0&0&1&1\\ 0&0&0&0&0&0&1&0&0&0\\ 0&0&0&0&0&0&1&1&0&0\\ 0&0&0&0&1&0&0&0&0&0\\ 0&0&0&0&1&1&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0\\ 0&0&1&1&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0&0&0\\ 1&1&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&1&0 \end{array} \right). $$

My Question: How to show that the $(n+2)$th power of ${\bf A}_n$, denoted by ${\bf A}_n^{n+2}$, is a positive matrix and matrices ${\bf A}_n^{i}$ with $1\leq i \leq n+1$ are not positive matrices?

For instance, it can be checked that ${\bf A}_5^{7}$ is a positive matrix and matrices ${\bf A}_5^{i}$ with $1\leq i \leq 6$ are not positive matrices.

I know this question is related with the concept of primitive matrices and maybe by considering the values of the eigenvalues of ${\bf A}_n$ we can obtain an answer. But I would like to find a combinatorial answer. For example, we can consider ${\bf A}_n$ as an adjacency matrix of a weighted directed graph. Then we should check why there is at least a directed walk between every node of the graph of length $n+2$? The weighted directed graph of ${\bf A}_5$ can be drawn in the following form

It follows from the given graph that there is at least a directed walk between every node of the graph of length $7$. Also, it can be checked that there is no directed walk between the node 4 to the node 2 of length less than seven.

Thanks for any suggestions.

Edition 1:

Consider the following $2\times 2$ matrices

$$ {\bf m}=\left( \begin{array}{c} 1&1 \\ 0&0 \end{array} \right),\quad {\bf n}=\left( \begin{array}{c} 0&0 \\ 1&0 \end{array} \right),\quad {\bf z}=\left( \begin{array}{c} 0&0 \\ 0&0 \end{array} \right). $$ The matrix ${\bf A}_n$ is a type of block-circulant matrices that can be defined as follows:

$$ {\bf A}_n=\left( \begin{array}{c} {\bf z} & {\bf z} &\cdots &{\bf z}& {\bf z}&{\bf n} & {\bf m}\\ {\bf z} & {\bf z} &\cdots & {\bf z}&{\bf n}&{\bf m} & {\bf z}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\dots\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ {\bf n} & {\bf m} &\cdots & {\bf z}&{\bf z}&{\bf z} & {\bf z}\\ {\bf m} & {\bf z} &\cdots & {\bf z}&{\bf z}&{\bf z} & {\bf n} \end{array} \right). $$

From Maple software, the associated graphs with ${\bf A}_i$ with $2\leq i \leq 11$ are provided as follows

Answer 1

It is convenient to treat $A_n$ as an $n\times n$ block matrix $B$ consisting of $n^2$ matrices of the side $2\times 2$. We enumerate the rows and columns of $B$ from 1 to $n$, but treat them as residues modulo $n$. I also write $\bf 0$ for $\bf z$. We have $$B_{ij}=\begin{cases}{\bf m},&\text{if}\,\, i+j=1,\\ {\bf n},&\text{if}\,\, i+j=0,\\ {\bf 0},& \text{otherwise} \end{cases}$$ Now we learn how to multiply ${\bf m}$ and ${\bf n}$. We have ${\bf n}^2={\bf 0}$, ${\bf m}^2={\bf m}$, ${\bf nm}=\pmatrix{0&0\\1&1}$, ${\bf mn}=\pmatrix{1&0\\0&0}$, ${\bf nmn}={\bf n}$, ${\bf mnm}={\bf m}$.

Consider any product of several ${\bf m}$'s and ${\bf n}$'s, it corresponds to some word in the alphabet $\{{\bf m},{\bf n}\}$. This product has 0 at its right upper entry unless the word starts and ends with $\bf m$. It has 0 at its right lower entry unless the word starts with $\bf n$ and ends with $\bf m$.

Assume now that $k\leqslant n+1$. Look at the block matrix $B^k$. Its $(a,b)$-th position (where $1\leqslant a,b\leqslant n$) equals $$ \sum_{i_1,i_2,\dots,i_{k-1}} B_{a,i_1}B_{i_1,i_2}\dots B_{i_{k-1},b}. $$

Any term is either a zero or a product of some $k$ letters in the alphabet $\{{\bf m},{\bf n}\}$. If $A^k$ is a positive matrix, for any $a,b$ there should exist such a word starting with $\bf{m}$ and ending with $\bf{mn}$. Consider such a word, the indices modulo $n$ must satisfy $a+i_1=1$, $b+i_{k-1}=0$, $i_{k-1}+i_{k-2}=1$ and $i_s+i_{s+1}:=\varepsilon_s\in \{0,1\}$ for all $s=1,2,\dots,k-3$. Therefore modulo $n$ we get $$ \varepsilon_{k-3}-\varepsilon_{k-4}+\dots+(-1)^{k-1}\varepsilon_1= i_{k-2}+(-1)^{k-1}i_1=1+b+(-1)^{k-1}(1-a). $$ Fix $a=1$ and $b$ such that $1+b+[(k-3)/2]=n-1$ (remind that this is all modulo $n$). Then $$ n-1=1+b+[(k-3)/2]=\varepsilon_{k-3}+(1-\varepsilon_{k-4})+\varepsilon_{k-5}+\dots $$ is a sum of $k-3\leqslant n-2$ elements of $\{0,1\}$. That is of course impossible.

As for $k=n+2$, we should construct necessary words of length $k$ of the form ${\bf m}\ldots {\bf m}$ and ${\bf m}\ldots {\bf mn}$ with prescribed alternating sum of $k-2$ or $k-3$ $\varepsilon$'s. This itself is certainly possible, since $k-2=n$, $k-3=n-1$ and any remainder modulo $n$ is a sum of at most $n-1$ elements of $\{0,1\}$. But we should also care that such a word does not contain two consecutive ${\bf n}$'s (this is the only thing to carry about: the matrices $\bf m$ and $\bf mn$ cover all four entries, so if the words of both type exist, $B_{a,b}$ is positive $2\times 2$-matrix.) On the language of $\varepsilon$'s this means that there should be no two consecutive zeroes. But this may be acheieved by making either $\varepsilon_{k-3}=\varepsilon_{k-5}=\dots=1$, or by making $\varepsilon_{k-2}=\varepsilon_{k-4}=\dots=1$. Any necessary alternating sum is still realized.