# How to prove that a matrix is positive definite?

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?

-

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.

-
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