Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer

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.