---
abstract: '[We provide algorithms to compute a complete irredundant set of extremely strong Shoda pairs of a finite group $G$ and the set of primitive central idempotents of the rational group algebra $\mathbb{Q}[G]$ realized by them. These algorithms are also extended to write new algorithms for computing a complete irredundant set of strong Shoda pairs of $G$ and the set of primitive central idempotents of $\mathbb{Q}[G]$ realized by them. Another algorithm to check whether a finite group $G$ is normally monomial or not is also described.]{}'
author:
- |
    Gurmeet K. Bakshi and Sugandha Maheshwary[[^1] [^2]]{}\
    [*Centre for Advanced Study in Mathematics,*]{}\
    [*Panjab University, Chandigarh 160014, India*]{}\
    [*email: gkbakshi@pu.ac.in and msugandha.87@gmail.com* ]{}
bibliography:
- 'ReferencesBM3.bib'
title: '**Extremely strong Shoda pairs with `GAP`**'
---

rational group algebra, primitive central idempotents, strong Shoda pairs, extremely strong Shoda pairs, normally monomial groups.\
[**MSC2000:** ]{}Primary: 20C05, 16S34; Secondary: 68W30.

Introduction
============

Let $G$ be a finite group and let $\mathbb{Q}[G]$ be the rational group algebra of $G$. A *strong Shoda pair* of $G$, introduced by Olivieri, del R[í]{}o and Sim[ó]{}n [@Oli], is a pair $(H,K)$ of subgroups of $G$ with the subgroups $H$ and $K$ satisfying some technical conditions. In [@BM], a strong Shoda pair $(H,K)$ with $H$ normal in $G$ is called as an *extremely strong Shoda pair* of $G$. An important property ([@Oli], Proposition 3.3) of the strong Shoda pairs of $G$ is that each such pair $(H,K)$ determines a *primitive central idempotent* of $\mathbb{Q}[G]$, called the *primitive central idempotent of* $\mathbb{Q}[G]$ *realized by* $(H,K)$, which is denoted by $e(G,H,K)$. Let $E$ be the set of all primitive central idempotents of $\mathbb{Q}[G]$ and $E_{SSP}$ (resp. $E_{ESSP}$) be the set of primitive central idempotents of $\mathbb{Q}[G]$ realized by the strong Shoda pairs (resp. extremely strong Shoda pairs) of $G$. The groups $G$ for which $E=E_{SSP}$ are called *strongly monomial* groups and are known to constitute a large class of monomial groups, including abelian-by-supersolvable groups [@Oli]. Also, in [@BM], it has been proved that $E=E_{SSP}=E_{ESSP}$ if, and only if, $G$ is a *normally monomial* group i.e., every complex irreducible character of $G$ is induced from a linear character of a normal subgroup of $G$. The `GAP` [@GAP] package `Wedderga` [@Wedd] features the function `PrimitiveCentralIdempotentsByStrongSP(QG);` that computes the set $E_{SSP}$ for the rational group algebra $\mathbb{Q}[G]$ and the function `StrongShodaPairs(G);` that determines a subset $X$ of strong Shoda pairs of $G$ such that $(H,K)\mapsto e(G,H,K)$ defines a bijection from $X$ to $E_{SSP}$. Such a set $X$ is called a *complete irredundant set of strong Shoda pairs* of $G$. These functions are based on the search algorithms provided by Olivieri and del R[í]{}o [@OliA]. Another relevant feature of `Wedderga` is the function `IsStronglyMonomial(G);` which checks whether the group $G$ is strongly monomial or not. Using this function, it has been revealed in [@Olte] that all the monomial groups of order less than $1000$ are strongly monomial.\
In this paper, we provide an algorithm to compute a complete irredundant set of extremely strong Shoda pairs of $G$. This algorithm is based on the work in [@BM]. We further extend this algorithm by combining it with the search algorithm provided by Olivieri and del R[í]{}o [@OliA] to obtain a new algorithm that computes a complete irredundant set of strong Shoda pairs of $G$. As a consequence, we obtain algorithms to write the sets $E_{ESSP}$ and $E_{SSP}$ of primitive central idempotents of $\mathbb{Q}[G]$ realized by extremely strong Shoda pairs of $G$ and those re alized by strong Shoda pairs of $G$ respectively. Another algorithm to check whether a finite group $G$ is normally monomial or not also follows as a consequence. These algorithms are given in Section 3 and enable us to write the following functions in `GAP` language:

