Assume that we have a full-rank diagonally dominant matrix $A$, all the diagonal elements of which are positive, all the non-diagonal elements are negative, and the sum of the absolute values of the non-diagonal elements is equal to the diagonal element. More precisely: \begin{equation} A=[a_{i,j}] \qquad a_{i,i}>0 \qquad a_{i,j} \leq 0 \textrm{ for $i \neq j$} \quad \textrm{and } \quad a_{i,i}=\sum _{j\neq i}|a_i,_j | \end{equation}

We also have a positive diagonal matrix $D$ whose trace is constant and equal to $K$: \begin{equation} d_{ij}=0 \textrm{ for } i \neq j \qquad d_{ii} \geq 0 \quad \textrm{and } \quad K=\sum_{i}d_{i,i} \end{equation}

What is the matrix $D$ such that the smallest eigenvalue of the matrix sum $T=A+D$ is as large as possible? In other words, how can we find the $d_{ii}$ 's such that we maximize the smallest eigenvalue of $T=A+D$? Thank you all in advance! :-)

  • $\begingroup$ The existence of such matrix is easy to prove, do you want to find it's coefficients? $\endgroup$ – Kate Juschenko Feb 10 '11 at 22:05
  • $\begingroup$ We need to find the elements of the diagonal matrix $D$, such that the real part of the eigenvalue with the smallest real part is as large as possible. If finding this matrix is easy, could you please give me some pointers on where to look? Thanks! :-) $\endgroup$ – Maria Kinget Feb 10 '11 at 23:18
  • $\begingroup$ Because everything acts on a finite-dimensional Hilbert space such matrix always exists. I don't know how to find it's coefficients. $\endgroup$ – Kate Juschenko Feb 10 '11 at 23:58
  • $\begingroup$ The smallest eigenvalue (or the real part of the eigenvalue with smallest real value) of a matrix is a nonconvex function of the matrix. Thus I would expect this to be a hard nonconvex optimization problem unless something special about the additional structure of your problem simplifies things. $\endgroup$ – Brian Borchers Feb 11 '11 at 0:53
  • 4
    $\begingroup$ You say the matrix $A$ has full rank, but all the row sums are zero, so that the all-ones vector is an eigenvector with eigenvalue $0$. So $A$ can't be full rank. $\endgroup$ – alex Feb 24 '11 at 21:55

If the A matrix were symmetric (so the eigenvalues are real), then you could just solve a semidefinite programming problem (SDP) to find the matrix D (and 'lambda'). In particular, maximizing the smallest eigenvalue ('lambda') of the matrix A + D in your case would be equivalent to the SDP (over variables D and lambda):

max lambda such that: A + D >= lambda I Trace(D) = K D_{ii} >= 0

where the first '>=' denotes 'greater-or-equal in the cone of positive semidefinite matrices', and I is the identity matrix.

There are several MATLAB-based packages in which you can formulate and solve problems like this (for instance, Yalmip and CVX). You'll probably also need a solver for SDPs (e.g., sedumi or sdpt3). Good luck, -Dan


Maximize what? The smallest eigenvalue is complex... Do you want to maximize the absolute value of the smallest eigenvalue?

  • $\begingroup$ The question states that the entries of A and D are real (and even states what their signs should be). So, if A is symmetric, then the eigenvalues will be real. (The nonsymmetric case seems less natural, although you could study it as well.) $\endgroup$ – DES-SupportsMonicaAndTransfolk Feb 10 '11 at 20:35
  • 3
    $\begingroup$ Wrong on three counts: The smallest eigenvalue is real, by Perron-Frobenius. The convention chosen in the question has row sum zero, so actually the all-ones vector is a right eigenvector. Choosing equal diagonal entries is not always the best you can do, as you can see by the example $A = \left[\begin{array}{rr}1 & -1\\\\ 0 & 0 \end{array}\right]$ and $K=1$. $\endgroup$ – Tracy Hall Feb 10 '11 at 20:36
  • $\begingroup$ @Tracy: How does P-F tell you that the smallest eigenvalue is real? $\endgroup$ – Igor Rivin Feb 10 '11 at 20:39
  • $\begingroup$ @Igor: Apply it to $tI -A-D$ for large enough positive $t$, such as $t=\mathrm{tr}(A)+K$. $\endgroup$ – Tracy Hall Feb 10 '11 at 20:55
  • $\begingroup$ We need to maximize the real part of the eigenvalue with the smallest real part. Thanks for pointing this out! :-) $\endgroup$ – Maria Kinget Feb 10 '11 at 21:28

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.