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)$.


(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)?

  • 1
    $\begingroup$ 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? $\endgroup$ – Emilio Pisanty Apr 27 '12 at 22:50

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.

| cite | improve this answer | |

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).

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – hypercube Mar 30 '12 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.