-   `ExtStrongShodaPairs(G);` which computes a complete irredundant set of extremely strong Shoda pairs of $G$ i.e., a subset $X$ of extremely strong Shoda pairs of $G$, such that such that $(H,K)\mapsto e(G,H,K)$ gives a bijection from $X$ to $E_{ESSP}$.

-   `StShodaPairs(G);` which computes a complete irredundant set of strong Shoda pairs of $G$.

-   `PrimitiveCentralIdempotentsByExtSSP(QG);` which computes the set of primitive central idempotents of $\mathbb{Q}[G]$ realized by extremely strong Shoda pairs of $G$.

-   `PrimitiveCentralIdempotentsByStSP(QG);` which computes the set of primitive central idempotents of $\mathbb{Q}[G]$ realized by strong Shoda pairs of $G$.

-   `IsNormallyMonomial(G);` which checks whether the group $G$ is normally monomial or not.

Using the function `IsNormallyMonomial(G);` we have searched for normally monomial groups among the groups in `GAP` library of small groups. The search indicates that the class of normally monomial groups is a substantial class of monomial groups. It may also be mentioned that if $G$ is a normally monomial group, then the output obtained by the functions `StShodaPairs(G);` and `PrimitiveCentralIdempotentsByStSP(QG);` is same as that obtained by `ExtStrongShodaPairs(G);` and `PrimitiveCentralIdempotentsByExtSSP(QG);` respectively. Furthermore, for a finite group $G$, the functions `StShodaPairs(G);` and `PrimitiveCentralIdempotentsByStSP(QG);` are alternative to the functions `StrongShodaPairs(G);` and `PrimitiveCentralIdempotentsByStrongSP(QG);` respectively, which are currently available in `Wedderga`.

In Section 4, we compare the runtimes of the function `StShodaPairs(G);` with `StrongShodaPairs(G);` for a large and evenly spread sample of groups of order up to $2000$. For this sample, the functions `PrimitiveCentralIdempotentsByStSP(QG);` and `PrimitiveCentralIdempotentsByStrongSP(QG)`; are also compared for runtimes. It is observed that these new functions show significant improvement in the time taken to compute the same outputs. Further, in order to observe the performance separately for solvable and non solvable groups, we also compared the runtimes of `StShodaPairs(G);` with `StrongShodaPairs(G);` for another two samples. The sample of solvable groups consists of all the groups of odd order up to 2000, and the other sample consists of all non solvable groups of order up to 2000. It is observed that the performance of `StShodaPairs(G);` is exceptionally better in comparison with that of `StrongShodaPairs(G);` for solvable groups. However, in the case of non solvable groups, the performance of the two functions is almost identical. Finally, we describe the reasons for the difference in the performance of these functions.

Notation and Preliminaries
==========================

Throughout this paper, $G$ denotes a finite group. By $H \leq G$ (resp. $H\unlhd G$), we mean that $H$ is a subgroup (resp. normal subgroup) of $G$. For $H \leq G$, $[G:H]$ denotes the index of $H$ in $G$, $N_{G}(H)$ denotes the normalizer of $H$ in $G$, $\operatorname{core}_{G}(H)=\bigcap_{x\in G}xHx^{-1}$ and $\hat{H}=\frac{1}{|H|}\sum_{h \in H}h$, where $|H|$ is the order of $H$. For $K\unlhd H \leq G$, write $$\varepsilon (H,K) := \begin{cases} \hat{H}, & {\rm if}~ H = K; \\ \prod (\hat{K}-\hat{L}), &  {\rm otherwise,} \end{cases}$$ where $L$ runs over the minimal normal subgroups of $H$ containing $K$ properly. Set

