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

[Jeff Newmiller]

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.

An idea...

Form a vector e of desired eigenvalues where the first eigenvalue is
1, the second is \lambda, and the remaining eigenvalues are whatever
is convenient (i*\lambda_i/(N-2) where i=0:(N-3) for example if repeated 
eigenvalues would be inconvenient). Then form A=diag(e) and modify it
to make the matrix stochastic by replacing the element just below
lambda_i with (1-lambda_i) until you get to the lambda_N, where A[1,N]
would be set to (1-lambda_N).

If \lambda=0.8, then we could form

e <- c(1, 0.8, 0.6, 0.4, 0.2)

then I think your desired matrix A is

A <- diag(e)
A[3,2] <- 1-e[2]
A[4,3] <- 1-e[3]
A[5,4] <- 1-e[4]
A[1,5] <- 1-e[5]
eigen(A)

-- 
---------------------------------------------------------------------------
Jeff Newmiller                        The     .....       .....  Go Live...
DCN:<jdnewmil at dcn.davis.ca.us>        Basics: ##.#.       ##.#.  Live Go...
                                       Live:   OO#.. Dead: OO#..  Playing
Research Engineer (Solar/Batteries            O.O#.       #.O#.  with
/Software/Embedded Controllers)               .OO#.       .OO#.  rocks...1k