# Norm of Cesaro matrix

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$.
-
You probably know this, but it looks like $C_n^{-1} = {\rm diag}(1,2,\ldots,n)M_n^{-1},$ where $M_n^{-1}$ is the inverse that Noam Elkies used in his solution yesterday. It isn't clear to me that this is a significant simplification, though. –  Geoff Robinson Aug 9 '11 at 17:05
Yes I did see that; this matrix actually seems to satisfy several other nice properties. I am hoping for a pretty solution. –  Suvrit Aug 10 '11 at 0:47
whoever downvoted this seems to have downvoted 3 of my questions in close succession (within 3 minutes of each other) --- interesting --- not that I am particularly proud of the elementary questions that were downvoted, but a string of them within quick succession seems a little suspicious! –  Suvrit Nov 29 '13 at 1:14

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

-
Nice answer! The upper bound seems to be easy; I saw in Choi's paper on "tricks and treats with the hilbert matrix" the exercise $I \succeq (I-C_n)(I-C_n)^T$, which yields the upper bound. –  Suvrit Aug 11 '11 at 1:09
Thanks -- also for the reference/reminder of Choi's paper (I remembered the paper though not the exercises, not surprisingly since it appeared 28 years ago). Choi says this proof of $\|C\|_2 \leq 2$ appears in a paper "Cesàro operators" by A. Brown, P.R. Halmos, and A.L. Shields (Acta Szeged 26 (1985), 125--137). Perhaps that paper also addresses your question. –  Noam D. Elkies Aug 11 '11 at 3:18
I couldn't find the Halmos paper, so started playing around with this matrix myself. I saw that this matrix has several other nice properties; though I don't know if they are that useful. Eg., $C^TC=M$, where $m_{ij}=1/\max(i,j)$, and it is known that the Hadamard power $[m_{ij}^\alpha]$ is also positive definite...do you see an easy way to exploit that fact to get some nice inequalities? –  Suvrit Aug 11 '11 at 3:36

After playing a bit with this it appears that we can make use of a very simple tridiagonal/bandmatrix. If we have $$C_5 = \small \begin{bmatrix} 1 & 1/2 & 1/3 & 1/4 & 1/5 \\ . & 1/2 & 1/3 & 1/4 & 1/5 \\ . & . & 1/3 & 1/4 & 1/5 \\ . & . & . & 1/4 & 1/5 \\ . & . & . & . & 1/5 \end{bmatrix}$$ and for the determination of the norm we build $$B_5 = C_5 \cdot C_5^{\Tiny H}$$ and use the squareroot of the largest eigenvalue $\lambda_0$as the norm of matrix $C_5$ then as well we can use the squareroot of the smallest eigenvalue of $A_5=B_5^{-1}$.
The interesting observation is, that the matrix $A_k$ has a very simple form: we get the easily extensible form $$A_5=\small { \begin{bmatrix} 1 & -1 & . & . & . \\ -1 & 5 & -4 & . & . \\ . & -4 & 13 & -9 & . \\ . & . & -9 & 25 & -16 \\ . & . & . & -16 & 41 \end{bmatrix} }$$ where the entries in the diagonal are just the sums of two neighboured squares.
The characteristic polynomials of the matrices of the first couple of truncations $A_1$ to $A_5$ are listed in the following matrix row by row, where I only document the coefficients at increasing powers of x col by col: $$\Tiny \begin{array} {r|rrrrrrrrr} k& x^0&x^1&x^2 & x^3&x^4&x^5&x^6&x^7 \\ \hline \\ 0& 1 & . & . & . & . & . & . & . \\ 1& -1 & 1 & . & . & . & . & . & . \\ 2& 4 & -6 & 1 & . & . & . & . & . \\ 3& -36 & 66 & -19 & 1 & . & . & . & . \\ 4& 576 & -1200 & 460 & -44 & 1 & . & . & . \\ 5& -14400 & 32880 & -15196 & 2008 & -85 & 1 & . & . \\ 6& 518400 & -1270080 & 672336 & -110184 & 6568 & -146 & 1 & . \\ 7& -25401600 & 65862720 & -38724624 & 7435608 & -558304 & 17682 & -231 & 1 \end{array}$$ The "polynomial" at $k=0$ is appended just to obtain a triangular form of that coefficients matrix to allow more structural analyses later on.

(Example:) So for $C_3$ we get the solution as the squareroot of the reciprocal of the smallest root of the polynomial at $k=3$ which is $$f_3(x) =-36 + 66x -19x^2 + 1x^3 = 0$$ The polynomial roots are $$\small {[0.670199052997, 3.66217242957, 14.6676285174] }$$ the reciprocals are $$\small { [1.49209402121, 0.273061965058, 0.0681773470613] }$$ the squareroots of this are $$\small { [1.22151300493, 0.522553313125, 0.261107922249] }$$ such that $$\small {||C_3||_2 \approx 1.22151300493 }$$

I think I have once read, that eigenvalues of symmetric tridiagonal matrices have a simple form (but can't find a good general expression at the moment), so I thought this comment might be helpful for further analyses of this.

-
Thanks for your observations Gottfried. I had also played around with $\lambda^{1/2}(CC^T)$ at the time I wrote this question (where I mention that $C$ enjoys several interesting properties) --- it would be great to get a handle of the "dominant spectrum" of this matrix... –  Suvrit Nov 29 '13 at 17:59