$e(G,H,K)$ := the sum of all the distinct $G$-conjugates of $\varepsilon(H,K)$.

Let $\varphi$ denote the Euler phi function. Denote by $\operatorname{Irr}(G)$, the set of all complex irreducible characters of $G$. For $\chi \in \operatorname{Irr}(G)$, $\mathbb{Q}(\chi)$ denotes the field obtained by adjoining to $\mathbb{Q}$, all the character values $\chi(g),~g \in G$, and $\operatorname{Gal}(\mathbb{Q}(\chi)/\mathbb{Q})$ is the Galois group of the extension $\mathbb{Q}(\chi)$ over $\mathbb{Q}$.

It is well known that $\chi \mapsto e_{\mathbb{Q}}(\chi):=\frac{\chi(1)}{|G|}\sum_{\sigma \in \operatorname{Gal}(\mathbb{Q}(\chi)/\mathbb{Q}) }\sum_{g \in G}\sigma(\chi(g^{-1}))g$ defines a surjective map from $\operatorname{Irr}(G)$ to the set of primitive central idempotents of the rational group algebra $\mathbb{Q}[G]$. If $\chi$ is the trivial character of $G$, then it is easy to see that $e_{\mathbb{Q}}(\chi)=\hat{G}$.\
Olivieri et al [@Oli] proved the following:

\[t1\][([[@Oli], Lemma 1.2, Theorem 2.1]{})]{}

1.  If $\chi$ is a non trivial linear character of $G$ with kernel $N$ then $$\label{e1}
        e_{\mathbb{Q}}(\chi)=\varepsilon(G,N).$$

2.  If $\chi$ is monomial, i.e. $\chi$ is induced from a linear character $\psi$ of a subgroup $H$ of $G$, then there exists $\alpha \in  \mathbb{Q}$ such that $$        e_{\mathbb{Q}}(\chi)= \alpha e(G, H, K),$$ where $K$ is the kernel of the character $\psi$. Furthermore $\alpha=1$, if the distinct $G$-conjugates of $\varepsilon(H,K)$ are mutually orthogonal.

Shoda (see [@curt], Theorem 45.2) gave a criteria to decide if the character of $G$ induced by a linear character $\psi$ of a subgroup $H$ of $G$ is irreducible, in terms of $H$ and the kernel $K$ of $\psi$. A pair $(H,K)$ of $G$ satisfying this criteria is called a *Shoda pair* ([@Oli], Definition 1.4) of $G$. A *strong Shoda pair* ([@Oli], Definition 3.1) of $G$ is a pair $(H,K)$ of subgroups satisfying the following conditions:

> (i)
>
> :   $K \unlhd H \unlhd N_{G}(K)$;
>
> (ii)
>
> :   $H/K$ is cyclic and a maximal abelian subgroup of $N_{G}(K)/K$;
>
> (iii)
>
> :   the distinct $G$-conjugates of $\varepsilon(H,K)$ are mutually orthogonal.
>
As the name suggests, each strong Shoda pair of $G$ is also a Shoda pair of $G$ ([@Oli], Proposition 3.3). A strong Shoda pair $(H,K)$ of $G$ is called an *extremely strong Shoda pair* of $G$, if $H\unlhd G$. Observe that $(G,G)$ is always an extremely strong Shoda pair of $G$.

