Timeline for Maximize sum of largest eigenvalues
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 28, 2011 at 11:22 | vote | accept | Kap | ||
| Oct 26, 2011 at 1:11 | comment | added | Noah Stein | There may well be, but I am not familiar with them. Good luck! | |
| Oct 25, 2011 at 20:53 | comment | added | Kap | I think I will try to study it with the eigenvalue decomposition $X = UDU$, and try to see how the orthogonal matrix $U$ impacts on the slope of the eigenvalue hyperplanes. So I guess there are no references for this type of problem somewhere? | |
| Oct 25, 2011 at 14:44 | comment | added | Kap | Maybe one could argue that if the solution of a certain rank is not uniquely defined by the planes, then one could decrease the linear objective function even more by perturbing the eigenvectors. | |
| Oct 25, 2011 at 13:48 | comment | added | Kap | Yes you're right, I have changed the description now. As you see, for some $d_j$, I can prove the optimal $X$ should have rational entries (so it's integer up to a scaling), because the optimum is then at the vertices of the hyperplanes. I suspect the same structure holds even for lower rank $X$. | |
| Oct 25, 2011 at 13:10 | comment | added | Noah Stein | Are you only interested in those particular values of $c_j$ and $v_j$? I haven't thought about them in particular, only the general case which you originally asked about. Also, why do you expect the optimal solution should be integral? It is helpful to include such additional conditions and preliminary results in the statement of the question when possible. | |
| Oct 25, 2011 at 12:28 | comment | added | Kap | Also, note that the matrices you wrote have integer entries (because you assumed integer vectors and constants), which I think should hold for the optimal matrix. I can explain why $X$ should have integer entries if the solution is full rank, because then it satisfies a set of integer equations. But for the lower rank, I'm not completely sure. | |
| Oct 25, 2011 at 11:59 | vote | accept | Kap | ||
| Oct 25, 2011 at 11:59 | |||||
| Oct 25, 2011 at 10:51 | comment | added | Kap | Thank you very much for your answer Noah. But let's say I have all $c_j = 1$ and vectors $v_j$ such that each of their element can be $-1,0,1$, so that there are $3^n - 1$ vectors in total (the all zero vector is not included). Then the matrices you presented don't satisfy the constraints. So you think it is still possible to find other low rank matrix solutions that are not defined uniquely from our planes? | |
| Oct 24, 2011 at 23:17 | comment | added | Noah Stein | The place where spanning does come in with respect to the constraints is that the problem is bounded if and only if the $v_j$ span $\mathbb{R}^n$. This doesn't seem particularly relevant to your question but I can add a proof if you'd like, or you can ask it separately. | |
| Oct 24, 2011 at 23:16 | history | answered | Noah Stein | CC BY-SA 3.0 |