# Positive semidefinite decomposition, Laplacian eigenvalues, and the oriented incidence matrix

Suppose $A\in\mathbb{C}^{n\times n}$ is Hermitian and positive semidefinite with some decomposition $A=BB^*$, where $B=(b_{ij})\in\mathbb{C}^{n\times m}$ (not necessarily the Cholesky decomposition).

Question: is there a nice relationship between the row/column sums of $B$ and the eigenvalues of $A$? Specifically, can we obtain lower bounds for the largest eigenvalue of $A$ with the one of the following forms (or similar in nature):

(1) $\displaystyle\max_{1\leq j\leq n}\sum_{k=1}^mb_{jk}$ + $\displaystyle\min_{1\leq k\leq m}\sum_{j=1}^n b_{jk}$ - 1 $\leq \lambda_{\max}(A)$.

OR

(2) $\displaystyle\max_{1\leq j\leq n}\sum_{k=1}^m|b_{jk}|$ + $\displaystyle\min_{1\leq k\leq m}\sum_{j=1}^n |b_{jk}|$ - 1 $\leq \lambda_{\max}(A)$.

Obviously $B$ would need to have some special condition in (1) to make sure these sums are real. Perhaps this is too strong, but it would be useful to have such a relationship. Here is some possible motivation:

The Laplacian matrix of a simple graph $G$ can be written as $L(G)=B(G)B(G)^{\text{T}}$, where $B$ is the oriented incidence matrix of $G$. The suggested lower bound (2) produces the well known bound:

$\Delta+2-1=\Delta+1\leq \lambda_{\max}(L(G))$.

So I suppose the question can be thought of as: is there a nice relationship between the oriented incidence matrix row/column sums and the Laplacian eigenvalues similar to (1) and (2)?

-
isn't there a scaling problem? if you rescale $B$ to $\alpha B$ for some $\alpha\in\mathbb{R}^+$, then the left sides of your inequalities scale like $\alpha$ while the right sides scale like $\alpha^2$, and you might have trouble in neighbourhoods of 0. How does your well-known bound deal with this? – Emilio Pisanty Apr 27 '12 at 22:50

## 2 Answers

Let n=m and let B have 1/2 in each entry of the first row and the rest zeros. Then your inequality reduces to (n-1)/2 < n/4, which is clearly false.

-

There is a large literature about the relations between the graph's degrees (i.e. the row sums of the incidence matrix; the column sums are all 0 and so less interesting) and the Laplacian eigenvalues. Are you interested in this? If yes, the Grone-Merris conjecture might be a place to start (it has been proved since but I think the name stuck).

-
Hi Felix, I know of the Grone-Merris conjecture as well as Bai's work on it (if you want a neat reference that is quite new: homepages.cwi.nl/~aeb/math/ipm.pdf). However, I am more interested if the matrix result above is true. – hypercube Mar 30 '12 at 20:27