From Theorem \[t1\], it follows that if $(H, K)$ is a strong Shoda pair of $G$, then $e(G,H,K)$ is a primitive central idempotent of $\mathbb{Q}[G]$, called [*the primitive central idempotent of $\mathbb{Q}[G]$ *realized by $(H,K)$**]{}. For a strong Shoda pair $(H,K)$ of $G$, we denote by $\operatorname{dim}(H,K)$, the $\mathbb{Q}$-dimension of the simple component $\mathbb{Q}[G]e(G,H,K)$ of $\mathbb{Q}[G]$. In view of ([@Oli], Proposition 3.4), $\operatorname{dim}(H,K)$ equals $\varphi([H:K])[N_{G}(K):H][G:N_{G}(K)]^{2}.$ Two strong (resp. extremely strong) Shoda pairs $(H_{1}, K_{1})$ and $(H_{2}, K_{2})$ of $G$ are said to be [*equivalent*]{} if $e(G, H_{1}, K_{1})=e(G, H_{2}, K_{2})$. A complete set of representatives of distinct equivalence classes of strong (resp. extremely strong) Shoda pairs of $G$ is called a [*complete irredundant set of strong [(]{}resp. extremely strong[)]{} Shoda pairs*]{} of $G$.

We now recall the method given in [@BM] to compute a complete irredundant set of extremely strong Shoda pairs of a finite group $G$.

Let $\mathcal{N}$ be the set of all the distinct normal subgroups of $G$. For $N \in \mathcal{N}$, let $A_{N}$ be a normal subgroup of $G$ containing $N$ such that $A_{N}/N$ is an abelian normal subgroup of maximal order in $G/N$. Note that the choice of $A_{N}$ is not unique. However, we need to fix one such $A_{N}$. For a fixed $A_{N}$, set\
$\begin{array}{lll}
  \mathcal{D}_{N}: & {\rm the ~set ~of ~all ~subgroups~} D ~{\rm  of} ~A_{N}~ {\rm containing ~} N~{\rm  such ~that~}
   \operatorname{core}_{G}(D)=N, \\&  A_{N}/D ~{\rm    is ~ cyclic ~  and ~  is ~a ~ maximal~ abelian ~ subgroup~  of~}   N_{G}(D)/D.  \vspace{.2cm}\\ \mathcal{T}_{N}: &  {\rm a ~set~ of ~representatives~ of~ } \mathcal{D}_{N} {\rm ~  under ~the~ equivalence~ relation~ defined~ by} \\ & {\rm
    conjugacy~ of~ subgroups~in~} G. \vspace{.2cm} \\  \mathcal{S}_{N}: & \{( A_{N},D)~|~ D \in \mathcal{T}_{N}\}.\end{array}$

\[t2\][([@BM], Theorem 1)]{} Let $G$ be a finite group. Then,\
[(i)]{} $\cup_{N \in \mathcal{N} }\mathcal{S}_{N} $ is a complete irredundant set of extremely strong Shoda pairs of $G$.\
[(ii)]{} $\{ e(G, A_{N}, D)\, |\, ( A_{N},D)  \in \mathcal{S}_{N},~ N \in \mathcal{N} \}$ is a complete set of primitive central idempotents of $\mathbb{Q}[G]$ if, and only if, $G$ is normally monomial.

It may be noted that in Theorem \[t2\], the choice of $A_{N}$ is irrelevant. For $N \in \mathcal{N}$, let $A_{N}'$ be another normal subgroup of $G$ containing $N$ such that $A_{N}'/N$ is an abelian normal subgroup of maximal order in $G/N$ and let $\mathcal{D}_{N}'$, $\mathcal{T}_{N}'$ and $\mathcal{S}_{N}'$ be defined corresponding to $A_{N}'$. Then any pair in $\mathcal{S}_{N}'$ is equivalent to a pair in $\mathcal{S}_{N}$ and vice versa. This is because, if $(A_{N}',D')\in \mathcal{S}_{N}'$ and $\psi$ is a linear character of $A_{N}'$ with kernel $D'$, then $\psi^{G}$ is irreducible and hence by ([@BM], Lemma 1), there exists $(A_{N},D)\in \mathcal{S}_{N}$ such that $e_{\mathbb{Q}}(\psi^{G})=e(G,A_{N},D).$ However, in view of Theorem \[t1\], $e_{\mathbb{Q}}(\psi^{G})=e(G,A_{N}',D').$ This gives that $(A_{N},D)$ is equivalent to $(A_{N}',D')$. The reverse conclusion holds similarly.

