5
$\begingroup$

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

enter image description here

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

enter image description here

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

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Amin235 Mar 1 '19 at 20:33
  • $\begingroup$ 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. $\endgroup$ – Amin235 Mar 1 '19 at 22:14
  • $\begingroup$ 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. $\endgroup$ – Amin235 Mar 1 '19 at 22:15
  • $\begingroup$ 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? $\endgroup$ – Fedor Petrov Mar 2 '19 at 9:12
  • $\begingroup$ 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 $\endgroup$ – Amin235 Mar 2 '19 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.