For each ${n}$, let ${A_n = (a_{ij,n})_{1 \leq i,j \leq n}}$ be a random ${n \times n}$ matrix (i.e. a random variable taking values in the space ${{\bf R}^{n \times n}}$ or ${{\bf C}^{n \times n}}$ of ${n \times n}$ matrices) such that the entries ${a_{ij,n}}$ of ${A_n}$ are jointly independent in ${i,j}$ and take values in ${\{-1,+1\}}$ with a probability of ${1/2}$ each. If ${\|A_n\|_{op}}$ denotes the operator norm of ${A_n}$, and ${\varepsilon > 0}$, show that ${\|A_n\|_{op} / n^{1/2+\varepsilon}}$ converges almost surely to zero, and that ${\|A_n\|_{op} / n^{1/2-\varepsilon}}$ diverges almost surely to infinity. (Hint: use the spectral theorem to relate ${\|A_n\|_{op}}$ with the quantities ${\hbox{tr} (A_n A_n^*)^k}$.)
Attempt: As $A_nA_n^*$ is symmetric, its' operator norm ${\|A_nA_n^*\|_{op}}$ is equal to the ${\ell^\infty}$ norm $\displaystyle \|A_nA_n^*\|_{op} = \max_{1 \leq i \leq n} \lambda_i$ of the eigenvalues ${\lambda_1,\ldots,\lambda_n\in {\bf R}}$ of $A_nA_n^*$ (note the eigenvalues are non-negative here). On the other hand, we have the standard linear algebra identity $\displaystyle \hbox{tr}(A_nA_n^*)^k = \sum_{i=1}^n \lambda_i^k$. In particular, for any natural number $k$, we get the inequalities $\displaystyle \|A_n\|^{2k}_{op} = \| A_nA_n^* \|_{op}^k \leq \hbox{tr}(A_nA_n^*)^k \leq n \|A_nA_n^*\|_{op}^k = n\|A_n\|^{2k}_{op}$.
From this, we see that for any even $k$,
$\displaystyle {\|A_n\|_{op} / n^{1/2+\varepsilon}} \leq [\hbox{tr}(A_nA_n^*)^k]^{\frac{1}{2k}} / n^{1/2+\varepsilon}$
and $\displaystyle {\|A_n\|_{op} / n^{1/2-\varepsilon}} \geq [\hbox{tr}(A_nA_n^*)^k]^{\frac{1}{2k}} / n^{\frac{1}{2k} + \frac{1}{2} - \varepsilon}$.
I was unable to proceed using law of large numbers with these bounds, since the entries of $A_nA_n^*$ are not iid. Any direct or indirect help will be appreciated.
Edit: After some further consideration, I managed to obtain a solution which I paste below. Critiques, verifications, and suggestion for different methods are welcomed.
Fix some $\varepsilon, \varepsilon' > 0$. As $A_nA_n^*$ is symmetric, the operator norm ${\|A_nA_n^*\|_{op}}$ is equal to the ${\ell^\infty}$ norm $\displaystyle \|A_nA_n^*\|_{op} = \max_{1 \leq i \leq n} \lambda_i$ of the eigenvalues ${\lambda_1,\ldots,\lambda_n\in {\bf R}}$ of $A_nA_n^*$ (note that these values are non-negative). Also, we have the standard linear algebra identity $\displaystyle \hbox{tr}(A_nA_n^*)^k = \sum_{i=1}^n \lambda_i^k$. Consequently, for any natural number $k$, we have the inequalities
$\displaystyle \|A_n\|^{2k}_{op} = \| A_nA_n^* \|_{op}^k \leq \hbox{tr}(A_nA_n^*)^k \leq n \|A_nA_n^*\|_{op}^k = n\|A_n\|^{2k}_{op}$
It follows that for any natural number $k$,
$\displaystyle {\|A_n\|_{op} / n^{1/2+\varepsilon}} \leq [\hbox{tr}(A_nA_n^*)^k]^{\frac{1}{2k}} / n^{1/2+\varepsilon}$
and
$\displaystyle {\|A_n\|_{op} / n^{1/2-\varepsilon}} \geq [\hbox{tr}(A_nA_n^*)^k]^{\frac{1}{2k}} / n^{\frac{1}{2k} + \frac{1}{2} - \varepsilon}$.
Let $E_n$ be the event $[\hbox{tr}(A_nA_n^*)^k]^{\frac{1}{2k}} / n^{1/2+\varepsilon} > \varepsilon'$, which is equivalent to the event
$\displaystyle \hbox{tr}(A_nA_n^*)^k / n^{k(1+2\varepsilon)} > \varepsilon'$, where we re-scale $\varepsilon' := (\varepsilon')^{2k}$. It can be shown by induction that ${\bf E}\hbox{tr}(A_nA_n^*)^k = 2n^{k+1} - n^k$ for all $n$ and all $k \geq 2$. From this and the Markov inequality, we obtain the bound
$\displaystyle {\bf P}(E_n) \leq \frac{2n - 1}{\varepsilon' n^{2 \varepsilon k}}$.
Valid for any $k \geq 2$. Choose some sufficiently large $k$ (greater than $2$) depending on $\varepsilon$ such that the denominator $\displaystyle \varepsilon' n^{2 \varepsilon k} \geq O(n^3)$ (say), we see in particular that the ${\bf P}(E_n)$ are summable, and ${\bf P}(\bigvee_{n \geq N} E_n) \to 0$ as $N \to \infty$ by subadditivity. Combined with the first inequality, this implies that ${\|A_n\|_{op} / n^{1/2+\varepsilon}}$ converges almost surely to zero.
Finally, setting $k=1$ in the second inequality gives the bound
$\displaystyle {\|A_n\|_{op} / n^{1/2-\varepsilon}} \geq n^{\varepsilon}$,
which implies that ${\|A_n\|_{op} / n^{1/2-\varepsilon}}$ diverges almost surely to infinity.