Consider two (not identical) symmetric Laplacian matrices $L_1$ and $L_2$ and a diagonal matrix $D > 0$. My question is if the eigenvalues of the product $A =L_1 D L_2$ have non-negative real-part. It is well known that the product of two positive semi-definite matrices have eigenvalues with non-negative real part. (see e.g. the book by Bernstein: Matrix Mathematics, Theory, Facts, and Formulas). Extensive simulations show that $A$ has indeed eigenvalues with non-negative real part and that this not true in general if $L_1$ and $L_2$ were `only' positive semi-definite matrices. However, I have been, trying similarity transformations and Sylvester's law of inertia, unable to find a proof. Of course, a counterexample would be very useful as well.


The answer is no. A random counterexample: the eigenvalues of $$ A=\pmatrix{1&0&-1\\ 0&1&-1\\ -1&-1&2} \pmatrix{1\\ &3\\ &&1} \pmatrix{2&-1&-1\\ -1&1&0\\ -1&0&1} =\pmatrix{3&-1&-2\\ -2&3&-1\\ -1&-2&3} $$ are $0$ and $\frac12(9\pm i\sqrt{3})$, so $A$ has non-real eigenvalues. When the matrix sizes are larger (such as $5\times5$), we can even obtain easily a counterexample in which $A$ has a negative real eigenvalue.

Edit. Another counterexample: the matrix product \begin{align*} A&=\pmatrix{ 1& 0& 0&-1& 0\\ 0& 2&-1& 0&-1\\ 0&-1& 2& 0&-1\\ -1& 0& 0& 1& 0\\ 0&-1&-1& 0& 2} \pmatrix{1\\ &3\\ &&3\\ &&&3\\ &&&&3} \pmatrix{ 2&-1& 0& 0&-1\\ -1& 2& 0& 0&-1\\ 0& 0& 1&-1& 0\\ 0& 0&-1& 1& 0\\ -1&-1& 0& 0& 2}\\ &=\pmatrix{ 2&-1& 3&-3&-1\\ -3&15&-3& 3&-12\\ 6&-3& 6&-6&-3\\ -2& 1&-3& 3& 1\\ -3&-12&-3& 3&15}, \end{align*} has an eigenpair $(\lambda,v)$ where $\lambda\approx-0.2111<0$ and $v\approx(0.46902,\,0.30552,\,-0.61103,\,-0.46902,\,0.30552)^T$.

  • $\begingroup$ Thank you. I clarified my question that I meant with non-negative, non-negative real part. Can you provide an example where $A$ has a negative real eigenvalue? You mention that it is easy, but unfortunately I do not find one. $\endgroup$ – galirt Oct 1 '17 at 15:10
  • $\begingroup$ @galirt Not meant to be rude, but for 5-by-5 matrices, it is indeed easy to obtain a counterexample with a real negative eigenvalue. There may be some limitations in the simulations you've done. $\endgroup$ – user1551 Oct 1 '17 at 16:41
  • $\begingroup$ Thanks. I have rerun my simulations, and I find indeed examples when the Laplacians (at least one) do not correspond to connected graphs (like your example). Initially, I excluded this possibility in my simulations as my associated graphs are always connected. Do you think this absence of connectivity is essential to find a counterexample? $\endgroup$ – galirt Oct 2 '17 at 11:36
  • $\begingroup$ @galirt It's quite plausible. I cannot obtain a counterexample (for matrices with sizes $\le8$) with a connected graph too. $\endgroup$ – user1551 Oct 4 '17 at 14:23

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.