[([@BM], Corollary 1)]{}\[c1\] If $G$ is a normally monomial group, then $\bigcup_{N \in \mathcal{N}}\mathcal{S}_{N}$ is a complete irredundant set of strong Shoda pairs of $G$.

\[c2\][([@BM], Corollary 2)]{} A finite group $G$ is normally monomial if, and only if, $$\sum_{N\in \mathcal{N}}\sum_{(A_{N},D) \in \mathcal{S}_{N}}dim(A_{N},D) = |G|.$$

Algorithms
==========

We shall use the notation developed in the previous section.

Extremely Strong Shoda Pairs
----------------------------

We provide Algorithm 1, which computes the set $ESSP$, which is a complete irredundant set of extremely strong Shoda pairs of a given finite group $G$. This algorithm is based on Theorem \[t2\]. It mainly requires the set $\mathcal{N}$ of normal subgroups of $G$ and the computation of $\mathcal{S}_{N}$ for each $N\in \mathcal{N}$. The set $\mathcal{S}_{N}$ is computed as explained in Section 2 and by using Lemmas \[l1\]-\[l2\] to avoid unnecessary computations.

\[l1\] For a normal subgroup $N$ of $G$, the following hold:

(i)

:   If $G/N$ is abelian, then $$\mathcal{S}_{N} = \begin{cases} \{(G, N)\}, ~& {\rm if}~G/N~{\rm is~  cyclic;}\\ \emptyset, & {\rm otherwise.}
        \end{cases}$$

(ii)

:   If $G/N$ is non abelian and $A_{N}/N$ is cyclic, then $$\mathcal{S}_{N} = \begin{cases} \{(A_{N}, N)\}, & ~{\rm if}~ A_{N}/N ~{\rm is~ a~ maximal~ abelian~ subgroup ~of} ~G/N;\\ \emptyset, & {\rm otherwise.}
        \end{cases}$$

[**Proof.**]{} Follows immediately from the definition of $\mathcal{S}_{N}$. $\Box$

\[l3\] If $\mathcal{M} \subseteq \mathcal{N}$ is such that $$\sum_{N\in \mathcal{M}}\sum_{(A_{N},D) \in \mathcal{S}_{N}}dim(A_{N},D)=|G|,$$ then $\mathcal{S}_{N}= \emptyset~ $ for all $~N \in \mathcal{N}\setminus \mathcal{M}$.

[**Proof.**]{} The primitive central idempotents $e(G,A_{N},D)$ for $(A_{N},D)\in \mathcal{S}_{N} $, $N \in \mathcal{N}$, are distinct, as $\bigcup_{N \in \mathcal{N}}\mathcal{S}_{N}$ is a complete irredundant set of extremely strong Shoda pairs of $G$. Therefore, $\bigoplus_{N \in \mathcal{N}}\bigoplus_{(A_{N},D)\in \mathcal{S}_{N}}\mathbb{Q}[G]e(G,A_{N},D)$ is a direct summand of $\mathbb{Q}[G]$, and hence its $\mathbb{Q}$-dimension is at most $|G|$. Consequently, $$\begin{aligned}
  |G| &\geq & \sum_{N\in \mathcal{N}}\sum_{(A_{N},D)\in \mathcal{S}_{N}} dim(A_{N},D) \nonumber \\
   &\geq & \sum_{N\in \mathcal{M}}\sum_{(A_{N},D)\in \mathcal{S}_{N}} dim(A_{N},D) ~~~~(\because\mathcal{M} \subseteq \mathcal{N}) \nonumber\\
   &=& |G|.\end{aligned}$$ This yields that $\mathcal{S}_{N} =\emptyset$ for all $N\not \in \mathcal{M}$ and completes the proof.$~\Box$

