Upper bound on norm of Hermitian matrix

I encountered this statement in this paper about random walks on groups by H. Kesten (page 336, (1.2)). Although he gives a reference, I cannot find the proof there. The statement looks like a simple exercise in linear algebra (and it may very well be one), but I spent quite some time on it without finding a proof:

Let $A=(a_{ij})_{1\leq i,j\leq n}$ be a Hermitian matrix.
Then we have $$||A||\leq \sup_{1\leq i\leq n} \sum_{j=1}^n |a_{ij}|,$$ where $||A||=\sup_{||x||=1}||Ax||$ is the operator norm with respect to the standard Euclidean norm on $\mathbb{C}^n$.

Solution 1:

Supposing one understands the operator 2 norm to be equivalent to the maximal singular value of $A$, this result follows from applying either (a) Gerschgorin Discs (since $A$ is Hermitian the modulus of each of its eigenvalues equals one of its singular values) or (b) the Schur Test.

proof of the Schur Test
for arbitrary $A \in \mathbb C^{m\times n}$
and $m$ dimensional $\mathbf x$ and $n$ dimensional $\mathbf y$, each constrained to have unit length (2 norm).

$R := \max_{i} \sum_{j=1}^n \vert a_{i,j}\vert$
$C := \max_{j} \sum_{i=1}^m \vert a_{i,j}\vert$
(max L1 norm amongst respective row and column vectors of $A$)

$$ \begin{align} &\big \vert \mathbf x^*A\mathbf y\big \vert\\ & \leq \sum_{i=1}^m \sum_{j=1}^n \big \vert x_i a_{i,j} y_j\big \vert\\ &= \sum_{i=1}^m \sum_{j=1}^n \big(\vert x_i\vert \vert a_{i,j}\vert^\frac{1}{2}\big) \big(\vert a_{i,j}\vert^\frac{1}{2}\vert y_j\vert\big)\\ &\leq \Big(\sum_{i=1}^m \sum_{j=1}^n \big(\vert x_i\vert \vert a_{i,j}\vert^\frac{1}{2}\big)^2\Big)^\frac{1}{2} \Big(\sum_{i=1}^m \sum_{j=1}^n \big(\vert a_{i,j}\vert^\frac{1}{2}\vert y_j\vert\big)^2\Big)^\frac{1}{2}\\ &= \Big(\sum_{i=1}^m \vert x_i\vert^2 \big(\sum_{j=1}^n \vert a_{i,j}\vert\big) \Big)^\frac{1}{2} \Big(\sum_{j=1}^n \vert y_j\vert^2 \big(\sum_{i=1}^m \vert a_{i,j}\vert\big) \Big)^\frac{1}{2}\\ &\leq \Big(\sum_{i=1}^m \vert x_i\vert^2 \cdot R \Big)^\frac{1}{2} \Big(\sum_{j=1}^n \vert y_j\vert^2 \cdot C \Big)^\frac{1}{2}\\ &= \Big(\sqrt{R\cdot C}\Big) \Big(\sum_{i=1}^m \vert x_i\vert^2 \Big)^\frac{1}{2} \Big(\sum_{j=1}^n \vert y_j\vert^2 \Big)^\frac{1}{2}\\ &= \sqrt{R\cdot C} \\ \end{align} $$where the inequalities are (1) Triangle Inequality, (2) Cauchy-Schwarz, (3) a point-wise bound (then summing over the bound)

remark:
i.) for this problem, $R=C$ because $A$ is Hermitian so we recover the bound in the problem statement.
ii.) in general if $A=U\Sigma V^*$ with maximal singular value $\sigma_1$ then selecting $\mathbf x:=\mathbf u_1$ and $\mathbf y:= \mathbf v_1$ gives
$\sigma_1 = \mathbf u_1^*A\mathbf v_1 = \big \vert \mathbf u_1^*A\mathbf v_1\big \vert\leq \sqrt{R\cdot C}$