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.
Best Answer
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.