## f(g(x)) = g(f(x)) (commuting mappings)

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### f(g(x)) = g(f(x)) (commuting mappings)

I have the following mathematical problem and no idea where to find a solution for it. Perhaps one of you can help?

Given a set X and a map f:X-->X
Let G be the set of maps, that commutate with f, that is: G = {g:X-->X | g°f = f°g}
How can I find and describe G?

X may be any kind of set, but if it helps to find a (partial) solution, we can assume it is a vector space, with f not necessarily linear.

Thanks for your help! Last edited by thefreiburger on Fri May 11, 2012 10:10 am UTC, edited 2 times in total.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: commutating maps

I'm going to assume that f is a bijection (as otherwise fog=gof doesn't make any sense) in which case g must also be a bijection and so your G is the centraliser of f in the automorphism group of X in the category of sets. In this category, Aut(X) is isomorphic to the symmetric group on |X| elements where |X| is the cardinality of X.

If there are any other restrictions on X or f then you'd have to make them explicit. The automorphism group of X is dependant on what category X is an object in.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: commutating maps

fg and gf make sense as long as they're both endomorphisms, no need for bijections. For example, if f is the constant map f(x) = c, then G is all g that fix c.

In general, everything in G must map the image of f to the image of f (though not necessarily in any nice way). With no restrictions on what g can be, it's going to be a pretty big and hairy set, and I'm not sure that there is a better description than 'the functions that commute with f'.

There are some nice things, like G is a monoid (if a, b in G then so is a*b), and contains f.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### Re: commutating maps

Any idea how to find those g in G, or at least some of them?
I mean except for the "trivial" ones like idX, f, f², f³,... (and f-1 if it exists).

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: commutating maps

Ok, so rather than fog=gof, you want f(g(x))=g(f(x)) for all x in X. It's a subtle but important difference. in that case, you might need to give some more context for the problem as it's a bit too vague at the moment.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

### Re: commutating maps

I would guess that a "nontrivial nice description" doesn't exist, else you could provide "nontrivial nice descriptions" of centralizers for arbitrary groups.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### Re: commutating maps

Talith wrote:rather than fog=gof, you want f(g(x))=g(f(x)) for all x in X. It's a subtle but important difference.
What is the difference? I thought it meant the same. But perhaps that's because I didn't pay enough attention in first semester I'm afraid I cannot give any more context other than that a solution for the special case that X is a vector space would already semi-satisfy me What I'm really searching for is a general formula or algorithm that takes f and returns G.
If that isn't possible, it would still be great to be able to decide whether G = <f> or G > <f> (sorry, cannot find the symbol for "supset")

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: commutating maps

Talith wrote:Ok, so rather than fog=gof, you want f(g(x))=g(f(x)) for all x in X. It's a subtle but important difference. in that case, you might need to give some more context for the problem as it's a bit too vague at the moment.

I'm really confused. Actually, I think you're confused. AFAIK, the only two definitions for functions that exist entail that either A) a function is determined by its graph, or B) a function is determined by its codomain and graph. Under definition A, f(g(x))=g(f(x)) for all x, then fog=gof. Under definition B, you additionally need that codom(fog)=codom(gof) for the two functions to be equal. But here, codom(fog)=codom(f)=X, and codom(gof)=codom(g)=X, so the functions will be equal iff their graphs are equal, i.e. iff f(g(x))=g(f(x)) for all x in X. So regardless of which definition you are using, we just want to find the set
{g: X -> X : f(g(x))=g(f(x)) for all x in X}.

Unless you know some other definition of function which is neither A nor B?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: commutating maps

thefreiburger wrote:I'm afraid I cannot give any more context other than that a solution for the special case that X is a vector space would already semi-satisfy me What would actually help is not just changing the domain of the functions, what would help is changing what functions are legal. For instance, if you just restrict to those f and g which are linear transformations, you can get a pretty useful answer by putting some thought into how Jordan normal form works.

http://en.wikipedia.org/wiki/Jordan_normal_form

What I'm really searching for is a general formula or algorithm that takes f and returns G.
If that isn't possible, it would still be great to be able to decide whether G = <f> or G > <f> (sorry, cannot find the symbol for "supset")

One option is to go through X orbit by orbit and see what needs to happen.

So, for instance, if you have a 5 point space X= {1,2,3,4,5}, with f(1)=2, f(2)=1, f(3) = 4, f(4)=5, f(5)=3, then the orbits are Orbits(f) = {{1,2}, {3,4,5}}. So, can you have a g that maps an element of the first orbit to the second, or vice versa? What does that tell you about the which g are legal? Go through and define g orbit by orbit, see what happens.

In general, if you have only one orbit, and f is invertible, I think you can prove that G=<f>, but that's a pretty unlikely case.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

### Re: commutating maps

