Re: order of magnitude of an inverse

On 14 Aug 2006 04:08:53 -0700, "oercim" <oercim@xxxxxxxxx> wrote:


Robert Israel wrote:
In article <1155460729.954548.143870@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
oercim <oercim@xxxxxxxxx> wrote:
If A = O(n) + aO(sqrt(n)) , then what is the
order of
magnitude of A (-1). Here a is unknown, it can be a scalar or a
function of n

Not determined.

Sorry, I wasn't clear. With A (-1) , I meant A^(-1).


What is A? A function of n, I guess, but are the values
numbers, matrices, what? Also, I presume you're talking about
integers n -> infinity?

A is a matrix. Yes, i am talking about as n goes to infinity.


If a is constant (i.e. not dependent on n), then
O(n) + a O(sqrt(n)) = O(n). All this means is that there are
some constants N and K such that |A| <= K n for n > N (if
A is a matrix, this means all |A_{ij}| <= K n for n > N).
If a is a function of n, then without further information
on a there's nothing you can say.

Can't we say about the order of magnitude in terms of a? (for
example:
A^(-1)=a^(-1)O(n^(-1)).


If A = O(n), there's no guarantee that A^(-1) exists: A could
be 0. If A is a number and nonzero, A^(-1) = Omega(1/n),
i.e. there exist constants N and K > 0 such that
|A^(-1)| >= K/n for n > N.
Assume A exists. I think A^(-1) should be
O(n^(-1))+a^(-1)O(n^(-1/2)).

That simply doesn't follow from anything you've said.

For an example with scalar A, let A = 0 for all n.
Then it's true that A = O(n) + aO(sqrt(n)) with
a = 1. But A^{-1} does not even exist.

And let say if a=1/n then
A^(-1)=O(n^(-1))+a^(-1)O(n^(-1/2))

=O(n^(-1))+O(n^(1/2))
=O(n^(1/2))

Am I right? Thanks a lot.



Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada


************************

David C. Ullrich
.

Relevant Pages