Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Limiting powers of stochastic and zero-one matrices

• To: mathgroup at smc.vnet.net
• Subject: [mg38835] Re: [mg38818] Limiting powers of stochastic and zero-one matrices
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Wed, 15 Jan 2003 02:20:17 -0500 (EST)
• References: <200301141111.GAA26294@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Kumar Chellapilla wrote:
> 
> Hi,
> 
> I am interested in determining where the zero and non-zero entries
> occur in the powers of stochastic matrices in the limit as the power ->
> infinity.
> 
> If A = {a_ij} and B = {b_ij} are stochastic matrices
> i.e., all non-negative (zero or positive) entries, rows sum to 1.0,  max eig
> value = 1.0,
> all other eigen values have abs(eigval) < 1, which gives us
>             A^\inf and B^\inf are both rank-1 matrices
> 
> (where A^\inf = lim_{n -> \inf}{A^n})
> 
> Let I(A) and I(B) be the indicator matrices ( (0,1) matrices) of A, and B,
> resp.
> where I(A) = {I_ij}, with
> I_ij = 1, if a_ij > 0 and
> I_ij = 0, if a_ij = 0
> 
> Now suppose I(A) = I(B),
> which gives us I(A^n) = I(B^n),
> Can we show that
> I(A^inf) = I(B^inf)            - Eqn (1)
> 
> Note that Eqn (1) is NOT TRUE in general (for non-stochastic matrices):
> E.g.
> A = [0.1 0.1; 0.1 0.1]
> B = [0.3 0.7; 0.3 0.7]
> 
> I(A) = I(B) = [1 1; 1 1]
> 
> A^inf = [0 0; 0 0]
> B^inf = B
> 
> I(A^inf) = [0 0; 0 0]
> I(B^inf) = [1 1; 1 1]
> 
> Thus I(A^inf) is not equal to I(B^inf)
> 
> Thank you,
> Kumar

I don't have a general answer offhand but I'll note that your rank-1
claim only holds generically. For (counter)example, if you take A to be
the identity matrix of whatever dimension, it is stochastic and A^inf ==
A has full rank. If you take, say, A = {{0,1},{1,0}} then A^inf does not
even exist.

For the (generic) regular case, i.e. all entries nonzero, you do have a
rank 1 infinite power. It is given as the matrix whose rows are
normalized null vectors of Transpose[(A - IdentityMatrix[Length[A]]];
the null vector is unique up to scaling and so you scale to have row sum
equal to one (since A^inf is stochastic).

In this case it is easy to show that no value is zero. Say the first
element in the null vector were zero. Then it's dot product with the
first column of A-IdentityMatrix cannot be zero because that column only
has a negative in the first element and all other elements are strictly
positive. Same argument shows no element in the null vector is zero. To
cast this in your terminology, if A is stochastic and I(A) consists
entirely of 1's, then A^inf has rank equal to 1 and all nonzero
elements.

When the matrix A has zero elements it may be a different matter. I
imagine this is well understood, but not by me.


Daniel Lichtblau
Wolfram Research

• Follow-Ups:
  • Re: Re: Limiting powers of stochastic and zero-one matrices
    • From: Dr Bob <majort@cox-internet.com>

• References:
  • Limiting powers of stochastic and zero-one matrices
    • From: "Kumar Chellapilla" <kumarc@microsoft.com>