# 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