Author |
Topic: Invertibility of I - AB (Read 7160 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Invertibility of I - AB
« on: Apr 9th, 2004, 11:16pm » |
 Quote  Modify
|
Let A and B be square matrices. Now suppose I - BA is invertible, where I is the identity matrix. Prove that this implies I - AB is also invertible.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Invertibility of I - AB
« Reply #1 on: Apr 11th, 2004, 4:11am » |
Quote Modify
|
[smiley=blacksquare.gif]
Assume one of the matrices – say, A – is invertible. Then (|X| is determinant of X):
|I-BA| = |I-BA||A-1||A| = |A||I-BA||A-1| = |A||A-1-B| = |I-AB|.
Thus, if |I-AB| [ne] 0, so is |I-BA|.
This argument fails if both A, B are singular. I do not have a satisfactory demonstration in this case. An informal way is as follows. Assuming it is legal to represent (I-X)-1 as power series for any X, we get:
(I-BA)-1 = I + BA + (BA)2 + (BA)3 + .. = I + B(I + AB + (AB)2 + (AB)3 + ...)A = I + B(I-AB)-1A.
[smiley=blacksquare.gif]
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #2 on: Apr 11th, 2004, 12:58pm » |
Quote Modify
|
on Apr 11th, 2004, 4:11am, Barukh wrote:| Assuming it is legal to represent (I-X)-1 as power series for any X, ... |
|
It is, and quite formal too.
|
| « Last Edit: Apr 11th, 2004, 1:01pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Invertibility of I - AB
« Reply #3 on: Apr 11th, 2004, 4:53pm » |
Quote Modify
|
Nice job. We can't assume that A or B are invertible, but the second argument works. Although I'm not sure that (I - X)-1 can be legally written as a power series expansion for any X (I think you need the matrix norm of X to be < 1), it actually doesn't matter in this case ... one can verify that your final expression is indeed the matrix inverse of (I-BA).
(In case anyone is confused: Barukh solves the problem where I - AB invertible [to] I-BA invertible, the direction opposite to that in the problem statement. However the solution in either direction is the same.)
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #4 on: Apr 11th, 2004, 5:57pm » |
Quote Modify
|
on Apr 11th, 2004, 4:53pm, william wu wrote:| I think you need the matrix norm of X to be < 1 |
|
Yep - I'm always quick to insert my foot in my mouth. Of course it only converges when ||X|| < 1.
But as you said, it was a very nice job anyway. By examining the case where it does converge, you get a very satisfactory, easy to follow, derivation of the form of the inverse, which can then be shown to hold even when the series does not converge.
An inspired approach, Barukh!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #5 on: Apr 11th, 2004, 7:46pm » |
Quote Modify
|
Thinking about this has made me wonder - is there a way to define I + X + X2 + ... so that it converges for all X? Perhaps by using a different topology instead of the normal one (coming from the norm ||X|| = det(XX*) ||X|| = tr(XX*)). Or maybe in some formal fashion.
If we were to stick with this series only, a simple formal definition presents itself: I + X + X2 ... := (I - X)-1, convergent whenever det(I - X) [ne] 0. But this does not generalize to other series.
Is there a looser definition of convergence that would allow Barukh's original derivation to hold for any AB, rather than those with norm < 1?
|
| « Last Edit: Apr 12th, 2004, 4:09pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Invertibility of I - AB
« Reply #6 on: Apr 12th, 2004, 9:17am » |
Quote Modify
|
on Apr 11th, 2004, 4:53pm, william wu wrote:| Although I'm not sure that (I - X)-1 can be legally written as a power series expansion for any X (I think you need the matrix norm of X to be < 1) |
|
Very interesting! For what norm (There seem to be a few ones used)? Have you got a formal proof for this? Also:
on Apr 11th, 2004, 7:46pm, Icarus wrote:| Thinking about this has made me wonder - is there a way to define I + X + X2 + ... so that it converges for all X? Perhaps by using a different topology instead of the normal one (coming from the norm ||X|| = det(XX*)). Or maybe in some formal fashion. |
|
I checked the definition of matrix's norm and haven't encountered anything like this. Moreover, it seems to contradict one the properties of the matrix norm saying: ||X|| = 0 iff X=0.
on Apr 11th, 2004, 5:57pm, Icarus wrote:| An inspired approach, Barukh! |
|
Thanks. I've learnt it from another subject – the group theory.
Quote:| it actually doesn't matter in this case ... one can verify that your final expression is indeed the matrix inverse of (I-BA). |
|
Hmm… How?
By the way, I just encountered a nice argument showing that |I-AB| = |I-BA| for all matrices A, B: consider the following nice identity:
[I-AB A; 0 I] * [I 0; B I] = [I 0; B I] * [I A; 0 I-BA]
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Invertibility of I - AB
« Reply #7 on: Apr 12th, 2004, 11:58am » |
Quote Modify
|
on Apr 12th, 2004, 9:17am, Barukh wrote:
Very interesting! For what norm (There seem to be a few ones used)? |
|
Any, I think, since
||AB|| [le] ||A|| * ||B|| and
||A+B|| [le] ||A|| + ||B||
has to hold for any of them.
You want the norm for the series [sum](AB)n to be finite (otherwise the values in the matrix aren't, and so it wouldn't be real). So with the above we get
||[sum](AB)n|| [le] [sum]||(AB)n|| [le] [sum]||(AB)||n,
this is just a geometric series.
If now ||AB|| < 1 this is obviously finite, like we want.
This doesn't exclude other possible solutions with ||AB|| >=1 however
on Apr 11th, 2004, 7:46pm, Icarus wrote:| Thinking about this has made me wonder - is there a way to define I + X + X2 + ... so that it converges for all X? |
|
Well, no, not unless you redefine addition or multiplication on matrices  .. For[2,0;0,2] for instance it can never converge,
[sum]ni=0[2,0;0,2]i gives [2k+1 - 1, 0; 0, 2k+1 - 1]
and I don't have to tell you what that does when n goes to [infty]
|
| « Last Edit: Apr 12th, 2004, 12:22pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #8 on: Apr 12th, 2004, 4:43pm » |
Quote Modify
|
on Apr 12th, 2004, 9:17am, Barukh wrote:
Very interesting! For what norm (There seem to be a few ones used)? Have you got a formal proof for this? Also:
I checked the definition of matrix's norm and haven't encountered anything like this. Moreover, it seems to contradict one the properties of the matrix norm saying: ||X|| = 0 iff X=0.
|
|
My apologies. The standard norm on gl(n, [bbc]) is tr(XX*), not det(XX*). It is also easily seen to be [sum] |aij|2. So in effect you are treating gl(n, [bbc]) as [bbc]n^2.
As with any norm, there are several other norms on gl(n, [bbc]) which give rise to the same topology.
Quote: Let K=(I - AB)-1
Then your form is I + BKA. So
(I-BA)(I+BKA) = I - BA + BKA - BABKA = I - BA + B(I-AB)KA = I - BA + BIA = I.
Hence (I - BA)-1 = I + BKA, as you calculated.
Quote:By the way, I just encountered a nice argument showing that |I-AB| = |I-BA| for all matrices A, B: consider the following nice identity:
[I-AB A; 0 I] * [I 0; B I] = [I 0; B I] * [I A; 0 I-BA] |
|
Nice, but incomplete. Do you know how to calculate the determinant of the outer matrices in terms of the inner ones? It is not quite as nice as the result for matrices of numbers.
on Apr 12th, 2004, 11:58am, towr wrote:Well, no, not unless you redefine addition or multiplication on matrices .. For[2,0;0,2] for instance it can never converge,
[sum]ni=0[2,0;0,2]i gives [2k+1 - 1, 0; 0, 2k+1 - 1]
and I don't have to tell you what that does when n goes to [infty] |
|
You don't redefine addition or multiplication. What you redefine is the limit, and maybe the space. I can easily make [sum] (2I)n converge by simply adding an extra point to gl(n, [bbc]) to be the limit. Of course, this is not what I am after. I want it to converge to -I. But that means I will need a different topology than the normal one.
Alas, but even if such a topology exists (one that works for all such series beyond their normal radii of convergence), it is almost certain that addition and multiplication will not be continuous under it, which means far more trouble than such an approach is worth. So my "bright idea" is more likely a fool's quest. Still, it might be interesting to explore.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Invertibility of I - AB
« Reply #9 on: Apr 13th, 2004, 12:57am » |
Quote Modify
|
Thanks everybody for insightful explanations 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Invertibility of I - AB
« Reply #10 on: Apr 13th, 2004, 2:53am » |
Quote Modify
|
on Apr 12th, 2004, 4:43pm, Icarus wrote:| I can easily make [sum] (2I)n converge by simply adding an extra point to gl(n, [bbc]) to be the limit. |
|
To be honest I have no idea what this means.. What is gl(n, [bbc]) ? What does adding extra points to it mean, and what does it have to do with limits?? And how can that cause lim n[to][infty] 2i to be smaller than [infty] (or isn't that what it comes down to?)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #11 on: Apr 13th, 2004, 5:22pm » |
Quote Modify
|
gl(n, [bbc]) is the algebra of n x n matrices with complex entries. I.e. it is the set of all n x n complex matrices, but considered as a normed algebra over [bbc]. (It should not be confused with the "general linear group" GL(n, [bbc]), which consists of invertible matrices only.)
As for the rest, you can add points to any space. For example, if you add "+[infty]" and "-[infty]" to [bbr], you get the extended reals [bbr]*. In the extended reals, all limits that "diverged" to +[infty] or -[infty] in [bbr] now "converge" to the extra points added. Just adding these two points makes a large number of previously non-convergent limits convergent (but not all - limx[to][subinfty] sin x still diverges, for instance). Note that the nature of these limits have not changed. They still climb, but now they have a target to climb to, instead of passing all targets on the way.
A similar trick is very useful for [bbc]. By adding a single point, [infty], which serves as a target for all limits that climb in absolute value without bound, you get the Riemann Sphere, which has many nice properties. You can find a fuller description in a post I did about it in the Complex Analysis forum.
Another example of the same thing occurs in the development of [bbr] itself. The Rationals are easily identified in abstract algebra as the minimal field of characteristic 0. To get [bbr], you must move beyond algebra into topology. Topologically, the rationals are very poorly behaved, but they do have a natural norm in the absolute value. Using this norm, we find that [bbq] has multitudinous cauchy sequences that do not converge. We solve this problem by calling cauchy sequences equivalent if the norm of their difference converges to zero. Then we introduce a new point for every equivalence class of non-convergent cauhy sequences (ie, every maximal set of equivalent sequences). The result is a set that contains [bbq], and inherits most of the properties of [bbq], but is much larger. That set is the set of real numbers [bbr].
But the absolute value is not the only possible norm on [bbq]. For instance, every rational number r [ne] 0 is expressible uniquely as 2k(p/q), where k is an integer, and p & q are odd. Define the norm [parallel]r[parallel] = 2-k ([parallel]0[parallel] = 0). You can check that it really does meet the conditions to be a norm:
(1) [parallel]r[parallel] > 0 for r [ne] 0.
(2) [parallel]r + s[parallel] [le] [parallel]r[parallel] + [parallel]s[parallel].
Under this norm, which sequences converge and what they converge to are much different than with the absolute value. For instance, limk[to][subinfty] 2k = 0, while limk[to][subinfty] 2-k diverges. If you complete the rationals using this norm instead of the absolute value, you get the 2-adic numbers (the norm is called the 2-adic norm). If you recall my thread in the hard section about the 10-adic numbers, you can see that they are a very different beast from the reals.
Something along these lines was the gist of my likely-not-so-bright inspiration. Could a norm (or a more general approach) be found so that [sum] Xk converged to (I - X)-1 whenever the latter existed? If it exists, this norm would differ drastically from the ordinary one, just as the 2-adic norm does from the absolute value. As such, it would completely change the concept of what is large and what is small.
I am almost completely certain that such a norm does not exist. For example, in the 2-adic numbers, [sum] 2k = -1, but [sum] (1/2)k diverges. So while I gained something I wanted by switching to this norm, I lost what I already had. I expect that it is asking too much for one norm to work in all situations. But there is still the possibility that a different definition of "limit", not based on norms, might give me everything I want (including that it be a useful concept - otherwise it would be easy! ).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Invertibility of I - AB
« Reply #12 on: Apr 14th, 2004, 12:56am » |
Quote Modify
|
does something like that also make it possible to converge [sum](-I)n?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #13 on: Apr 14th, 2004, 7:51pm » |
Quote Modify
|
That one - equivalently, the sequence an = 0 for n odd, = 1 for n even - will not converge under any conventional (topological) meaning of "limit" in which sequences have unique limits. (Every space has a trivial topology wherein all limits converge, but each converges to every point in the space!)
So no, you can't have that sum converging even by more general means than I described. You could concoct a meaning for "limit" which would provide a value for such sequences (I know of one means to assign limits to that and many other sequences), but how far can you go from our normal ideas of limits and still be justified in calling it a "limit"?
One means of making {an} "convergent" is to use Cesaro summation as your limiting process: Define
Climn[to][subinfty] ah = limN[to][subinfty] (1/N) [sum]n=1N an.
Clim [sum] (-1)n = 1/2.
(The same thing can be applied in gl(n, [bbc]), but we might as well discuss the much friendlier domain of [bbr] itself.)
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Invertibility of I - AB
« Reply #15 on: Apr 15th, 2004, 4:01pm » |
Quote Modify
|
Yes, I am. Be careful of the notation here: the sequence being Cesaro summed is not (-1)n, but an = [sum]k=0n (-1)n = {1 for n even, 0 for n odd}.
So Climn [sum]n (-1)k = Climn an = limN (1/N)[sum]N an = limN (1/N)(1+[lfloor]N/2[rfloor]) = 1/2.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Invertibility of I - AB
« Reply #16 on: Apr 15th, 2004, 11:49pm » |
Quote Modify
|
on Apr 15th, 2004, 4:01pm, Icarus wrote:| Yes, I am. Be careful of the notation here: the sequence being Cesaro summed is not (-1)n |
|
oops.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Whosoever
Guest
|
|
Re: Invertibility of I - AB
« Reply #17 on: Nov 18th, 2004, 12:57am » |
Quote Modify
 Remove
|
Hi,
Though its too late to respond, but there is a simpler way by which you can show the above. And if I remember right, we did this way back in 2nd year of Engineering. Here it is.
Let X be inverse of (I-AB).
then X(I-AB)A=X(A-ABA)
A=XA(I-BA)
BA=BXA(I-BA)
I-BA=I-BXA(I-BA)
(I-BA)+BXA(I-BA)=I
(I+BXA)(I-BA)=I
and voila..
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print