Page 1 of 1

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

Posted: Tue May 08, 2012 6:20 pm UTC
by thefreiburger
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! :)

Re: commutating maps

Posted: Tue May 08, 2012 7:13 pm UTC
by Talith
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.

Re: commutating maps

Posted: Tue May 08, 2012 7:55 pm UTC
by mike-l
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.

Re: commutating maps

Posted: Tue May 08, 2012 10:46 pm UTC
by thefreiburger
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).

Re: commutating maps

Posted: Tue May 08, 2012 10:49 pm UTC
by Talith
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.

Re: commutating maps

Posted: Tue May 08, 2012 11:31 pm UTC
by z4lis
I would guess that a "nontrivial nice description" doesn't exist, else you could provide "nontrivial nice descriptions" of centralizers for arbitrary groups.

Re: commutating maps

Posted: Tue May 08, 2012 11:35 pm UTC
by thefreiburger
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 :P

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 :wink:

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")

Re: commutating maps

Posted: Wed May 09, 2012 12:07 am UTC
by skeptical scientist
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?

Re: commutating maps

Posted: Wed May 09, 2012 12:21 am UTC
by jestingrabbit
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 :wink:


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.

Re: commutating maps

Posted: Wed May 09, 2012 1:14 am UTC
by Talith
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.

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

Posted: Fri May 11, 2012 10:54 am UTC
by thefreiburger
Thank you for your answers so far!

I am especially fund of jestingrabbits method :D 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?

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

Posted: Fri May 11, 2012 1:07 pm UTC
by mike-l
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)

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

Posted: Sun May 13, 2012 11:15 am UTC
by jestingrabbit
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.

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

Posted: Sun May 13, 2012 8:35 pm UTC
by thefreiburger
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? :lol:

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

Posted: Sun May 13, 2012 10:54 pm UTC
by skeptical scientist
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? :lol:

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.

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

Posted: Tue May 15, 2012 12:26 am UTC
by thefreiburger
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 :D

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

Posted: Sun May 20, 2012 9:32 pm UTC
by skeptical scientist
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.