Question about the convergence of a stationary iteration procedure

[Gerardo Berbeglia]

Let A be an n x n matrix such that
- 0 <= (A)ij <= 1
- the sum over the values at a given column i is at most 1. (for all
columns i=1,...,n)

Let v be a n-dimension vector.

Consider the following stationary iteration procedure:
v_0 = v
v_k+1 = A*v_k.

Question: When does the limit when k->infinite of v_k converge? Does
it always converge? It is possible to give a nice characterization of
A and v for the limit to converge?

[Robert Israel]

Gerardo Berbeglia <gberb...@gmail.com> writes:

It does not always converge, e.g. consider the matrix
[ 0 1 ]
[ 1 0 ]
or more generally a permutation matrix.

It is always true that all eigenvalues of the matrix A have absolute
value <= 1. In order to have convergence for all v, you need all eigenvalues
not equal to 1 to have absolute value < 1. Note that by adding another
row and column, you can make A into the transpose of a stochastic matrix
P. The condition you want is that the Markov chain corresponding to
this stochastic matrix has no periodic recurrent class of states.
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada