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

$\endgroup$
  • 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 Jan 15 '16 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 Jan 15 '16 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 Jan 31 '16 at 3:58
12
+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.$$

$\endgroup$
  • 9
    $\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 Jan 15 '16 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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