4
$\begingroup$

I'm trying to come up with an upper bound for the Frobenius norm of the inverse of a non-singular matrix. To be precise, let $A \in \mathbb{C}^{n \times n}$ be non-singular, with entries denoted by $a_{ij}$, and let $$\|A\|_F = \sqrt{\sum_{i,j=1}^n |a_{ij}|^2}$$ be the Frobenius norm of $A$.

I'm trying to get an upper bound for $\|A^{-1}\|_F$ such that:

1) This bound doesn't rely on the computation of the determinant of $A$ nor its eigenvalues or singular values. 2) This bound doesn't need to be sharp, but can't be absurdly large (like something of exponential order).

Ideally, I'm looking for a bound relying on $n$, on the entries of $A$ and on any norm of $A$. Something like $\|A^{-1}\|_F \leq \sqrt{n}\left( \frac{\|A\|_2}{\|A\|_F} \right)^3$ would be ok (I just invented this bound as an example).

In fact, I've tried something, but I think someone could come up a better idea. Here is what I did:

Let $\sigma_1 \geq \ldots \sigma_n > 0$ be the singular values of $A$, so $$\|A\|_F = \sqrt{\sigma_1^2 + \ldots + \sigma_n^2}$$ and $$\|A^{-1}\|_F = \sqrt{\frac{1}{\sigma_1^2} + \ldots + \frac{1}{\sigma_n^2}}.$$

By this article (equation (1)), we have the lower bound $$\sigma_n \geq |\det A|\left( \frac{n-1}{\|A\|_F^2} \right)^\frac{n-1}{2}. $$

Therefore, $$\|A^{-1}\|_F = \sqrt{\frac{1}{\sigma_1^2} + \ldots + \frac{1}{\sigma_n^2}} \leq \sqrt{\frac{n}{\sigma_n^2}} = \frac{\sqrt{n}}{\sigma_n} \leq \frac{\sqrt{n}}{|\det A|} \left( \frac{\|A\|_F^2}{n-1} \right)^\frac{n-1}{2}.$$

But now I have the problem of bounding the determinant...

EDIT: I'm accepting lower bounds to the determinant and lowest singular value of $A$ as answers. The bound may be large, as long as it is directly accessible from the entries or the norm of $A$. Thanks.

$\endgroup$
  • $\begingroup$ Finding an upper bound without invoking singular values in some way seems like it's going to be impossible. To begin with, you should come with some kind of upper bound that would work for the case $$ \pmatrix{1\\&\ddots\\&&1\\&&&\epsilon} $$ for arbitrarily small $\epsilon > 0$. You'll find that it's difficult to do with the usual norms. $\endgroup$ – Omnomnomnom Aug 2 '17 at 21:29
  • $\begingroup$ If you can bound the norm of $A^{-1}$, then you can bound the lowest singular value of $A$ from below. It's the same thing up to a factor that depends only on $n$. So you are essentially asking "how to bound a singular value without involving singular values". $\endgroup$ – user357151 Aug 3 '17 at 2:57
  • $\begingroup$ @Alex There are bounds to the smallest singular value of $A$ without involving singular values. See the article in my post for instance. The only problem with this bound is that it relies on the determinant of $A$, which I want to avoid. So I'm still looking for better bounds. $\endgroup$ – Integral Aug 3 '17 at 3:18
  • $\begingroup$ @Omnomnomnom The Frobenius norm of the inverse of this matrix is $\sqrt{1^2 + \ldots + 1^2 + \frac{1}{\varepsilon}^2 } = \sqrt{n-1 + \frac{1}{\varepsilon^2}}$ right? So I don't even need to bother trying to find an upper bound to the norm, I have an equality. Even better, this equality doesn't rely on singular values, but rely only on the entries of the matrix, which is exactly what I'm looking for. $\endgroup$ – Integral Aug 3 '17 at 3:52
  • $\begingroup$ @Integral I think I'm operating under the assumption that any reasonable upper bound will be invariant under unitary changes of basis. Of course, taking the lower-left entry works in this case, but we shouldn't expect that to work in general; if we were looking at a matrix unitarily similar to mine, then $\epsilon$ would only be accessible as a lowest eigenvalue/singular value. $\endgroup$ – Omnomnomnom Aug 3 '17 at 4:26

Your Answer

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

Browse other questions tagged or ask your own question.