Let $\bf{H}$ be $n\times n$ real symmetric matrix with zero diagonal and entries $h_{ij} \in [0, M]$. Denoting its eigenvalues $\lambda_1 \leq \dots \leq \lambda_n$, I want to improve the upper bound $$\sum_i|\lambda_i| \leq O(n^2M)$$ (obtained e.g. via Gershgorin disc theorem forcing $|\lambda_i| \leq nM$) to, ideally, $$\sum_i|\lambda_i| \leq O(nM).$$
Because $\sum_i \lambda_i = \mathrm{tr}(\mathbf{H})=0$, showing that $|\lambda_1|$ or $|\lambda_n|$ are bounded by $O(f(M))$ would be one way to do so — however I did not find a way to put a sufficiently tight bound on either.
P.S. "singular values" in the title is due to the symmetry of $\mathbf{H}$ implying $\sigma_i = |\lambda_i|$.
UPD: we can use the fact that diagonal entries of $\mathbf{H}^\mathrm{T}\mathbf{H}$ are bounded from above by $nM^2$, and therefore $$\sum_i|\lambda_i| = \sum_i \sigma_i \leq \sum_i\sqrt{(\mathbf{H}^\mathrm{T}\mathbf{H})_{ii}} \leq n^{\frac{3}{2}}M.$$
Best Answer
It seems to be impossible to lower the power of $n$ in the bound below $\frac{3}{2}$ in the general case. In the case when the Perron–Frobenius eigenvalue $\lambda_n(\bf{H})$ is significantly larger in magnitude than the others, a useful alternative bound can be achieved from combining a lower bound on $\lambda_n(\bf{H})$ and an upper bound on the sum of squared entries of $\mathbf{H}$. Because in my case $\bf{H}$ was a result of applying an element-wise convex function to another matrix, I obtained a tight bound $\lambda_n(\mathbf{H}) \geq \alpha$ by using the Min-Max theorem for vector $\begin{bmatrix}\frac{1}{\sqrt{n}} \ldots \frac{1}{\sqrt{n}}\end{bmatrix}$ together with Karamata's inequality (based on the original matrix's mean). Trivially, $$\sum\lambda_i^2 = \mathrm{tr}(\mathbf{H}^T\mathbf{H}) = \sum H_{ij}^2 \leq n^2M^2.$$
Then $$\sum|\lambda_i| \leq nM + \sum_{i=1}^{n-1}|\lambda_i| \leq nM + \sqrt{(n-1)\sum_{i=1}^{n-1}\lambda_i^2} \leq nM + \sqrt{(n-1)(n^2M^2 - \alpha^2)}.$$