eigenvalue of Laplacian matrix

If we have a Laplacian matrix $\boldsymbol{A}$ such that \begin{align} &A_{ii} >0 \\ &A_{ii}=-\sum_{j\neq i}A_{ij} \end{align} with known eigenvalues $\lambda_i$.

Define the matrix $\boldsymbol{B} = \boldsymbol{A}+\boldsymbol{A}^\top$. Is there some criteria for entries of $\boldsymbol{A}$ to ensure that $\boldsymbol{B}$ is (semi-)positive definite?

-

Let $z$ be the vector with all entries equal to 1. If $Az=0$ and $B=A+A^T$, then $z^TBz=0$. Choose an orthogonal basis for $\mathbb{R}^n$ with $z$ as its first vector. If $C$ is the matrix representing $B$ relative to this basis, then $C_{1,1}=0$. Also $B$ is positive semidefiniteif and only if $C$ is.

If $C$ is positive semidefinite and $C_{1,1}=0$, all entries in the first row and column of $C$ must be zero. Let $C_1$ be the matrix we get by deleting the first row and column of $C$. Then $C$ is positive semidefinite if and only if the entries in its first row and column are zero and $C_1$ is positive semidefinite.

So we can reduce the question of whether an $n\times n$ matrix of the form $A+A^T$ is positive semidefinite to deciding whether an $(n-1)\times(n-1)$ matrix is positive semidefinite.

If $B$ is positive semidefinite and $z^TBz=0$, then $Bz=0$ and also $A^Tz=0$. So in terms involving only $B$, we can say that $B$ is positive semidefinite if and only if $Bz=0$ and the matrix representing the action of $B$ on the orthogonal complement to the span of $z$ is positive semidefinite.

The brief summary seems to be that knowing that $B=A+A^T$ with $Az=0$ does not give you much.

-
Thank you very much – user98883 Oct 14 '13 at 16:36

If $A$ is symmetric (i.e., the corresponding graph is undirected), then $B$ will always be positive semidefinite. This is true because every symmetric Laplacian matrix is positive semidefinite. And being symmetric it shares eigenvalues with its transpose. Specifically,

$$\lambda(A)_0 = \lambda(A^T)_0 \geq 0.$$

So the smallest eigenvalue of $B$ is given by

$$\lambda(B)_0 =\arg \min_x x^T(A+A^T)x=\arg \min_x x^TAx+x^TA^Tx = 2\lambda(A)_0 \geq 0$$

It follows that $B$ is positive semidefinite since it's eigenvalues are all non-negative.

-
Also: if $A$ is symmetric, $A=A^T$ and $B=2A$. – Federico Poloni Nov 10 '13 at 9:08

You want the numerical range, or field of values, of $A$ to be included in the right half-plane.

There is literature on computing and characterizing the numerical range, but not many explicit results, apart from normal matrices. It is known that it can extend arbitrarily large and far away from the eigenvalues; often it serves as a sort of condition number for numerical problems, so it may well be that it is an intrinsic difficulty in your case, too.

A graph Laplacian is an M-matrix. This terms can be useful for a literature search, for instance there is a quick reference to numerical radii of M-matrices on page 370 of Horn, Johnson, Topics in Matrix Analysis (remark: not the same book as the more known Matrix Analysis by the same authors). The same book contains a chapter on the field of values.

-