Line 65: Line 65:
  
 
[[Category: GATE2009]]
 
[[Category: GATE2009]]
[[Category: Graph Theory questions]]
+
[[Category: Graph Theory questions from GATE]]

Latest revision as of 11:38, 15 July 2014

For the composition table of a cyclic group shown below


* a b c d
a a b c d
b b a d c
c c b d a
d d c a b

Which one of the following choices is correct?

(A) $a, b$ are generators

(B) $b, c$ are generators

(C) $c, d$ are generators

(D) $d, a$ are generators

Solution by Happy Mittal

An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all elements of group.

For example here : $a*a = a$, then $(a*a)*a = a*a = a$, and so on. Here we see that no matter how many times we apply $a$ on itself, we can't generate any other element except $a$, so $a$ is not a generator.

Now for $b$, $b*b = a$. Then $(b*b)*b = a*b = b$. Then $(b*b*b)*b = b*b = a$, and so on. Here again we see that we can only generate $a$ and $b$ on repeated application of $b$ on itself. So it is not a generator.

Now for $c$, $c*c = b$. Then $(c*c)*c = b*c = d$. Then $(c*c*c)*c = d*c = a$. Then $(c*c*c*c)*c = a*c = c$. We see that we have generated all elements of group, so $c$ is a generator.

For $d$, $d*d = b$. Then $(d*d)*d = b*d = c$. Then $(d*d*d)*d = c*d = a$. Then $(d*d*d*d)*d = a*d = d$. We have generated all elements of group from $d$, so $d$ is a generator.

Thus $c$ and $d$ are generators. So option (C) is correct.




blog comments powered by Disqus

For the composition table of a cyclic group shown below


* a b c d
a a b c d
b b a d c
c c b d a
d d c a b

Which one of the following choices is correct?

(A) $a, b$ are generators

(B) $b, c$ are generators

(C) $c, d$ are generators

(D) $d, a$ are generators

Solution by Happy Mittal[edit]

An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all elements of group.

For example here : $a*a = a$, then $(a*a)*a = a*a = a$, and so on. Here we see that no matter how many times we apply $a$ on itself, we can't generate any other element except $a$, so $a$ is not a generator.

Now for $b$, $b*b = a$. Then $(b*b)*b = a*b = b$. Then $(b*b*b)*b = b*b = a$, and so on. Here again we see that we can only generate $a$ and $b$ on repeated application of $b$ on itself. So it is not a generator.

Now for $c$, $c*c = b$. Then $(c*c)*c = b*c = d$. Then $(c*c*c)*c = d*c = a$. Then $(c*c*c*c)*c = a*c = c$. We see that we have generated all elements of group, so $c$ is a generator.

For $d$, $d*d = b$. Then $(d*d)*d = b*d = c$. Then $(d*d*d)*d = c*d = a$. Then $(d*d*d*d)*d = a*d = d$. We have generated all elements of group from $d$, so $d$ is a generator.

Thus $c$ and $d$ are generators. So option (C) is correct.




blog comments powered by Disqus