# Big eigenvalues of a special stochastic matrix

Given a matrix $M$ of size $n\times n,$ we write its different eigenvalues by $x_1,x_2,\ldots,x_m$ with $m\leq n$ such that $|x_1|>|x_2|>|x_3|>\cdots|x_m|,$ and call $x_2\doteq |\lambda_2|(M).$

Given an integer $n>2,$ we consider a set of indices $S\subset \{(x,y):x,y \in\{1,2,...,n\} \}$ such that $(x,y)\in S\setminus \left(\{n\}\times\{1,2,..,n\}\cup\{1,2,..,n\}\times\{n\}\right)\Rightarrow (x,z)\in S, \forall z\in \{y+1,...,n\}$ and $\forall x\in\{1,2,...,n\}, \exists z\in\{1,...,n-1\}: (x,z),(x,z+1)\in S.$

Now I fix a set $S$ as above, take $\epsilon>0$ small and I write an optimisation problem:

$\max |\lambda_{2}|(M)-M_{(1,1)}$

such that

$M_{(1,1)}\geq M_{(x,y)},$ $\forall(x,y),x,y\in\{1,2,\ldots,n\},$

$M_{(x,y)}=0,$ $\forall (x,y)\in S,x,y\in\{1,2,\ldots,n\},$

$\sum_{y:(x,y)}M_{(x,y)}=1,$ $\forall x\in\{1,2,\ldots,n\},$

$\epsilon\leq M_{(x,y)}\leq1-\epsilon,$ $\forall(x,y)\notin S,$

$M_{(x,x)}=M_{(x+1,x+1)},$ $\forall(x,x)\notin S\cup \{(1,1),(n,n)\}.$

We call $M_{S,\epsilon}$ to its maximum (it exists, because the function to maximize is continuous (it is in particular well defined in this domain, because the second eigenvalue always exists) and the domain a closed (also convex) set). My question is if there is some idea to solve it. Or if is it possible to say something about its solutions, for example, can we determine $S$ such that $M_{S,\epsilon}>0$ for any $\epsilon>0$ small enough.

-
Trivial comments: 1) It isn't guaranteed that a second eigenvalue exists (e.g. the identity matrix) 2) It seems that $S = [n]x[n]$ is allowed. It seems that condition 2 implies $M_{(1,1)} = 0$, so then we would have $M_{S} > 0$ when it makes sense. 3) What is $\epsilon$? Doesn't the fourth condition contradict the second? In condition three, are you missing $\in S$ in the subscript for the sum? Less trivially: It would be helpful to know a little about what you have tried, where this comes from, what you expect to be true, what would be `good enough,' etc. – qams3 May 17 '13 at 13:47
It is possible to prove that for this $S$ the second eigenvalue always exists. So the problem is well defined. – Umberto May 17 '13 at 14:29