8
$\begingroup$

Question. Given a positive-definite $n \times n$ matrix $A = (a_{ij})$ with eigenvalues $$ \lambda_1 \leq \cdots \leq \lambda_n , $$ is there a sharp upper bound for the product $\lambda_2 \cdots \lambda_n$ in terms of the quantity $$ \|A\|_\infty := \max_{1 \leq i, j \leq n} |a_{ij}| ? $$

A classic inequality due to A. Hirsch states that the modulus of an eigenvalue of an $n \times n$ complex matrix $A$ is less than $n \|A\|_\infty$, which implies that $$ |\lambda_2 \cdots \lambda_n| \leq n^{n-1}\|A\|_\infty^{n-1} . $$ However, this seems like a rather rough estimate for positive-definite matrices. I'm interested in any estimate that is substantially better than this.

Motivation. Using Hirsch's inequality one can improve Lemma 4 in page 43 of Siegel's Lectures on Quadratic Forms to yield the following result:

Theorem. If $A = (a_{ij})$ is a positive-definite $n \times n$ matrix, then for every $x \in \mathbb{R}^n$ we have that $$ \frac{\det(A)}{n^{n-1}a_{11} a_{22} \cdots a_{nn}} \sum a_{ii} x_i^2 \leq \sum a_{ij} x_i x_j \leq n \sum a_{ii} x_i^2 . $$

The inequality on the left would be greatly improved if we had the sharp upper bound required in the question. This in turn would yield a better answer to this enclosure problem (see my answer to that question).

Addendum. If we apply the estimate in Suvrit's answer in the proof of the theorem above, the inequality is indeed improved to:

$$ \frac{\det(A)}{2^{n-1}a_{11} a_{22} \cdots a_{nn}} \sum a_{ii} x_i^2 \leq \sum a_{ij} x_i x_j \leq n \sum a_{ii} x_i^2 . $$

In fact, in the proof the estimate for $\lambda_2 \cdots \lambda_n$ is applied to an auxiliary matrix $B = (b_{ij})$ whose diagonal entries are all $1$ and for which $|b_{ij}| < 1$ if $i \neq j$.

In turn this yields the following improved bound for the enclosure problem:

Theorem. Let $E \subset \mathbb{R^n}$ be an $n$-dimensional ellipsoid centered at the origin and containing no other integer point. There exists a transformation $T \in GL(n,\mathbb{Z})$ such that $T(E)$ is contained in the ball of radius $$ \left(\frac{3}{2}\right)^{(n-1)(n-2)/2} \frac{2^n}{\epsilon_n}\sqrt{2^{n-1}} $$ centered at the origin.

Here $\epsilon_n$ is the volume of the unit ball of dimension $n$.

Does anyone know a better bound?

$\endgroup$
0

1 Answer 1

11
$\begingroup$

$\newcommand{\trace}{\operatorname{trace}}$ The result below mentions a reasonably improved inequality.

Let $m = \frac{\trace(A)}{n}$, and $s^2= \frac{\trace(A^2)}{n}-m^2$. Then, Wolkowicz and Styan (Linear Algebra and its Applications, 29:471-508, 1980), show that

\begin{equation*} \lambda_1 \ge \frac{\det(A)}{(m+s/\sqrt{n-1})^{n-1}} \end{equation*}

Remark: As per the notation in the OP, $\lambda_1$ is the smallest eigenvalue---usually the literature uses $\lambda_1$ to be largest.

Thus, we obtain the upper bound \begin{equation*} \lambda_2\lambda_3\cdots\lambda_n \le \left(m+ \frac{s}{\sqrt{n-1}}\right)^{n-1}. \end{equation*} This bound is tight. Consider for example, If $A= \text{Diag}(1,2,2,\ldots,2)$, then the lhs is $2^{n-1}$, $m=2-1/n$, and $s^2 = 1/n-1/n^2$, so that $s/\sqrt{n-1} = 1/n$. Thus, the bound on the rhs is tight.

With $M := \max_{i,j}|a_{ij}|$, we see that $m \le M$ and $s^2 \le nM^2 - m^2$, which leads to an upper bound in terms of $M$ as desired

\begin{equation*} \lambda_2\lambda_3\cdots\lambda_n \le \left(M+ \sqrt{\frac{nM^2-m^2}{n-1}}\right)^{n-1} < \left(M + M\sqrt{\frac{n}{n-1}} \right)^{n-1}, \end{equation*} which is better than the bound mentioned in the post (though we lost a bit by deleting $m^2$).

$\endgroup$
3
  • $\begingroup$ Thanks Suvrit ! Your answer plus the argument to prove the theorem in the OP yields a very neat result (see the edited question). $\endgroup$ Apr 28, 2013 at 7:04
  • $\begingroup$ By the way, it is $s^2 \leq n M^2 - m^2$, right? It makes no difference to the applications I had in mind, because I'm interested in the case $m = M = 1$. $\endgroup$ Apr 28, 2013 at 12:43
  • $\begingroup$ Oops, sorry, you are right, it should be $nM^2-m^2$! When typing it up, I felt the $\sqrt{M}$ factor to be a bit odd. Let me update the answer! Thanks. $\endgroup$
    – Suvrit
    Apr 28, 2013 at 15:48

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.