3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – S. Carnahan Jun 14 '10 at 3:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Roland Bacher Jun 15 '10 at 11:13
  • 1
    $\begingroup$ 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... $\endgroup$ – damiano Jun 15 '10 at 12:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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