# Operator norms of circulant matrices

The definition and basic properties of circulant matrices can be found here: http://en.wikipedia.org/wiki/Circulant_matrix.

For complex numbers $a_1,\ldots,a_n$, I will use the notation

$$\mbox{circ}(a_1,\ldots,a_n)=\left(\begin{array}{llll} a_1& a_2 & \cdots & a_{n-1} & a_n \\ a_n& a_1 & \cdots & a_{n-2} & a_{n-1} \\ \vdots & \vdots & \ddots & \vdots &\vdots\\ a_3& a_4 & \cdots & a_1 & a_2\\ a_2& a_3 & \cdots & a_{n} & a_1\\ \end{array}\right).$$ I am interested in their operator $p$-norms (not to be confused with their Schatten $p$-norms). The operator $p$-norm on $M_n$ is the norm induced by regarding each $n\times n$ matrix as an operator on $\ell^p(\{1,\ldots,n\})\cong \mathbb{C}^n$ in the usual way. Such norms are not invariant under multiplication by unitary matrices (except when $p=2$).

Ideally I would like an explicit formula for the operator $p$-norm of $\mbox{circ}(a_1,\ldots,a_n)$ in terms of $a_1,\ldots,a_n$, but this is probably too much to ask for. I've looked at the available literature and I haven't been able to find anything in this direction (although there is a lot on other norms).

Question 1: Can the $p$-norms of at least some (non-trivial) circulant matrices be computed more or less explicitly?

If they can't be computed explicitly in general, maybe one can say something about the following:

Question 2: Suppose $a$ is a circulant matrix and $\|a\|_1>\|a\|_2$. Does it follow that $\|a\|_p>\|a\|_2$ for every $p \in (1,2)$?

In reference to question 2 (which is the one I'm most interested in): it is known that if $a$ is a circulant matrix, then $\|a\|_p=\|a\|_q$ whenever $p$ and $q$ are conjugate exponents, and that $\|a\|_p\geq \|a\|_2$ for all $p$. The function $p\mapsto \|a\|_p$ is log-convex and decreasing on $[1,2]$ by Riesz-Thorin. So to answer question 2 affirmatively, one would have to argue why $\|a\|_p$ can't be constant on some neighborhood of 2 without being constant everywhere.

As a very special case, set $\omega=e^{2\pi i/n}$ and consider the matrix

$$a=\mbox{circ}(2,1+\omega^{n-1},1+\omega^{n-2},\ldots,1+\omega)=\left(\begin{array}{llll} 2& 1+\omega^{n-1} & \cdots & 1+\omega^{2} & 1+\omega \\ 1+\omega& 2 & \cdots & 1+\omega^{3} & 1+\omega^{2} \\ \vdots & \vdots & \ddots & \vdots &\vdots\\ 1+\omega^{n-2}& 1+\omega^{n-3} & \cdots & 2 & 1+\omega^{n-1}\\ 1+\omega^{n-1}& 1+\omega^{n-2} & \cdots & 1+\omega & 2\\ \end{array}\right).$$

One checks that $\|a\|_1>\|a\|_2$. Is it true that $\|a\|_p>\|a\|_2$ for the other values of $p$?

Finally, I would like to point out that it is most likely the case that if one omits the assumption that $a$ be a circulant matrix in question 2, then the answer is in general "no".

• Not quite what you are asking about, but an interesting observation nevertheless in my view: if $a_i\geq 0$ for each $i$, then $\Vert C\Vert_1=\Vert C\Vert_2=\Vert C\Vert_{\infty}$. Proof (very short) in 10.1016/j.amc.2010.12.094 for a special matrix, but the idea works in general whenever $a_i\geq 0$. – Federico Poloni May 18 '14 at 7:19
• Since at least one person seems to have fallen into the "Schatten trap", perhaps it's worth emphasising that by operator $p$-norm you mean "operator norm on $\ell_p^n$" – Yemon Choi May 19 '14 at 19:37
• Have you found any non-trivial bounds on the norm of the standard Fourier matrix (the one which implements DFT and which intertwines the circulants with diagonal matrices)? – Yemon Choi May 19 '14 at 19:38
• Unfortunately I haven't. It is clearly not an isometry for $p\neq 2$ but I do not know what it's actual norm is (or even a lower bound). – Eusebio Gardella May 19 '14 at 19:41
• I edited the question to prevent other people from falling into the Schatten trap. – Eusebio Gardella May 19 '14 at 19:47

The answer to Question 2 is "No". Note that the $2$-norm is just the maximum of $\left|\sum_{k=0}^{n-1}a_{k+1}z^k\right|$ over the $n$-th power roots of unity and the $1$-norm is just $\sum_k |a_k|$. So, take any $a_k$ such that $\sum_k a_k=1$, $\sum_k |a_k|>1$ and $\sum_k a_k\omega^k\approx 0$ for any non-trivial $n$-th power root of unity (just perturb $\frac 1n$ a bit adding small imaginary parts or something like that).
Denote by $S$ the Euclidean unit sphere. Let $v_0=(n^{-1/2},\dots,n^{-1/2})$. Then $Tv_0=v_0$. Note that for any $v\in S$ with $\langle v,v_0\rangle>0$, we have $\|Tv\|_2^2\le 1-c\|v-v_0\|_2^2$. Since the $L^p$ norm of a vector is continuous in $p$, we see that the only chance to get the ratio $\frac{\|Tv\|_p}{\|v\|_p}$ greater than $1$ for $p$ close to $2$ is to take $v$ close to $v_0$.
To consider this neighborhood, it will be convenient to replace $v$ by its multiple $w$ of the form $w=w_0+z$ where $w_0=(1,\dots,1)$ and $\langle z,w_0\rangle=0$. We still have $Tw_0=T^*w_0=w_0$. The above inequality translates into $\|Tw\|_2^2\le \|w\|^2-c\|z\|_2^2$ (with slightly different but still fixed positive $c>0$).
Since for small $t$, $|(1+t)^p-(1+t)^2-(p-2)t|\le \delta(p) t^2$ with $\delta(p)\to 0$ as $p\to 2$, we have $$\frac{\|Tw\|_p^p}{\|w\|_p^p}\le \frac{\|Tw\|_2^2+(p-2)\langle Tz,w_0\rangle+\delta(p)\|Tz\|_2^2}{\|w\|_2^2+(p-2)\langle z,w_0\rangle-\delta(p)\|z\|_2^2} \\ \le \frac{\|w\|_2^2-(c-\delta(p))\|z\|_2^2}{\|w\|_2^2-\delta(p)\|z\|_2^2}\le 1\,,$$
provided that $2\delta(p)\le c$. (We used that $\langle Tz,w_0\rangle=\langle z,T^*w_0\rangle=\langle z,w_0\rangle=0$ and that $\|Tz\|_2\le\|z\|_2$ here.)
It looks like this argument works more often than not (all I have really used is that the largest eigenvalue of the circulant matrix is simple; that the eigenvalue is $1$ and the corresponding eigenvector is $(1,\dots,1)$ can be assumed without loss of generality because we can always conjugate by $\operatorname{diag}(1,\zeta,\zeta^2,\dots,\zeta^{n-1})$ and multiply by a scalar without changing anything in the problem). So, unless I have made a stupid mistake anywhere, you are out of luck.