\[l2\] If $(H,K)$ is a strong Shoda pair of $G$ with $N=\operatorname{core}_{G}(K)$, then the centre of $G/N$ must be cyclic.\
In particular, if $N \in \mathcal{N}$ is such that the centre of $G/N$ is not cyclic, then $\mathcal{S}_{N}= \emptyset$.

[**Proof.**]{} Let $aK$ be a generator of $H/K$ and let $\zeta$ be a primitive $m^{th}$ root of unity, where $m=[H:K]$. Consider the linear representation $\rho: H \rightarrow \mathbb{C}$ given by $x\mapsto \zeta^{i}$, if $xK=a^{i}K$, for $x \in H$. Since $(H,K)$ is a strong Shoda pair, $\rho^{G}$ is an irreducible representation of $G$. Now, as $\operatorname{ker}(\rho^{G})=\bigcap_{x\in G}x(\operatorname{ker}\rho)x^{-1}=\bigcap_{x\in G}xKx^{-1}=\operatorname{core}_{G}(K)=N$, the result follows from ([@IM], Lemma 2.27).$~\Box$\

\[A1\]

$\mathcal{N}:=$Normal subgroups of $G$ (in decreasing order) $ESSP:=[[G,G]]$ $SumDim:=1$

We now describe Algorithm 1. The first step of the algorithm is to compute the list $\mathcal{N}$ of all the normal subgroups of $G$ in decreasing order. If $N=G$, we have $\mathcal{S}_{N}= \{(G,G)\}$. Therefore, we initially set the list $ESSP$, which is the list of extremely strong Shoda pairs of $G$ found at any stage of computation, to be `[[G,G]]`. As $\operatorname{dim}(G,G)=1$, we set $SumDim$, which denotes the sum of $\mathbb{Q}$-dimensions of the simple components of $\mathbb{Q}[G]$ corresponding to the elements in $ESSP$, to be 1. For $N\in \mathcal{N}$, $N \neq G$, if $N$ contains the commutator subgroup $G'$ of $G$, then the corresponding set $\mathcal{S}_{N}$ is computed using Lemma \[l1\](i). Otherwise, $\mathcal{S}_{N}$ is computed using Theorem \[t2\] along with Lemmas \[l1\] and \[l2\]. In either of the two cases, if $\mathcal{S}_{N}\neq \emptyset$, then the elements of $\mathcal{S}_{N}$ are added to the list $ESSP$. Also, the sum of $\mathbb{Q}$-dimensions of simple components of $\mathbb{Q}[G]$ corresponding to the extremely strong Shoda pairs of $G$ in $\mathcal{S}_{N}$ is added to $SumDim$. In view of Lemma \[l3\], the process stops when either $SumDim=|G|$ or when all the normal subgroups of $G$ are exhausted. The normal subgroups $N$ of $G$ are selected in decreasing order i.e., if the normal subgroup $N_{1}$ is chosen before the normal subgroup $N_{2}$, then $|N_{1}|\geq|N_{2}|$. This has been done keeping in view the ease of computation of $\mathcal{S}_{N}$, if $G/N$ has small order. This algorithm enables us to write the function `ExtStrongShodaPairs(G);` in `GAP` language.

Strong Shoda Pairs
------------------

We next describe Algorithm \[A2\] to compute the set $StSP$, which is a complete irredundant set of strong Shoda pairs of a given finite group $G$.\

\[A2\]

$StSP$:= A complete irredundant set of extremely strong Shoda pairs of $G$;\
$SumDim$:=the sum of $\mathbb{Q}$-dimensions of simple components of $\mathbb{Q}[G]$ corresponding to the primitive central idempotents realized by the extremely strong Shoda pairs of $G$;

