"(Dear me! I am not certain quite
That even now I've got it right!)"
- "Eletelephony", by Laura Elizabeth Richards
Dan has pointed out that I still didn't pose my problem correctly,
so let me see if I can finally get it straight:
Let's say a stochastic matrix A is posipotent if some power of A
has all its entries positive. (This is Dan's nice coinage; I had
used the standard but bulkier phrase "irreducible and aperiodic".)
For each positive integer n > 0, what is the maximum value of N
for which there exists an n-by-n posipotent stochastic matrix A
and a probability vector v such that the vector A^N v has all its
entries positive but the vectors
v , A v , A^2 v , ... , A^(N-1) v
do not?
This can be shown to be equivalent to the following question:
For each positive integer n > 0, what is the maximum value of N
for which there exists an n-by-n posipotent stochastic matrix A
such that the matrix A^N has all its entries positive but the
matrices
I , A , A^2 , ... , A^(N-1)
do not?
This can also be recast as a combinatorial question. Suppose
we restrict attention to finite directed graphs with n vertices
with the property that for every ordered pair of vertices (v,w)
there is a way to get from v to w in exactly M moves. Define
the "inconvenience" of such a digraph as the smallest M that
works for all v,w. How large can the inconvenience be? (Note
that we are limiting ourselves to directed graphs for which
there exists a universal M such that for every ordered pair
of vertices (v,w) you can get from v to w in M moves. Of
course, if M is a number with this property, so is M+1.)
To clarify what I mean by "moves": When I say "There is a way to
get from v to w in exactly K moves" I mean "There exists a sequence
of not necessarily distinct vertices v = v_0, v_1, ..., v_K = w
such that for each j in {1,2,...,K-1} there is a directed edge
from v_{j-1} to v_j."
Example: Consider the direct graph on 4 vertices {A,B,C,D} with
edges A->B, B->C, C->D, D->A, and D->B. Then, starting from A,
the vertices that are reachable in a specified number of moves
are as follows:
In 1 move: B
In 2 moves: C
In 3 moves: D
In 4 moves: A,B
In 5 moves: B,C
In 6 moves: C,D
In 7 moves: A,B,D
In 8 moves: A,B,C
In 9 moves: B,C,D
In 10 moves: A,B,C,D
So we have shown that the inconvenience of this digraph is
at least 10.
Correspondingly, consider the matrix and vector
( 0 1 0 0 ) ( 1 )
( ) ( )
( 0 0 1 0 ) ( 0 )
A = ( ) , v = ( ) ;
( 0 0 0 1 ) ( 0 )
( ) ( )
(1/2 1/2 0 0 ) ( 0 )
A^10 v has all its entries positive, but A^9 v does not.
Here is a proof that the inconvenience can be at most 2^n-2:
Each probability vector can be represented by an n-tuple of
0's and +'s, where 0 stands for 0 and + stands for any positive
number. Call this the signature of the vector. It is easy to see
that the signature of a vector v determines the signature of its
image A v. If the 2^n - 1 vectors v , A v , A^2 v , ... ,
A^(2^n-2) v all have signatures different from (0,0,...,0) and
(+,+,...,+), then by the pigeonhole principle two of the vectors
must have the same signature. But then the sequence of signatures
must cycle forever and never hit (+,+,...,+), which contradicts
our assumptions. So either (0,0,...,0) must occur (which is
impossible since all our vectors are probability vectors) or
(+,+,...,+) must occur (in which case that signature recurs
forever after). Hence, for every v, A^(2^n-2) v has all
its entries positive.
Clearly one can do better than the upper bound N(n) leq 2^n - 2.
My question is, how much better can one do?
Jim Propp
