1
$\begingroup$

Is there an efficient algorithm to check the simultaneous feasibility of linear and eigenvalue constraints? For example, given $ \lambda_1 \ge \lambda_2 \ge 0$, is the following problem efficiently solvable : Are there $a_{ij} \ge 0$ such that

(i) $\sum_{i,j} a_{ij}=1$ such that $a_{ij} = a_{ji}$.

(ii) Largest eigenvalue of the matrix $A = [a_{ij}] = \lambda_1 $

(iii) All other eigenvalues of $A$ are upper bounded by $\lambda_2$ in magnitude.

It is okay if constraints (ii) and (iii) are satisfied with $\epsilon$ error.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is $A$ symmetric? $\endgroup$
    – Suvrit
    Oct 5, 2013 at 17:34
  • $\begingroup$ Yes, A is symmetric. I added the condition now. $\endgroup$
    – Anindya De
    Oct 6, 2013 at 1:59
  • $\begingroup$ It seems to me that this might not be writable as an SDP---but I haven't had time to think about it properly yet. $\endgroup$
    – Suvrit
    Oct 6, 2013 at 2:02
  • $\begingroup$ I feel that if $\lambda_1$ is small enough, then there should always be a matrix that satisfies these constraints; the $a_{ij} \ge 0$ is the twist seems to make things harder.... $\endgroup$
    – Suvrit
    Oct 6, 2013 at 22:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.