1
$\begingroup$

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$.
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2011 at 17:05
  • $\begingroup$ Yes I did see that; this matrix actually seems to satisfy several other nice properties. I am hoping for a pretty solution. $\endgroup$
    – Suvrit
    Aug 10, 2011 at 0:47
  • $\begingroup$ 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! $\endgroup$
    – Suvrit
    Nov 29, 2013 at 1:14

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Aug 11, 2011 at 1:09
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 11, 2011 at 3:18
  • $\begingroup$ 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? $\endgroup$
    – Suvrit
    Aug 11, 2011 at 3:36
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Suvrit
    Nov 29, 2013 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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