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.



Upper bound for sum of absolute values of eigenvalues of Hermitian matrix
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.


