Group Automorphisms & the Graph
Isomorphism problem
Juspreet Singh Sandhu
I’ve decided to write a post on Automorphisms in Groups as it seems to
produce numerous questions on Quora. In this post, I’ll outline the definition of
an Automorphism (for Groups), the Automorphism Group of a Group, Auto-
morphisms in Cyclic Groups, a general theorem regarding Automorphisms, and
their connection to Graph Theory.
Def
n
: Automorphism - A function f : G → G , , f(ab) = f(a)f(b) , ∀
a, b ∈ G, where G is a group - G =< S, . >
Intuitively, an Automorphism is just an Isomorphism from a group to itself.
The Trivial Automorphism : The trivial automorphism is the identity func-
tion : f(x) = x , which is also called (x)
All isomorphisms are basically bijections that preserve an operation on the set.
Every bijection is a permutation. Therefore, one can think of Automorphisms
as symmetry preserving permutations from a group to itself.
Let’s move on to the Automorphism Group:
Def
n
: Automorphism Group : A =< {a
1
, .., a
k
}, ◦ > , ∀ a
i
as automorphisms
of a Group G.
Claim: The Set of all Automorphisms A of a set S is a Group.
Proof : We’ll show closure, the existence of the identity element, and the exis-
tence of the inverse.
a) Closure:
Let a
i
, a
j
∈ A .
Let a
l
= a
i
◦ a
j
We will show that (a
l
is a bijection) ∧ (a
l
preserves adjacency).
We know thata
l
is a bijection as it is a composition of 2 bijective functions.
For adjacency preservation, we know that a
i
, a
j
preserve adjacency.
So, we need to show that : a
l
(ab) = a
l
(a)a
l
(b), ∀ a, b ∈ G
Let’s start with the LHS :
a
l
(ab) = a
i
◦ a
j
(ab) = a
i
(a
j
(a)a
j
(b)) = a
i
(a
j
(a))a
i
(a
j
(b))
For the RHS :
a
l
(a)a
l
(b) = (a
i
◦ a
j
(a))(a
i
◦ a
j
(b)) = a
i
(a
j
(a))a
i
(a
j
(b))
LHS = RHS
1
As a
l
is a bijection from G → G, and it preserves adjacency, a
l
is an Auto-
morphism.
b) Identity Element:
By definition, if, ∃ e , ,e◦ a
i
= a
i
◦e = a
i
, ∀ a
i
∈ G , then e is the Identity
Element of G.
Now, we can clearly see that the trivial automorphism fulfills this require-
ment as ◦ a
i
= (a
i
(x)) = a
i
The same can be easily shown for the inverse.
c) Inverse Element:
By definition, an inverse a
−1
i
for some a
i
∈ G, is the element, ,a
i
◦ a
−1
i
=
a
−1
i
◦ a
i
= e
Again, if a
−1
i
is an Automorphism, it must belong to A by definition.
We need to show: (a
−1
i
is a bijection) ∧ (a
−1
i
(preserves adjacency).
We know that a
−1
i
is a bijection as the inverse of a bijective function is a
bijection.
So, we need to show that a
−1
i
(ab) = a
−1
i
(a)a
−1
i
(b)
Again, let’s start with the LHS:
a
i
◦ (a
−1
i
(ab)) = e(ab) = ab
For the RHS:
a
i
(a
−1
i
(a)a
−1
i
(b)) = (a ◦ a
−1
i
(a))(a ◦ a
−1
i
(b)) = e(a)e(b) = ab
LHS = RHS
As a
−1
i
is a bijection from G → G and it preserves adjacency, a
−1
i
is an
Automorphism.
The three results above imply that A is a Group.
QED
Now, we shall see the power of Automorphisms by seeing how they tell us
the inherent invariance of a Cyclic Group under a permutation.
Claim: For a given Cyclic Group C
n+1
= {a
0
, .., a
n
} with a
0
→ a
1
→ . . . →
a
n
→ a
0
, f(a
i
) = a
n−i
is a non-trivial automorphism.
The proof for this can be found in an answer I gave here:
What is an automorphism?
(Note: The element a
0
is assumed to be the identity element)
A more powerful theorem regarding Finite Cyclic Groups is:
T h
m
: All Finite Cyclic Groups of the same order are Isomorphic to each other.
These 2 statements provide tremendous insight regarding the symmetry of
Cyclic Groups. Essentially, one can go from a cyclic group to another provided
they have the same order by a clever one-to-one assignment of the elements.
Then, one can essentially “flip” the Group by a 180 degrees, and we’d still have
the same group.
This is a beautiful result, and shows the powerful tools that Automorphisms
are in studying Symmetry.
It is also trivial to see that A <
sub−g roup
S
n
, where S
n
is the Group of Permu-
tations of n-elements.
2
It may seem that Automorphisms are pretty abstract and would hold different
properties for different Groups. True as that may be, there is still one simple
and central result that shows a generic property of Automorphisms. Let us state
it, prove it, and then see its symmetric significance.
Claim: For any Group G , f(x) = axa
−1
, where a ∈ G is an Automorphism
of G.
Proof :
We need to show 3 things :
f → bijection.
f(ab) = f (a)f(b), ∀ a, b ∈ G.
f(e) = e.
Let us first show that f is a bijection:
i) Injective : If f is injective f (x
i
) = f(x
j
) =⇒ x
i
= x
j
Now,
f(x
i
) = axa
i
a
−1
f(x
j
) = axa
j
a
−1
Therefore, axa
i
a
−1
= axa
j
a
−1
Manipulating the LHS and RHS:
a
−1
ax
i
a
−1
= a
−1
ax
j
a
−1
ex
i
a
−1
= ex
j
a
−1
ax
i
a
−1
a = ex
j
a
−1
a
x
i
e = x
j
e =⇒ x
i
= x
j
Therefore, f is injective.
ii) Surjective:
If f is surjective, ∀ b ∈ G , ∃ a ∈ G , , f (a) = b.
Case 1):
b = e =⇒ x = e (The mapping of the identity element is preserved).
Case 2):
b = a =⇒ x = a
2
(This is easy enough to see).
Case 3):
Now, for some b ∈ G and b = a, e ,∃ a
i
a
j
So, if we choose a = a
i
and x , , x = a
j
a = a
j
a
i
, then:
axa
−1
= a
i
(a
j
a
i
)a
−1
i
= a
i
a
j
e = a
i
a
j
= b
Therefore, f is surjective.
Now, we shall show that the adjacency operation is preserved.
iii) Adjacency:
We need to show that : f (x
i
x
j
) = f(x
i
)f(x
j
)
Let us first evaluate the LHS:
f(x
i
x
j
) = a(x
i
x
j
)a
−1
Now, the RHS:
f(x
i
)f(x
j
) = a(x
i
)a
−1
a(x
j
)a
−1
= ax
i
ex
j
a
−1
= a(x
i
x
j
)a
−1
LHS = RHS
Therefore, our claim is proved.
QED
If we think about it for a moment, this mapping is very similar to the mapping
3
of Quadratic forms. In Linear Algebra, we often ”modify” the Dot-Product
of a vector in a Vector Space by mapping it via its Quadratic Form (which is
basically a solution to this equation):
x
T
Ax = 1, ∀x ∈ R
n
and some A ∈ R
n
× R
n
This amounts to ”stretching” the vector some amount (via a solution to the
Eigenvalue problem for the above equation) and tells us the dot-product in one
of the eigen-bases.
Similarly, this Automorphism tells us that this mapping preserves the symme-
try of a Group. It can be thought of as a mapping that basically creates the
elements defined by their operation with a and a
−1
.
We now move on to our final part in this post, Graph Automorphisms.
Def
n
: A Graph Automorphism is an Isomorphism from the Vertex Set of
a Graph to itself.
Formally, A Graph Automorphism is:
f : V (G) → V (G) , , f (a
i
)f(a
j
) = (a
i
a
j
), such that,
(a
i
a
j
) ∈ E(G) iff (a
i
a
j
) ∈ E(G)
Essentially, this function allows us to “re-draw” our graphs in a way whereby
re-labeling the vertices makes Graph look the same (structurally).
This problem is computationally TRICKY. It is not as straight-forward as it
seems.
In fact :
Claim: Graph Automorphism ∈ NP.
Proof :
This result is easily shown as :
i) Graph Isomorphism <
P
Graph Automorphism
ii) Graph Automorphism is P-verifiable
Construct the Edge-List, and make sure that mappings are preserved.
This is easily checked in O(n
2
time using a Hash-Map to memoize
validation of adjacency requirements.
The Graph Isomorphism Problem has a best known Algorithm that runs in
Quasi-Polynomial Time.
More specifically :
- Given : G
1
, G
2
.
- Problem P
1
: Is G
1
∼
=
G
2
?
T
n
(Algorithm(P
1
)) = 2
(O(log
2
n))
c
This Algorithm was proposed by Laszlo Babai in his paper Graph Isomorphism
in Quasipolynomial Time.
It is easy to see that we are interested in ”valid” permutations of the ver-
tices that preserve the operation of ”adjacency” (which is governed by edges).
Now, as edges compose together together to form a Walk, it is easy to see how
4
the Symmetric Group S
n
corresponding to a labeling of the vertices would be
helpful in understanding valid permutations for a given Graph G.
To motivate why this problem is so tricky, and requires results from Combinato-
rial Group Theory such as efficient Coset construction and the Split-or-Johnson
routine (the meat of the algorithm proposed by Babai), I will introduce the no-
tion of a degree sequence. To further see the connections between the Alternat-
ing Group (a sub-group of S
n
), its Cosets, Johnson Graphs and their connection
to Graph-Isomorphism, I suggest listening to Babai’s 3 talks at UChicago. Now,
let me introduce a basic (but powerful) concept from Graph Theory and show
how it fails to ”capture” all the information about the symmetry of a graph
that we desire.
The Degree-Sequence of a Graph:
Def
n
: Given G = (V, E), a Graph has a sequence s
G
= deg(v
1
), . . . , deg(v
n
).
One can reverse-sort this sequence to convert it into a Degree-Sequence. A sim-
ple Theorem that helps validate whether a degree-sequence represents a Graph:
T h
m
: A non-increasing sequence s : d
1
, d
2
, . . . , d
n
where d
i
≥ 0, ∀i is graphical
iff: s
1
: d
2
− 1, . . . , d
d
1
+1
− 1, d
d
1
+2
, . . . , d
n
is graphical.
Note: It may be tempting to think that, if s
G
1
= s
G
2
, then G
1
∼
=
G
2
.
However, this is NOT the case, and can be shown with a little thought. I shall
leave the Proof as an exercise to the reader.
Hint: The degree sequence may tell us the cardinality of the degree of a vertex,
however, it doesn’t give us enough information about how the edges are being
absorbed. This should allow us to create 2 Graphs that have the same degree
sequences, but are not isomorphic. Seeing that this trivial representation (and
consequently linear-algebraic) approach doesn’t help us capture the symmetry
of the problem, we move on to tools from Combinatorial Group Theory.
5