# Determining the primitive order of a binary matrix

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 • The entries in row 3, columns 6 and 8, of your $A_5$ don't agree with your $A_n$. – Gerry Myerson Feb 27 '19 at 21:12
• @GerryMyerson you right. I made a mistake in typing. It will be edited. Thanks – Amin235 Feb 27 '19 at 21:17
• The pictured graph suggests switching each odd index $i$ with $2n - i$, giving a directed cycle graph plus some bidirectional edges. – user44191 Feb 28 '19 at 13:56
• Would you please define the matrix (or better corresponding directed graph) more explicitly? – Fedor Petrov Feb 28 '19 at 17:00
• @FedorPetrov The question based on your comment is edited. – Amin235 Feb 28 '19 at 17:31

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.

• Nice approach professor Petrov. I need to focus on you answer to find out its details. Just I have a question that want to ask you in the next comment. Thanks – Amin235 Mar 1 '19 at 20:33
• An extension of my question can be in the following form. Assume that the matrix ${\bf A}_n$ such that in the $i$th row(column) of ${\bf A}_n$ with $1\leq i \leq n$ we have exactly one matrix $\bf m$ and one matrix $\bf n$ and the other entries of the $i$th row(column) of ${\bf A}_n$ are filled with the $\bf z$ matrix. My question that you answered is a special case of this proposed extension. The matrix ${\bf A}_n$ with this new definition can be primitive or non-primitive matrix. – Amin235 Mar 1 '19 at 22:14
• My new question is that how changes should be done in your answer when we apply the new definition for ${\bf A}_n$. In other words, how should modify your interesting answer such that it detects whether ${\bf A}_n$ is a primitive matrix or non-primitive matrix? In addition, if the matrix ${\bf A}_n$ is a primitive matrix, the methodology of answer find the order of primitivity of ${\bf A}_n$. In fact, i would like to derive an algorithm to test primitivity of ${\bf A}_n$ when we apply this new definition for the matrix ${\bf A}_n$. Thanks in advance. – Amin235 Mar 1 '19 at 22:15
• I am not sure that I understand what exactly do you need. A fast algorithm? An explicit answer in terms of general matrix of such form? – Fedor Petrov Mar 2 '19 at 9:12
• I mean an explicit answer in terms of general matrix of such form. In fact the matrix ${\bf A}_n$ in the question, is constructed from two permutations $P=[n,n-1,\cdots,1]$ and $Q=[n-1.n-2,\cdots,1,n]$. I want to know that if we construct ${\bf A}_n$ from two permutations $P=[p_1,p_2,\cdots,p_n]$ and $Q=[q_1.q_2,\cdots,q_n]$ such that $p_i\neq q_i$ for all $1\leq i \leq n$, then how to obtain the primitive order of ${\bf A}_n$? For example by choosing $P=[n,n-1,\cdots,1]$ and $Q=[n-1.n-2,\cdots,1,n]$ the matrix ${\bf A}_n$ is a primitve matrix and its order is $n+2$ (as you proved).Thanks – Amin235 Mar 2 '19 at 9:28