# Upper bound for sum of absolute values of eigenvalues of Hermitian matrix

Given a hermitian, but not necessarily positive, sparse matrix $C = (c_{ij}) \in \mathbb{C}^{n \times n}$ and $n \ggg 1$ ($n \approx 2^{100}$) with eigenvalues $\lambda_1 \le \lambda_2 \le \dots \le \lambda_n$.

Is there an upper bound for $\mathrm{tr} \sqrt{C^\dagger C} = \sum_i |\lambda_i|$? Preferable in terms of the dimension $n$, or the norm $\|C\|_\infty := \max_{1 \leq i, j \leq n} |c_{ij}|$, or the norm $\| C \|_F := \sqrt{\sum_{i=1}^m \sum_{j=1}^n |c_{ij} |^2 }$.

Essentially, I'd like to relate the trace or eigenvalues with something related to the dimension $n$ and the absolute values of the matrix elements $c_{ij}$.

The trivial solution would be $\mathrm{tr} \sqrt{C^\dagger C} \le \sum_i \|C\|_\infty = n \|C\|_\infty$, but n is huge, and I expect most matrix elements, and almost all diagonal elements, to be zero, thus it's not a very good solution.

So far my best shot is the result by Brauer (1946) (http://www.sciencedirect.com/science/article/pii/002437958090258X):

$|\lambda_n| \le \text{min} ( \text{max}_l \sum_i |c_{li}|, \text{max}_k \sum_j |c_{jk}|) \Rightarrow \mathrm{tr} \sqrt{C^\dagger C} \in \mathcal{O}(n^2)$

I think there might be some room for improvement.

• I'm a bit confused: if the matrix is given, you just sum the diagonal elements to get the trace, what "bound" on the trace would you want? – Carlo Beenakker Sep 8 '15 at 10:15
• Sorry, it's not that clear. The matrix is not given. But due to physical constraints I have an upper bound for the biggest matrix element. Also, I have a good estimate for the average absolute value of a matrix element. – user32422 Sep 8 '15 at 10:32
• so it's like asking what you can say about the sum of reals when you know the sum of their absolute values; the latter will be an upper bound to the former, but I can't imagine you can lower that. – Carlo Beenakker Sep 8 '15 at 11:29
• @Carlo Beenakker I've corrected my question. I don't know the sum of their absolute values and neither does I want to know the sum of reals. I'm interested in the former. The problem is: almost everything, what I know about the matrix, comes from concepts in physics. The question is probably not suited for this site. I had not given the topic enough thought. – user32422 Sep 8 '15 at 12:27
• OK, I've edited the title to more accurately correspond to your question (changed "trace" into "sum of absolute value of eigenvalues") – Carlo Beenakker Sep 8 '15 at 12:42

Set $$H = \left( \begin{matrix} 1 & 1 \\ 1 & -1 \end{matrix} \right).$$

Then, the matrix $H_k := H^{\otimes k}$ is a $2^k \times 2^k$-matrix with entries $\pm 1$ (with respect to the natural basis). Set $n:=2^k$. It is easy to see that $H_k^2=n$.

It follows that the sum of absolute values of eigenvalues of $H_k$ is $n^{3/2}$. So, no upper bound better than this can be expected.