[R] Generating a stochastic matrix with a specified second dominant eigenvalue

[David Winsemius]

On Oct 15, 2009, at 6:24 PM, Ravi Varadhan wrote:

> Hi,
>
> Given a positive integer N, and a real number \lambda such that 0 <  
> \lambda
> < 1,  I would like to generate an N by N stochastic matrix (a matrix  
> with
> all the rows summing to 1), such that it has the second largest  
> eigenvalue
> equal to \lambda (Note: the dominant eigenvalue of a stochastic  
> matrix is
> 1).
>
> I don't care what the other eigenvalues are.  The second eigenvalue is
> important in that it governs the rate at which the random process  
> given by
> the stochastic matrix converges to its stationary distribution.
>
> Does anyone know of an algorithm to do this?

I surely don't. My linear algebra is a distant and not entirely  
pleasant memory. I went searching and ended up at Google books reading  
a couple of texts on real analysis and stochastic matrices. Both  
citations reminded me that a matrix induces or implies a polynomial  
form over powers of <some> matrix (? constructed out of the basis  
vectors?) with the eigenvalues representing the coefficients. I  
believe that form can be solved for, but I don't know the process. It  
made me wonder if constructing a matrix out of powers of an  
appropriate stochastic basis would deliver the sought for resultant.  
Such a construction is outside my abilities.

-- 
David Winsemius, MD
Heritage Laboratories
West Hartford, CT