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.

  • $\begingroup$ 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? $\endgroup$ Sep 8, 2015 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – user32422
    Sep 8, 2015 at 10:32
  • 4
    $\begingroup$ 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. $\endgroup$ Sep 8, 2015 at 11:29
  • $\begingroup$ @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. $\endgroup$
    – user32422
    Sep 8, 2015 at 12:27
  • $\begingroup$ OK, I've edited the title to more accurately correspond to your question (changed "trace" into "sum of absolute value of eigenvalues") $\endgroup$ Sep 8, 2015 at 12:42

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .