Re: Help with Diagonal subgroup problem

From: Arturo Magidin (magidin_at_math.berkeley.edu)
Date: 11/17/04 

Date: Wed, 17 Nov 2004 19:44:08 +0000 (UTC)

In article <20041116233942.14312.00000719@mb-m13.aol.com>,
Warren065 <warren065@aol.com> wrote:
>>Subject: Re: Help with Diagonal subgroup problem
>>From: magidin@math.berkeley.edu (Arturo Magidin)
>>Warren065 <warren065@aol.com> wrote:
>>>D is a subgroup of G=M x N (INTERNAL direct product) is a diagonal subgroup
>>if
>>>(D intersect M) = 1 = (D intersect N) and DM=G=DN.
>>>
>>>Show that G has a diagonal subgroup IFF M is isomorphic to N.
>>>
>>><== ?????????????
>>
>>Let D be the "graph" of the isomorphism from M to N: fix f:M->N which
>>is an isomorphism, and let D = {(m,f(m)) : m in M}.
>
>I had asked another student about this and they basically said something
>similar -- (m, f(m)) and they claimed it was just 'trivial' after that. I
>guess that I just don't 'see' anything. It says "diagonal" subgroup, so I
>assume that means on a 'graph' it would be the diagonal from left to right
>across only.

As someone pointed out, it is called "diagonal" because in the special
case when M=N (which you can assume up to isomorphism if M is
isomorphic to N) and f=id, you get the literal diagonal.

>I need to show that DM=G=DN and (D intersect M)=1=(D intersect N). Unless D
>itself is just the identity (doesn't make sense to me), it would seem that M
>and N could fill up the entire graph and equal G.

G is not the "graph". G would be more like the plane: G=MxN.

So, assume f:M->N is an isomorphism. let G = MxN, and let

D = {(m,f(m)) in G: m in M}.

Notice that for each "point" on the "x-axis" M, there is one and only
one "point" on the "y-axis", N; that's why this is sometimes called
the "graph" of the isomorphism.

M is identified with the subgroup {(m,1) in G: m in M} of G; N
corresponds to the subgroup {(1,n) in G: n in N}.

Then D intersect M = {(m,f(m)) in G: m in M, f(m)=1}.

Since f is an isomorphism, it is injective, so the only m for which
f(m)=1 is m=1. Thus, D intersect M = {(1,1)}, the trivial element of
G.

Likewise, D intersect N = {(m,f(m)) in G: m in M, m=1}. Since f is a
group homomorphism, f(m)=1, so D intersect N = {(1,1)}, the trivial
element of G.

Now we want to show that DM = G. That is, that the set of all products
of the form

(r,f(r))(m,1) = (rm, f(r)1) = (rm, f(r)).

with m, r in M, cover all elements of G.

Well, let (x,y) be an element of G. We want to express it in the form
(r,f(r))(m,1) = (rm, f(r)) for some r,m in M.

Since f is an isomorphism, it is surjective, so there exists r in M
such that f(r)=y. And then if we let m = r^{-1}x, which lies in M, we
have

(r,f(r))(m,1) = (rm,f(r)) = (rr^{-1}x,y) = (x,y). Thus, G is contained
in DM, and hence (since DM is certainly contained in G), equal to DM.

Now do something similar to show that G = DN. 

-- 
======================================================================
"It's not denial. I'm just very selective about
 what I accept as reality."
    --- Calvin ("Calvin and Hobbes")
======================================================================
Arturo Magidin
magidin@math.berkeley.edu

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... exchanged is isomorphic to the original graph, which is as it should be. ... the same node hash values with the same duplicate values. ... Once the actual isomorphism mapping is reported, ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... exchanged is isomorphic to the original graph, which is as it should be. ... the same node hash values with the same duplicate values. ... Once the actual isomorphism mapping is reported, ... I'm worried about the classic Zero Knowledge proof a Hamiltonian circuit. ...
    (sci.crypt)
  • Re: copyright for combinatorial entities
    ... graph, if for no other reason than doing so would fly in the ... face of the reason for having copyright in the first place, ... blocking the publication of an adjacency matrix ... isomorphism is another issue. ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... graph and Hamiltonian cycle problems,, Victor ... If graph isomorphism is in RP (as ... about the circuit in G by being shown the circuit in H. ... the prover either sends keys to unlock only edges that form a Hamiltonian circuit or sends the permutation of the nodes that constitutes the isomorphism and keys to unlock all edges. ...
    (sci.crypt)
  • Re: 2 questions on group homomorphisms
    ... subgroup Lof a group K. If each proper subgroup of G is isomorphic ... with each proper subgroup of K and there is a bijection L->L, ... of K corresponding to S under the isomorphism of, ... The subgroup lattice of ^k is EQUAL to the ...
    (sci.math)