15
$\begingroup$

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".

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Federico Poloni May 18 '14 at 7:19
  • 1
    $\begingroup$ 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$" $\endgroup$ – Yemon Choi May 19 '14 at 19:37
  • 1
    $\begingroup$ 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)? $\endgroup$ – Yemon Choi May 19 '14 at 19:38
  • $\begingroup$ 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). $\endgroup$ – Eusebio Gardella May 19 '14 at 19:41
  • $\begingroup$ I edited the question to prevent other people from falling into the Schatten trap. $\endgroup$ – Eusebio Gardella May 19 '14 at 19:47
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.