0

This example in Stephen Boyd's Convex Optimization book says that the following matrix is element-wise positive and therefore $x^TQx$ is semi-definite where $Q=W - \lambda_{min}(W)(I) \succcurlyeq 0$.

The example appears in Sec. 5.1.5, just before equation 5.8.

There's also no mention of what specifically is $\lambda_{min}$. If $\lambda_{min} \succcurlyeq 0$ then $Q$ should be element-wise less than 0.

enter image description here

sprajagopal
  • 622
  • 1
  • 5
  • 20

1 Answers1

1

For any symmetric matrix $M$, if $\lambda_1\geq \ldots\geq \lambda_n$ are the eigenvalues (which exist by the spectral theorem), then the eigenvalues of $M-\lambda_n I$ are just $\lambda_i-\lambda_n$. These are all nonnegative, so this new matrix is positive semi-definite. It has nothing to do with element-wise nonnegativity.

J.G
  • 5,084
  • Thanks! But I have a few more follow-up questions. Is $M-\lambda_n I$ equivalent to $W - \lambda_{min}(W)I$? I'm confused because it's not $W-\lambda_{min}I$. Also, I interpreted $\succcurlyeq$ as element-wise inequality (in this textbook, it seems to be the meaning). Isn't that a necessary condition for $M$ to be positive semidefinite? – sprajagopal Sep 03 '19 at 17:14
  • 1
    $\lambda_{min}(W)$ refers to the smallest eigenvalue of $W$. $\succeq$ refers to the PSD (Loewner) partial order, i.e. $A\succeq B$ iff $A-B$ is positive semi-definite. Element-wise nonnegativity of a symmetric matrix $M$ is neither necessary nor sufficient for $M$ to be positive semi-definite (I'd encourage you to find simple $2\times 2$ examples! It's easy to test in this case as a $2\times 2$ matrix is psd iff it has nonnegative trace and determinant). – J.G Sep 03 '19 at 17:34