Initially, $StSP$ is the list $ESSP$ of extremely strong Shoda pairs of $G$ obtained using Algorithm \[A1\]. Also, $SumDim$ is set to be the the sum of $\mathbb{Q}$-dimensions of simple components of $\mathbb{Q}[G]$ corresponding to the primitive central idempotents realized by extremely strong Shoda pairs of $G$. In case $SumDim=|G|$, by Corollaries \[c1\] and \[c2\], $StSP$ is a complete irredundant set of strong Shoda pairs of $G$ and the algorithm terminates. Otherwise, to find the remaining strong Shoda pairs of $G$, we make use of the algorithm provided by Olivieri and del R[í]{}o [@OliA] with desired modifications. For a strong Shoda pair $(H,K)$ of $G$, we use the fact that $G/\operatorname{core}_{G}(K)$ must be cyclic (Lemma \[l2\]). Moreover, if $(H,K)$ realizes a primitive central idempotent of $\mathbb{Q}[G]$ different from the one realized by an extremely strong Shoda pair of $G$, then none of $H$ or $K$ is normal in $G$. This algorithm allows us to write the function `StShodaPairs(G);` in `GAP` language.

Primitive Central Idempotents
-----------------------------

The algorithm to compute the primitive central idempotents of $\mathbb{Q}[G]$ realized by extremely strong Shoda pairs of $G$ is similar to Algorithm 1. The only difference is that at any stage of the computation, instead of collecting the elements of $\mathcal{S}_{N}$, one collects the primitive central idempotents realized by them. Using this algorithm, we write the function `PrimitiveCentralIdempotentsByExtSSP(QG);` in `GAP` language which computes the set of primitive central idempotents realized by extremely strong Shoda pairs of $G$. To compute the primitive central idempotent $e(G,H,K)$ of $\mathbb{Q}[G]$ realized by the strong Shoda pair $(H,K)$ of $G$, we use the function `Idempotent_eGsum(QG,H,K);` currently available in `Wedderga`.

Similarly, the algorithm to compute the primitive central idempotents of $\mathbb{Q}[G]$ realized by strong Shoda pairs of $G$ is obtained by a slight modification of Algorithm \[A2\] and the corresponding function `PrimitiveCentralIdempotentsByStSP(QG);` is also obtained.

Normally Monomial Groups
------------------------

The algorithm to check whether a finite group $G$ is normally monomial or not is obtained by replacing the result $ESSP$ of Algorithm \[A1\] with $SumDim$. In view of Corollary \[c2\], $G$ is normally monomial if, and only if, $SumDim$=$|G|$. This algorithm enables us to write the function `IsNormallyMonomial(G);` in `GAP` language.

Using the function `IsNormallyMonomial(G);` we have found by a computer search that $98.84\%$ of the monomial groups of order up to $500$ are normally monomial. Also, $97.88\%$ of all the finite groups of order up to $500$ are normally monomial. An exhaustive computer search also yields that among the groups of odd order up to $2000$, the only groups which are not normally monomial are:

> `SmallGroup(375,2); SmallGroup(1029,12); SmallGroup(1053,51); SmallGroup(1125,3); SmallGroup(1125,7); SmallGroup(1215,68); SmallGroup(1875,18); SmallGroup(1875,19);`

It may be pointed out that all the groups in the above list, except the second and the third, are non monomial.\

Runtime Comparison
==================

We now present an experimental runtime comparison between the following two sets of functions for different samples of groups:

1.  `StrongShodaPairs(G);` with `StShodaPairs(G);`

2.  `PrimitiveCentralIdempotentsByStrongSP(QG);` with\
    `PrimitiveCentralIdempotentsByStSP(QG);`

For a given sample of groups, let $t(n)$ be the average of the runtimes, taken in milliseconds, for the groups in $S$ of order $n$ for $n\geq 1$. If the sample contains no group of order $n$, then set $t(n)=0$. Define $T(n)= \sum_{i=1}^{n}t(i),~n\geq 1$.

