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?
How to prove that a matrix is positive definite?
2
$\begingroup$
linear-algebra
matrices
graph-theory
algebraic-graph-theory
topological-graph-theory
1 Answers
5
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.
-
0@XiangyuMeng: Darn, I totally missed that. I was getting your first answer wrong, and was only looking at the restrictions of $D$. Thanks! – 2012-07-23