skeptical scientist wrote:I'm really confused. Actually, I think you're confused. AFAIK, the only two definitions for functions that exist entail that either A) a function is determined by its graph, or B) a function is determined by its codomain and graph. Under definition A, f(g(x))=g(f(x)) for all x, then fog=gof. Under definition B, you additionally need that codom(fog)=codom(gof) for the two functions to be equal. But here, codom(fog)=codom(f)=X, and codom(gof)=codom(g)=X, so the functions will be equal iff their graphs are equal, i.e. iff f(g(x))=g(f(x)) for all x in X. So regardless of which definition you are using, we just want to find the set
{g: X -> X : f(g(x))=g(f(x)) for all x in X}.

Unless you know some other definition of function which is neither A nor B?

You're right, I confused myself between the definition of codomain and image. I guess I've been working too much with automorphisms recently.

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### Re: f(g(x)) = g(f(x)) (commuting mappings)

I am especially fund of jestingrabbits method Going through the orbits and see what happens is definitely a very smart idea.
I've tried to think that idea a bit further and come up with this so far:
It should be possible to identify each orbit with a quiver ( = directed graph), but you would have to allow infinite quivers, if there is such a thing.
A function g may commute those orbits with each other, that are isomorphic (in the sense that their quivers are isomorphic).
I believe that every g that commutes isomorphic orbits, is legal and the other way around, but that's just a conjecture.
If this is true, it would always be possible to find the whole set of G, when you have all the orbits of f.

Am I thinking right?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: f(g(x)) = g(f(x)) (commuting mappings)

The converse is certainly false. If f has a fixed point, then it commutes with the constant map to that fixed point.

Even the main direction needs some work in terms on what you mean by 'commutes those orbits', for example (123)(456) does not commute with (14)(26)(35)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: f(g(x)) = g(f(x)) (commuting mappings)

thefreiburger wrote:A function g may commute those orbits with each other, that are isomorphic (in the sense that their quivers are isomorphic).
I believe that every g that commutes isomorphic orbits, is legal and the other way around, but that's just a conjecture.

I believe that this is only true if we restrict f and g to invertible maps, and where by "commute those orbits" we mean that g restricted to a particular orbit is a graph isomorphism, where we use the graphs to represent the action of the function.

Otherwise we do have problems of the kind mike-I was mentioning.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### Re: f(g(x)) = g(f(x)) (commuting mappings)

Ok, you are right, there was a mistake in my thinking.

Maybe I should specify what I mean by "isomorphic orbits", or at least try to describe what I have in mind:
If we have an orbit like f(x)=x1, f2(x)=x2, f3(x)=x3,...
we would identify this with the quiver: •→•→•→•→...
If we have an orbit like f(x)=y, f2(x)=x, f3(x)=y,...
this would be the quiver: •↔•
idx would be a single vertex with an arrow mapping that vertex into itself.
More generally, every finite orbit would be a quiver ending in a loop or being a circle.

If we have two or more orbits that merge at a certain point, like
f(x)=x1, f2(x)=x2,
f(y)=y1, f2(y)=y2,
f3(x)=x3=y3=f3(y),
f4(x)=f4(y)=...
I would combine them to get one quiver:
•→•→•→•→•→...
•→•→•

I hope you understand what I mean...
NOW I am saying that a g, which is a graph isomorphism, that maps every orbit (=quiver) into another quiver of the same shape, is legal.
Am I right now? skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: f(g(x)) = g(f(x)) (commuting mappings)

thefreiburger wrote:NOW I am saying that a g, which is a graph isomorphism, that maps every orbit (=quiver) into another quiver of the same shape, is legal.
Am I right now? Yes, such a map will commute with f. Since f just moves everything one arrow forward, and g is a graph isomorphism (and maps arrows to arrows), f and g will commute. More generally, if g is any graph homomorphism, it will commute with f. This is an equivalence: g commutes with f iff g is a homomorphism of the digraph induced by f in the way we have been describing.

There's not really any "meat" to this equivalence—it's just a way of restating the condition that f and g commute, in different language.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

thefreiburger
Posts: 23
Joined: Sat Jan 14, 2012 11:50 pm UTC

### Re: f(g(x)) = g(f(x)) (commuting mappings)

skeptical scientist wrote:There's not really any "meat" to this equivalence

I disagree! There is quite a lot "meat" to it, because we can now systematically construct well-defined(!) g-fuctions AND we can estimate their minimum number!
There would still be some more possibilities for g than we can construct that way, but we do at least have a partial solution now. Thank you so far skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: f(g(x)) = g(f(x)) (commuting mappings)

thefreiburger wrote:
skeptical scientist wrote:There's not really any "meat" to this equivalence

I disagree! There is quite a lot "meat" to it, because we can now systematically construct well-defined(!) g-fuctions AND we can estimate their minimum number!

I just mean that the proof of the equivalence is just "definition chasing" and doesn't involve any deep insight. But you're right, sometimes just having a rephrasing of the definition can make some things more apparent.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson