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.


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.