Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:02:41Z http://mathoverflow.net/feeds/question/55065 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/55065/maximizing-the-smallest-eigenvalue-of-a-diagonally-dominant-matrix Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix Maria Kinget 2011-02-10T18:49:03Z 2011-09-26T22:22:12Z <p>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: $$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 |$$</p> <p>We also have a positive diagonal matrix $D$ whose trace is constant and equal to $K$: $$d_{ij}=0 \textrm{ for } i \neq j \qquad d_{ii} \geq 0 \quad \textrm{and } \quad K=\sum_{i}d_{i,i}$$</p> <p>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! :-)</p> http://mathoverflow.net/questions/55065/maximizing-the-smallest-eigenvalue-of-a-diagonally-dominant-matrix/55072#55072 Answer by user for Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix user 2011-02-10T20:17:44Z 2011-02-10T20:22:49Z <p>Maximize what? The smallest eigenvalue is complex... Do you want to maximize the absolute value of the smallest eigenvalue?</p> http://mathoverflow.net/questions/55065/maximizing-the-smallest-eigenvalue-of-a-diagonally-dominant-matrix/59829#59829 Answer by Dan for Maximizing the Smallest Eigenvalue of a Diagonally Dominant Matrix Dan 2011-03-28T13:05:16Z 2011-03-28T13:05:16Z <p>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):</p> <p>max lambda such that: A + D >= lambda I Trace(D) = K D_{ii} >= 0</p> <p>where the first '>=' denotes 'greater-or-equal in the cone of positive semidefinite matrices', and I is the identity matrix. </p> <p>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</p>