Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
I don't know what "the proper approach" is, but I would suggest a subgradient method, where the function to be minimized is the $L^2$ distance from the vector of eigenvalues to the multiplicity $n-1$ subset of $\mathbb{R}^n$. –  S. Carnahan Jun 14 '10 at 3:25
    
Thank you Scott for your comment. –  Zhi Ming Chen Jun 15 '10 at 11:01
1  
Which eigenvalue do you want to maximize? You could have a look at the definition of Colin de Verdiere's $\mu-$ invariant for graphs. It is defined as the maximal multiplicity of the second smallest eigenvalue under some stability condition for a Schroedinger operator associated to the graph. –  Roland Bacher Jun 15 '10 at 11:13
1  
Adding a scalar matrix simply shift the eigenvalues, so we might as well minimize the rank of the matrix. Having said that, the rank cannot go lower than the rank computed by considering minors that are "diagonal free", that is minors obtained by choosing k rows and k columns with no overlap. Not sure what else to say at the moment... –  damiano Jun 15 '10 at 12:58

1 Answer 1

up vote 1 down vote accepted

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 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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.