f(g(x)) = g(f(x)) (commuting mappings)
Moderators: gmalivuk, Moderators General, Prelates

 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!
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.
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
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.
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.

 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 id_{X}, f, f², f³,... (and f^{1} if it exists).
I mean except for the "trivial" ones like id_{X}, 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.
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.

 Posts: 23
 Joined: Sat Jan 14, 2012 11:50 pm UTC
Re: commutating maps
What is the difference? I thought it meant the same. But perhaps that's because I didn't pay enough attention in first semesterTalith 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.
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 semisatisfy 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
 closedminded 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
"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 semisatisfy 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.

 Posts: 23
 Joined: Sat Jan 14, 2012 11:50 pm UTC
Re: f(g(x)) = g(f(x)) (commuting mappings)
Thank you for your answers so far!
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?
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?
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)
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 mikeI was mentioning.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 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)=x_{1}, f^{2}(x)=x_{2}, f^{3}(x)=x_{3},...
we would identify this with the quiver: •→•→•→•→...
If we have an orbit like f(x)=y, f^{2}(x)=x, f^{3}(x)=y,...
this would be the quiver: •↔•
id_{x} 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)=x_{1}, f^{2}(x)=x_{2},
f(y)=y_{1}, f^{2}(y)=y_{2},
f^{3}(x)=x_{3}=y_{3}=f^{3}(y),
f^{4}(x)=f^{4}(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?
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)=x_{1}, f^{2}(x)=x_{2}, f^{3}(x)=x_{3},...
we would identify this with the quiver: •→•→•→•→...
If we have an orbit like f(x)=y, f^{2}(x)=x, f^{3}(x)=y,...
this would be the quiver: •↔•
id_{x} 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)=x_{1}, f^{2}(x)=x_{2},
f(y)=y_{1}, f^{2}(y)=y_{2},
f^{3}(x)=x_{3}=y_{3}=f^{3}(y),
f^{4}(x)=f^{4}(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
 closedminded 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
"With math, all things are possible." —Rebecca Watson

 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 welldefined(!) gfuctions 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
 closedminded 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 welldefined(!) gfuctions 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
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 11 guests