Services & ResourcesWolfram ForumsMathGroup Archive

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

Limiting powers of stochastic and zero-one matrices

• To: mathgroup at smc.vnet.net
• Subject: [mg38818] Limiting powers of stochastic and zero-one matrices
• From: "Kumar Chellapilla" <kumarc at microsoft.com>
• Date: Tue, 14 Jan 2003 06:11:47 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

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

• Follow-Ups:
  • Re: Limiting powers of stochastic and zero-one matrices
    • From: Daniel Lichtblau <danl@wolfram.com>