# A sharper bound for $\|\cos(kA)\|_{\infty}$ for symmetric stochastic matrices

Given $A \in \mathbb{R}^{n \times n}$ that is symmetric, stochastic and diagonalizable, and $k \in \mathbb{N}$, I am interested in bounding $\|\cos(kA)\|_{\infty}$ from above.

$\| \|_{\infty}$ is the induced $\ell_{\infty}$ norm, i.e. $\|A\|_{\infty} = \max_{i}\sum_j|A_{i,j}|$, and the cosine of a matrix can be defined, for instance, via its Taylor expansion, $\cos(A) = \sum_t \frac{(-1)^{t}}{(2t)!}A^{2t}$.

The trivial bound is of course $\cosh(k)$. However, it seems highly untight for large $k$. For instance, we also have $\|\cos(kA)\|_{\infty} \le \sqrt{n}\|\cos(kA)\|_{2} = \sqrt{n}$ (since $\cos(kA)$ is normal and its largest eigenvalue is at most $1$).

Can you see a tighter bound in the special case where $A$ is doubly stochastic?

Thank you very much.

• @user1551, in case $A$ is the $2 \times 2$ matrix $[a,1-a;1-a, a]$, the infinity norm is given by $\max\{|\cos(k)|,|\cos((2a-1)k)|\}$. And indeed, as you stated, the maximum is obtained for $a=0.5$, which corresponds to your assumption. Unfortunately, I had no further insight. Thank you. – DanDan May 13 '14 at 14:01
• Have you thought of looking for examples amongst circulant matrices en.wikipedia.org/wiki/Circulant_matrix? It is easy to characterize symmetry and stochasticness of these matrices. And it is fairly straight forward to compute the cos of these matrices, because they can be diagonalized via the discrete Fourier transform. – Stephen Montgomery-Smith May 16 '14 at 3:58
• @StephenMontgomery-Smith, thank you for your comment. Trying to derive an analytic expression, even though the diagonalization is explicitly known, was not successful. However, I did try random symmtric stochastic circulant matrices in Matalb, and for $k = O(\log n)$ the results were indeed small. However, for larger $k$ (which I am not interested), the results did exceed $3$. Any other insight would be helpful, as I am trying to show that under some (maybe more) constraints I can bound the infinity norm of $\frac{1}{T}\sum_{k=1}^{T}\cos(kA)$ by a constant, for $T = O(\log n)$. – DanDan May 16 '14 at 19:27
• @user1551, it only happens for larger $n$ and very large $k$. Although, for $k$ which is relatively small to $n$, it does not exceed $3$ even for large $n$. It might have something to do with the accuracy of the "funm" function rather than to the result itself. I have no intuition as to why it should not be uniformly bounded. – DanDan May 17 '14 at 9:58

Denote $f(x) = \cos(kx)$, and let $g(a) = f\left(1-2\frac{|a|}{d}\right)$ for $a \in \{0,1\}^{d}$.
If we take $A$ to be the adjacency matrix of the hypercube graph with $2^{d}$ vertices, the question is equivalent to finding the so-called spectral norm of $g$ as a Boolean function, i.e. $$\|f(A)\|_{\infty} = \| \hat{g}\|_{1}.$$
I could not bound it analytically, however numerical experiments suggest that the above behaves like $d$ and unfortunately is not bounded by a constant.