3
$\begingroup$

For a matrix $M\in\mathbb{R}^{n\times n}_{\geq 0}$ with nonnegative entries, we define $m$ as the smallest positive integer such that all the entries of $M^m$ are strictly positive (if there is one).

What is, as a function of $n$, the maximum possible (finite) value of $m$ over all possible choices of $M$?

My attempt: By taking the matrix $M(i,i+1)=M(1,1)=M(1,n)=1$ else $M(i,j)=0$ I got $m=6,12,18$ for $n=4,7,10$. So it seems that $m=2n-2$?

I added the "probability" tag because Markov chain convergence was the motivation.

Improve this question
$\endgroup$
4
  • $\begingroup$ By the way, maybe the following strategy may be of use: since you can assume that all elements of the initial matrix are 0 or 1, you can brute-force this $m(n)$ on a computer at least for n=1,2,3,4,5 (maybe 6 too - there are $2^{n^2}$ matrices). And then look up that sequence on oeis.org $\endgroup$
    – Serguei Popov
    Commented Nov 29, 2016 at 15:38
  • 2
    $\begingroup$ If you are looking for the relation between the minimum power such that a primitive matrix is strictly positive and the size of the matrix, look at H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950). The paper arxiv.org/abs/1302.5793 summarizes some of the results. $\endgroup$
    – Benjamin Steinberg
    Commented Nov 29, 2016 at 16:08
  • $\begingroup$ Or try ac.els-cdn.com/S0024379502004147/… $\endgroup$
    – Benjamin Steinberg
    Commented Nov 29, 2016 at 16:10
  • 2
    $\begingroup$ See math.stackexchange.com/questions/450090/… for a detailed discussion and references. $\endgroup$
    – Gerry Myerson
    Commented Nov 29, 2016 at 22:35

2 Answers 2

Reset to default
3
$\begingroup$

This is a combination of the answer Gerry Myerson gave on MSE, the paper linked there, and the comments here.

The largest possible minimum $m$ is $(n-1)^2+1 = n^2-2n+2$. This was proved by Wielandt, although this proof was not published. He claimed the result in H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z., 52, 642–648 (1950). There is an essentially unique matrix showing that this is sharp, although there are many examples built from similar ideas showing that the minimum $m$ is $\Omega(n^2)$.

$$\begin{pmatrix}0 & 0 & \cdots & 0 & 1 \newline 1 & 0 & \cdots & 0 & 0 \newline \epsilon & 1 & \cdots & 0 & 0 \newline \vdots & \vdots & \ddots & \vdots \newline 0 & 0 & \cdots & 1 & 0 \end{pmatrix}$$

Except for the $\epsilon$, this is a circulant matrix.

For example, let $n=8$, and set $\epsilon=1$. Here is the $40$th power:

$$\begin{pmatrix}1 & 0 & 0 & 1 & 5 & 10 & 10 & 5 \newline 5 & 1 & 0 & 0 & 1 & 5 & 10& 10 \newline 15 & 5 & 1 & 0 & 1 & 6 & 15 & 20 \newline 20 & 10 & 5 & 1 & 0 & 1 & 6 & 15 \newline 15 & 10 & 10 & 5 & 1 & 0 & 1 & 6\newline 6& 5& 10 & 10 & 5 & 1 & 0 & 1 \newline 1 & 1 & 5 & 10 & 10 & 5 & 1 & 0 \newline 0 & 0 & 1 & 5 & 10 & 10 & 5 & 1 \end{pmatrix}$$

Here is some Mathematica code you can use to animate the powers of the matrix.

wmat[n_] := Table[If[Mod[i - j, n] == 1 || (i == 2 && j == 0), 1, 0], {i, 0, n - 1}, {j, 0, n - 1}]
ListAnimate[Table[TableForm[MatrixPower[wmat[8], i]], {i, 1, 50}]]
Improve this answer
$\endgroup$
1
$\begingroup$

There is an example in the book "Essentials of Stochastic processes" of Durrett, which shows that, in general, $m$ need not be equal to $2n-2$ (it is Example 4.5 of the chapter devoted to Markov chains, Durrett calls this example "Mathematician's nightmare"). The state space of the chain is $\{0,1,\ldots,14\}$, from $0$ it jumps to $5,9,14$ with equal probabilities, from other states $x>0$ it always jumps to $x-1$. It is then claimed that $m$ is at least $30$ for this chain (I didn't do the calculations myself, though).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .