Hi,


We have a real, non-singular and symmetric matrix M of size n by n, with diagonal elements 0's. Its eigenvalues and eigenvectors are computed.


Now we wish to change its diagonal elements arbitrarily to maximize the multiplicy of an eigenvalue ( unnecessary to be the same value with old one). 


For example, let n be even, M=ones(n)-diag(ones(n,1)), then
n-1 is the largest. The modification is unnecessary.
 $\lambda$1>$\lambda$2=$\lambda$3=...=$\lambda$n


Is the powerful convex programming the proper approach to solve this problem?


I try to creat a more complicated example M of interger entries ( small n ), but it seems to be hard...


To transform a model to convex programming is not easy either... :)


Thank you for your help


Zhi Ming



Maximize the multiplicity of an eigenvalue
Let $W = M + D$, where $M$ is the original $n \times n$ matrix and $D$ is the added diagonal matrix that we want to determine.


$W$ is symmetric, thus diagonalizable by an adjoint action of the orthogonal group.
Larger multiplicities in the eigenvalues of $W$ imply smaller dimensions of the adjoint orbits.


For example, if we have an eigenvalue of multiplicity $n-1$, then the adjoint orbit will be
$O(n)/(O(n-1) \times O(1)) = S^{n-1}/Z\_2 = RP^{n-1}$ of dimension $n-1$; 
while, if all the eigenvalues are distinct, the adjoint orbit is the real flag manifold $Fl\_{\mathbb{R}}^n = O(n)/(Z\_2)^n$ of dimension $ \frac{n(n-1)}{2}$. (Of course, in the case of scalar multiple of the unit matrix, the adjoint orbit is just a single point).


Thus in order to achieve large multiplicities, we need to minimize the dimension of the adjoint orbit.
This problem can be reduced to a problem of matrix rank minimization as follows:


Let $\{l\_i \}\_{i=1,...,n(n-1)/2}$, be a set of generators of the Lie algebra of $O(n)$ normalized according to:
$\textrm{tr}(l\_i l\_j) = \delta\_{ij}$. The dimension of the adjoint orbit equals the rank of the Gram matrix $C$ whose elements are given by, $C\_{ij} = \textrm{tr}([l\_i, W][l\_j, W])$. The problem is thus reduced to the minimization of the rank of the Gram matrix whose elements depend linearly on the added diagonal matrix elements.


One of the possible methods to solve this problem is through a convex programming 
heuristic approach for the solution of matrix rank minimization,
based on replacing the rank by the nuclear norm (the sum of the singular values), as explained in the following [lecture notes](http://temple.birs.ca/~10w5007/parrilo.pdf) by: P.A. Parillo. The nuclear norm is a convex envelope of the rank which may explain why this method works well in practice in general.


