(Created page with "For the composition table of a cyclic group shown below <table> <tr> <th>a</th> <th>b</th> <th>c</th> <th>d</th> </tr> <tr> <td>b</td> <td>a</t...")
 
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
For the composition table of a cyclic group shown below
 
For the composition table of a cyclic group shown below
<table>
+
  <tr>
+
 
    <th>a</th>
+
{| class="wikitable"
    <th>b</th>
+
! *
    <th>c</th>
+
! a
    <th>d</th>
+
! b
  </tr>
+
! c
  <tr>
+
! d
    <td>b</td>
+
|-
    <td>a</td>
+
!a
    <td>d</td>
+
|a
    <td>c</td>
+
| b
  </tr>
+
| c
  <tr>
+
| d
    <td>c</td>
+
|-
    <td>d</td>
+
!b
    <td>b</td>
+
| b
    <td>a</td>
+
| a
  </tr>
+
| d
  <tr>
+
| c
    <td>d</td>
+
|-
    <td>c</td>
+
!c
    <td>b</td>
+
| c
    <td>a</td>
+
| b
  </tr>
+
| d
</table>
+
| a
 +
|-
 +
!d
 +
| d
 +
| c
 +
| a
 +
| b
 +
|}
 
Which one of the following choices is correct?
 
Which one of the following choices is correct?
<br>
+
<b>(A) </b>a, b are generators
+
(A) $a, b$ are generators
&nbsp;
+
<b>(B) </b>b, c are generators
+
(B) $b, c$ are generators
<br>
+
<b>(C) </b>c, d are generators
+
(C) $c, d$ are generators
&nbsp;
+
<b>(D) </b>d, a are generators
+
(D) $d, a$ are generators
 
==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
 
==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
  
 
An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all  
 
An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all  
 
elements of group.
 
elements of group.
<br>
+
 
For example here : a*a = <b>a</b>, then (a*a)*a = a*a = <b>a</b>, and so on. Here we see that no matter how many times we apply a on itself,  
+
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.
+
we can't generate any other element except $a$, so $a$ is not a generator.
<br>
+
Now for b, b*b = <b>a</b>. Then (b*b)*b = a*b = <b>b</b>. Then (b*b*b)*b = b*b = <b>a</b>, and so on. Here again we see that we can only generate a and b
+
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.
+
on repeated application of $b$ on itself. So it is not a generator.
<br>
+
Now for c, c*c = <b>b</b>. Then (c*c)*c = b*c = <b>d</b>. Then (c*c*c)*c = d*c = <b>a</b>. Then (c*c*c*c)*c = a*c = <b>c</b>. So we see that we have generated
+
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.
+
all elements of group, so $c$ is a generator.
<br>
+
For d, d*d = <b>b</b>. Then (d*d)*d = b*d = <b>c</b>. Then (d*d*d)*d = c*d = <b>a</b>. Then (d*d*d*d)*d = a*d = <b>d</b>. So we have generated all elements
+
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.
+
of group from $d$, so $d$ is a generator.
<br>
+
So c and d are generators. So option <b>(C)</b> is correct.
+
Thus $c$ and $d$ are generators. So option <b>(C)</b> is correct.
  
  
Line 58: 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
b a d c
c d b a
d c b a

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. So 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. So we have generated all elements of group from d, so d is a generator.
So c and d are generators. So option (C) is correct.




blog comments powered by Disqus