Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $L$ be a Laplacian matrix of a strong connected and balanced directed graph. Define $$ L^{s}=\frac{1}{2}\left( L+L^{T}\right) .$$ Let $D$ be a diagonal matrix with $$ D=\begin{bmatrix} d_{1} & & & \\ & d_{2} & & \\ & & \ddots & \\ & & & d_{n}% \end{bmatrix}, $$ with $d_{i}\geq 0.$ There is at least one $d_{i}>0$. Clearly, this matrix is positive semi-definite. Is the matrix $ L^{s}+D $ positive definite or not?

share|cite|improve this question
up vote 5 down vote accepted

Take any nonzero $\mathbf{x}\in\mathbf{R}^n$ and let $\mathbf{x}=(x_1,x_2,\dotsc ,x_n)$.


$\quad \mathbf{x} L_s\mathbf{x}^t=\sum_{ij} (x_i-x_j)^2 > 0$,

where the sum is taken over the edges of the graph (edges without orientation), which shows that $L_s$ is positive definite (the graph is strongly connected). On the other hand $D$ is clearly positive semi-definite, and hence the addition of both matrices is positive definite.

share|cite|improve this answer
Thanks for A.Schulz's answer. I got some hint from you. The matrix $L^{s}+D$ is positive definite, not just positive semi-definite. Follow A.Schulz's proof, we have $ x\left( L^{s}+D\right) x=\sum_{ij}\left( x_{i}-x_{j}\right) ^{2}+\sum_{i}d_{i}x_{i}^{2} $. Suppose $d_{i}$ is positive. If $x\left( L^{s}+D\right) x=0$, then $x_{i}=0$, then the graph is strongly connected, then all $x_{j}=0$. Thus we get that $L^{s}+D$ is positive definite. – Xiangyu Meng Jul 22 '12 at 3:29
@XiangyuMeng: Thanks, I have missed the fact that the one of the $d_i$s is positive. I edited the answer. – A.Schulz Jul 22 '12 at 5:33
I don't know exactly what you missed (that at least one of the $d_i$ is positive, or that all the others can be zero), but in any case $D$ is only positive semi-definite; it is definitely :-) not "clearly positive definite". – Marc van Leeuwen Jul 22 '12 at 8:43
@MarcvanLeeuwen Thanks for the pointer. – A.Schulz Jul 22 '12 at 17:25
We cannot allow that the graph contains no edges at all since the graph is strongly connected. – Xiangyu Meng Jul 22 '12 at 21:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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