2

2

Motivated by Federico's recent question: Norm of upper triangular matrix of all ones I decided to ask a 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$.
flag
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 2011 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. – S. Sra Aug 10 2011 at 0:47

1 Answer

3

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

link|flag
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. – S. Sra Aug 11 2011 at 1:09
1 
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 2011 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? – S. Sra Aug 11 2011 at 3:36

Your Answer

Get an OpenID
or

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