13
$\begingroup$

I am interested in the history of an inequality for the spectral radius of a $d\times d$ real or complex matrix, which occurs in Jairo Bochi's 2002 article Inequalities for numerical invariants of sets of matrices. Let $\|\cdot\|$ denote the matrix norm induced by the Euclidean norm, and let $\rho(A)$ denote the spectral radius of $A$, that is, the maximum of the absolute values of its eigenvalues. The inequality in question is $$\left\|A^d\right\|\leq \left(2^d-1\right)\rho(A)\left\|A\right\|^{d-1}.$$ This may be proved easily using the Cayley-Hamilton formula: since $$\sum_{k=0}^d (-1)^k\left(\mathrm{tr}\,A^{\wedge k}\right) A^{d-k}=0$$ we may write $$\left\|A^d\right\| \leq \sum_{k=1}^{d}\left|\mathrm{tr}\,A^{\wedge k}\right|\cdot \|A^{d-k}\| \leq \sum_{k=1}^d {d \choose k} \rho(A)^k\|A^{d-k}\| \leq \left(2^d-1\right)\rho(A)\|A\|^{d-1}$$ since $A^{\wedge k}$ has ${d\choose k}$ eigenvalues all of which are bounded by $\rho(A)^k \leq \rho(A)\|A\|^{k-1}$, and since $\sum_{k=1}^d {d\choose k} =2^d-1$. The inequality yields quick proofs of Gelfand's formula for matrices and the continuity of $\rho(A)$ as a function of $A$ as corollaries. Furthermore it has powerful generalisations to numerical invariants of sets of matrices, and these generalisations can be applied to obtain nontrivial results on phenomena such as the rate of convergence in the Berger-Wang theorem and the affinity dimension of self-affine fractals. Indeed, some of these results currently admit no other known proof.

The original inequality itself is a sufficiently useful and, to my mind, interesting inequality that I am curious to know more about its history. Jairo tells me that he invented it independently of other sources and has not seen it elsewhere, but is unsure whether it has appeared elsewhere in the literature. My first question therefore is:

Has anyone seen this inequality elsewhere? What is the earliest reference for it? Is it in any textbook? Does it have a name?

My second question is whether the optimality of the constant has been investigated:

Is the constant $2^d-1$ optimal? Is it of optimal order as a function of $d$? Which matrices constitute the `worst case'?

Edited: Fedor Petrov and Mikael de la Salle have given excellent answers to the second part of the question. I've set up a bounty to see if I can get a similarly comprehensive answer to the first part.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Actually, as the proof shows, the inequality holds (with the same constant 2^d-1) for any submultiplicative norm on dxd matrices, and not just the Euclidian-induced one. So, in principle, the optimal constant may have different values, depending on whether we care only about the Euclidian-induced norm, or whether we want an inequality valid simultaneously for all submultiplicative norms. $\endgroup$
    – Jairo Bochi
    Commented Jan 15, 2016 at 21:27
  • 1
    $\begingroup$ Oops! Actually the constant from Ian's proof depends on the norm of the identity matrix (which may be different from 1: for example for the Hilbert-Schmidt norm), and so I don't know if there is a uniform constant that works for all submultiplicative norms. Anyway, my comment makes sense if "submultiplicative norm" is replaced with "matrix norm induced by a norm in R^d". $\endgroup$
    – Jairo Bochi
    Commented Jan 15, 2016 at 23:46
  • $\begingroup$ I'm afraid I can't help with the literature/history, but if you still want to know, it might be worth sending an email enquiry to Thomas Ransford (Laval) who tends to be very knowledgeable about these kinds of things. $\endgroup$
    – Yemon Choi
    Commented Jan 31, 2016 at 3:58
  • $\begingroup$ Is there a reference so I can see the proof of this Cayley-Hamilton formula? Does it come from the Cayley-Hamilton theorem? I've never seen it and don't know what is $A^{\wedge k}$. $\endgroup$
    – Gomes93
    Commented Sep 11 at 19:19

1 Answer 1

Reset to default
14
+100
$\begingroup$

Constant is definitely not sharp. For example, let me show inequality $\|A^d\|\leqslant \frac1{\sqrt[d]{2}-1}\cdot \rho(A)\cdot \|A\|^{d-1}$. We may suppose $\|A\|=1$, denote $\rho(A)=\rho$, then we have two inequalities $\|A^d\|\leqslant \|A\|^d=1$ and $\|A^d\|\leqslant d\rho+\dots+\rho^d=(1+\rho)^d-1$, explained in the post. If $\rho\geqslant \sqrt[d]{2}-1$ use first inequality, if $\rho<\sqrt[d]{2}-1:=\rho_0$, use the second: $$\frac{(1+\rho)^d-1}{\rho}\leqslant \frac{(1+\rho_0)^d-1}{\rho_0}=\frac1{\sqrt[d]{2}-1},$$ and we are done.

Note that this constant is of linear order in $d$, it behaves like $\frac{d}{\log 2}$ for large $d$ and is less than $\frac{d}{\log 2}$ for all $d$, since $$\sqrt[d]2=e^{\frac{\log 2}d}\geqslant 1+\frac{\log 2}d.$$

Improve this answer
$\endgroup$
1
  • 10
    $\begingroup$ $d/\log 2$ is not far from the best constant. Indeed, consider the matrix $A$ of the linear map $e_i \mapsto e_i + C e_{i+1}$ for $i=1 \dots d-1$ and $e_d \mapsto e_d$. You have that $\rho(A)=1$ whatever value of $C$, and $\|A\| \sim C$ and $\|A^{d}\| \sim d C^{d-1}$ as $C \to \infty$. Therefore, the best constant is at least $d$. $\endgroup$
    – Mikael de la Salle
    Commented Jan 15, 2016 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .