Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer 1

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)$.

Then

$\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|improve this answer
1  
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
show 1 more comment

Your Answer

 
discard

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.