MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.