We now describe the first sample $S$ which consists of $31272$ groups of order up to $2000$. For $1 \leq n \leq 2000$, $n\neq 1024$, if the number of non isomorphic groups of order $n$ is less than $200$, then $S$ contains all the groups of order $n$. Otherwise, we include in the sample $S$, at least $100$ groups of order $n$, which are evenly spread in the `GAP` library of small groups. The groups of order 1024 are excluded because of their non availability in `GAP` library. For this sample, the graph of $n$ versus $T(n)$ for the comparison of the functions `StrongShodaPairs(G);` and `StShodaPairs(G);` is presented in Fig.1. Also, Fig.2 presents the runtime comparison of the function `PrimitiveCentralIdempotentsByStrongSP(QG);` with the function `PrimitiveCentralIdempotentsByStSP(QG);`

\[f1\]![Strong Shoda pairs (Sample S)](Chart1 "fig:")

\[f2\] ![Primitive Central Idempotents (Sample S)](Chart2 "fig:")

We next compare the runtimes of `StrongShodaPairs(G);` and `StShodaPairs(G);` for a sample of solvable and that of non solvable groups. The sample $S_{1}$ of solvable groups consists of all the groups of odd order up to 2000 and the sample $S_{2}$ consists of all the non solvable groups of order up to 2000. The graph of $n$ versus $T(n)$ for these samples are presented in Figs.3 and 4 respectively.

\[f3\]![Strong Shoda pairs (Sample S1)](Chart3 "fig:")

\[f4\] ![Strong Shoda pairs (Sample S2)](Chart4 "fig:")

In Figs.1-4, `SSP` and `StSP` are the curves for the functions `StrongShodaPairs(G);` and `StShodaPairs(G);` respectively and `PCIsBySSP` and `PCIsByStSP` represent the curves for the functions `PrimitiveCentralIdempotentsByStrongSP(QG);` and `PrimitiveCentralIdempotentsByStSP(QG);` respectively. These experiments have been performed on the computer with Intel Core i7-4770 CPU @ 3.40GHz Dual Core, 4GB RAM.\
The overall improvement in the performance of `StShodaPairs(G);` in comparison to `StrongShodaPairs(G);` is mainly due to following differences in their respective algorithms:

[2]{}

`StShodaPairs(G);`

`StrongShodaPairs(G);`

[2]{}

1.

:   Begins by computing all the normal subgroups of $G$. The conjugacy classes of subgroups of $G$ are computed only if $G$ is not normally monomial.

<!-- -->

1.

:   Always begins by computing all conjugacy classes of subgroups of $G$. It may be pointed out that generating the full subgroup lattice of $G$ restricts the efficiency when $G$ has large order.

[2]{}

2.

:   Firstly, the extremely strong Shoda pairs of $G$ are computed. If $G$ is not normally monomial, then the remaining strong Shoda pairs of are found by the search algorithm of `StrongShodaPairs(G);`, with slight modifications.

<!-- -->

2.

:   There is no distinction between the computation of extremely strong Shoda pairs and that of strong Shoda pairs of $G$.

[2]{}

3.

:   Extremely strong Shoda pairs of $G$ are computed using Theorem\[t2\], which ensures that each time a new extremely strong Shoda pair is constructed, it is necessarily inequivalent to any of the extremely strong Shoda pair already obtained.

<!-- -->

3.

:   When a new strong Shoda pair of $G$ is discovered, it is not necessarily inequivalent to the ones already discovered. Each time a new strong Shoda pair is found, the algorithm computes the corresponding primitive central idempotent of $\mathbb{Q}[G]$ and checks its equivalence.

The above differences also result in the improved performance of the function `PrimitiveCentralIdempotentsByStSP(QG);` in comparison to that of the function `PrimitiveCentralIdempotentsByStrongSP(QG);` which is currently available in `Wedderga`.

**Acknowledgements**\
The authors are grateful to the anonymous referees for their valuable comments and suggestions which have helped to write the paper in the present form.

[^1]: Research supported by CSIR, India (File No: SPM-09/135(0107)/2011-EMR-I) is gratefully acknowledged

[^2]: Corresponding author
