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

Improve this question
$\endgroup$
5
  • $\begingroup$ The existence of such matrix is easy to prove, do you want to find it's coefficients? $\endgroup$
    – Kate Juschenko
    Commented 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$
    – Maria Kinget
    Commented 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$
    – Kate Juschenko
    Commented 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$
    – Brian Borchers
    Commented 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
    Commented Feb 24, 2011 at 21:55

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
0
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .