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

Jeff Newmiller jdnewmil at dcn.davis.ca.us
Sat Oct 17 09:23:23 CEST 2009

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
A[4,3] <- 1-e
A[5,4] <- 1-e
A[1,5] <- 1-e
eigen(A)

--
---------------------------------------------------------------------------
Jeff Newmiller                        The     .....       .....  Go Live...
DCN:<jdnewmil at dcn.davis.ca.us>        Basics: ##.#.       ##.#.  Live Go...