5
$\begingroup$

I encounter a symmetric positive definite matrix whose features are

  • all diagonal entries are $1$.
  • all the other entries are in $[0, 1)$, but the matrix is not diagonally dominant.

Now I am looking for a positive lower bound of the smallest eigenvalue, expressed by trace and Frobenius norm.

I have seen a lot of papers related to this topic. Especially, the result in this paper is very close to my goal. But that expression still involves the maximum eigenvalue and determinant. I have seen the answer of Lower bound on the smallest eigenvalue. I'm happy if the answer posted in that is correct. But I think it's wrong. Does that kind of lower bound exist?

Anyone could give me any tips? Thanks so much!

$\endgroup$
1
  • 1
    $\begingroup$ Are your matrices correlation matrices? What is the context? $\endgroup$ Jul 27, 2016 at 0:31

2 Answers 2

5
$\begingroup$

If it's an $n \times n$ matrix with all diagonal entries $1$, the trace is $n$, so that won't help. The Frobenius norm is bounded by $n$. Since the smallest eigenvalue can be arbitrarily close to $0$, I don't see how you could possibly get a nonzero lower bound in terms of the Frobenius norm.

$\endgroup$
4
  • $\begingroup$ Thanks so much for your reply. I think I have to detour this question. $\endgroup$
    – jack
    Jul 27, 2016 at 16:12
  • $\begingroup$ Hi, could you show me on how to construct such a s.p.d. matrix with the smallest eigenvalue arbitrarily close to 0? (it has 1's on the diagonal) $\endgroup$ Oct 22, 2019 at 16:00
  • 1
    $\begingroup$ @VinayakSuresh All $1$'s on the diagonal, all $1-\epsilon$ elsewhere. $\endgroup$ Oct 23, 2019 at 1:07
  • $\begingroup$ Ah yes I was able to realize this simple example half hour after I asked this question. Thanks! $\endgroup$ Oct 23, 2019 at 15:58
2
$\begingroup$

Let $\mathrm A \in [0,1)^{n \times n}$ be a symmetric, positive definite, nonnegative matrix whose diagonal entries are equal to $1$. Using the Gershgorin circle theorem, the minimum eigenvalue of $\mathrm A$ is bounded by

$$\lambda_{\min} (\mathrm A) \geq 1 - \max_{1 \leq i \leq n} \, \sum_{j \neq i} a_{ij} = 1 - \| \mathrm A - \mathrm I_n\|_{\infty}$$

Unfortunately, unless $a_{ij} \ll 1$, this bound is likely too loose. I suspect that this bound is only potentially useful for small perturbations of the identity matrix.

If the bound is not too loose, then, using the inequality $\| \cdot \|_{\infty} \leq \sqrt n \, \| \cdot \|_{F}$, we obtain

$$\lambda_{\min} (\mathrm A) \geq 1 - \| \mathrm A - \mathrm I_n \|_{\infty} \geq 1 - \sqrt n \, \| \mathrm A - \mathrm I_n \|_{F}$$

$\endgroup$
2
  • $\begingroup$ Thanks so much for your reply. But your bound cannot be guaranteed to be positive, right? $\endgroup$
    – jack
    Jul 27, 2016 at 16:34
  • $\begingroup$ @jack That is correct. $\endgroup$ Jul 27, 2016 at 16:56

You must log in to answer this question.

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