[Math] Norm of Cesaro matrix

matricespositivity

EDIT (28.11.2013).
This math.SE question about Cesaro operators should also be of interest (it discusses upper bounds; Noam has produced lower bounds below)

Federico's recent question Norm of upper triangular matrix of all ones
motivated me to ask this question about the norm of a matrix that is, in a sense, dual to the all ones upper triangular matrix.

Let $C_n$ be the $n \times n$ matrix (transpose of the Cesàro matrix)

$$
[C_n]_{ij} = \begin{cases}
1/j & i \le j\\\\
0 & i > j
\end{cases}
$$

What is $\|C_n\|_2$?

Notes:

  1. From results on Cesàro operators, it seems to follow that $\|C_n\| \le 2$ for all $n \ge 1$.
  2. It is also worth noting that $\|C_n\|_1=1$ and $\|C_n\|_{\infty} = H_n$, where $H_n$ denotes the $n$-th Harmonic number.
  3. Computing $\frac{e^TC_n^TC_ne}{e^Te}=2-H_n/n$ (e is the all ones vector) we obtain a simple lower-bound on $\|C_n\|_2$.

Best Answer

Here there is likely no closed form for $\|C_n\|_2$, but I can show $\|C_n\|_2 > 2 - O(1/\log n)$; given that also $\|C_n\|_2 \leq 2$ (is this easy to prove?) it follows that $\|C_n\|_2 \rightarrow 2$ as $n \rightarrow \infty$.

In general we can consider, for fixed $p \in [1,\infty]$, the $l^p$-operator norm of the Cesàro transformation $C_n$ that takes any finite sequence $(a_1,a_2,\ldots,a_n)$ to its sequence of averages $j^{-1} \sum_{i=1}^j a_i$. [If I've kept my $i$'s and $j$'s straight, that's the action of $C_n$ on row vectors, so this operator norm is what you'd call $\|C_n\|_q$ where $p^{-1} + q^{-1} = 1$; fortunately for $p=2$ the $l^p$ norm is self dual.] I claim that this operator norm is at least $p - O(1/\log n)$. Indeed Let $v_n(p)$ be the sequence whose $j$-th term is $j^{-1/p}$, so $\|v_n\|_p^p = H_n$. Then the image of $v_n(p)$ under $C_n$ differs from $p v_n(p)$ by a vector of $l_p$-norm $O(1)$, because its $j$-th entry is between $$j^{-1} \int_1^j \phantom. x^{-1/p} \phantom. dx = p \cdot (j^{-1/p} - j^{-1})$$ and $$j^{-1} \int_0^j \phantom. x^{-1/p} \phantom. dx = p \phantom. j^{-1/p}.$$ We have thus found a nonzero vector whose norm is multiplied by $p - O(1/\log n)$, which proves the claimed lower bound.

I don't expect that $\|C_n\|_2$ has a closed form, because it is a root of the characteristic polynomial of $C_n^{\rm T} C_n^{\phantom.}$, and these characteristic polynomials have maximal Galois group for small $n$: running the gp code

C(n) = matrix(n,n,i,j,(i<=j)/j)
S2(M) = charpoly(M*M~)
P(n)=S2(C(n))
for(n=1,11,print(polgalois(P(n))))

I found that the Galois group is $S_n$ for each $n \leq 11$. The norm $\|C_n\|_2$ can then also be computed (as long as $n$ is small enough that the computation terminates in reasonable time) by telling gp

N(n) = sqrt(vecmax(real(polroots(P(n)))))

and the convergence to $2$ seems slow enough that $O(1/\log n)$ might well be the correct error estimate.

Curiously it seems that the action of $C_n$ on the column vector $(a_n(2))^{\rm T}$ comes rather close to the actual $l^2$-operator norm. For example, when $n=40$ this yields the lower bound $1.5520\ldots$ on the norm (which is actually $1.5594\ldots$), while the row vector gets only $1.4201\ldots$. If this persists as $n \rightarrow \infty$ it should yield a much better estimate on $\|C_n\|_2$.

Related Question