Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
Thanks Suvrit ! Your answer plus the argument to prove the theorem in the OP yields a very neat result (see the edited question). –  alvarezpaiva Apr 28 '13 at 7:04
    
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$. –  alvarezpaiva Apr 28 '13 at 12:43
    
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. –  Suvrit Apr 28 '13 at 15:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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