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