10
$\begingroup$

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! :-)

$\endgroup$
5
  • $\begingroup$ The existence of such matrix is easy to prove, do you want to find it's coefficients? $\endgroup$ Feb 10, 2011 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$ Feb 10, 2011 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$ Feb 10, 2011 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$ Feb 11, 2011 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, 2011 at 21:55

2 Answers 2

3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
5
  • $\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$ Feb 10, 2011 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, 2011 at 20:36
  • $\begingroup$ @Tracy: How does P-F tell you that the smallest eigenvalue is real? $\endgroup$
    – Igor Rivin
    Feb 10, 2011 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, 2011 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$ Feb 10, 2011 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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