# Standardizing a coset table via matrix manipulation

Suppose we have a group $G$ and a subgroup $H$. A coset table encodes the permutation representation of $G$ on the right cosets of $H$. When we want to use these coset tables in calculations, it is often first necessary to "standardize" them. This standardization works as follows: cycle through the table by row, and then by column (label the rows of the table $\alpha$ and the columns $x$). If the value of the first element of the table (call it $\beta_{11}$) is not 2, swap the 2nd row and the $\beta_{11}$th row of the table, and then swap all the entries in the table which have the value $\beta_{11}$ with all the entries which have the value 2. After this, we want the elements to be introduced in numerical order. So move onto the element $\left(1,2\right)$, with our test value now $\gamma=2+1=3$. If the value of this element is less than 3, do nothing. If the value of this element is equal to 3, that's also fine, but for subsequent elements the value we're looking for is $\gamma=4$. If the value of this element is greater than 3, then swap the 3rd row of the table with the $\beta_{12}$th row, and then swap all the entries in the table which have the value $\beta_{12}$ with all the entries which have the value 3. Continue in this way through the table. Once the end of the first row is reached, move onto the next row, etc. (This algorithm is described in depth in Holt et al. - Handbook of Computational Group Theory).

To illustrate this standardization algorithm, consider the following matrix:

$\begin{pmatrix}2 & 4 & 2 & 4\\ 3 & 1 & 3 & 1\\ 4 & 2 & 4 & 2\\ 1 & 3 & 1 & 3 \end{pmatrix}$

This should be reordered to:

$\begin{pmatrix}2 & 3 & 2 & 3\\ 4 & 1 & 4 & 1\\ 1 & 4 & 1 & 4\\ 3 & 2 & 3 & 2 \end{pmatrix}$

This is because the first element is fine, but for the second element, 4>3, so swap the 4th and 3rd rows and then replace all the occurrences of 4 in the matrix with 3, and vice versa. After that, the algorithm does nothing.

The function I have written for this standardization algorithm on a 4x4 matrix is the following:

standardize[a_] := Module[{alpha, beta, gamma, x},
gamma = 2;
For[alpha = 1, alpha <= 4, alpha++,
For[x = 1, x <= 4, x++,
beta = a[[alpha, x]];
If[beta >= gamma,
If[beta > gamma,
a[[{gamma, beta}]] = a[[{beta, gamma}]];
a = (a /. {beta -> gamma, gamma -> beta});
];
gamma++;
];
];
];
a // MatrixForm
]


However, the following two lines bring up errors:

a[[{gamma, beta}]] = a[[{beta, gamma}]];
a = (a /. {beta -> gamma, gamma -> beta});


This is strange to me, because both of the lines work fine when you throw in a matrix normally. So would it be possible to tell me a) why errors come up here but not normally, and b) whether there is a possible fix?

-
You need to define a local copy of the matrix within Module[]: Module[{atemp = a, (* stuff *)}, (* stuff *)], and then atemp[[{gamma, beta}]] = atemp[[{beta, gamma}]]; and similarly for the other lines. – J. M. Aug 26 '12 at 15:32

If you make standardize have attribute HoldFirst, your code works as is:

ClearAll[standardize];
SetAttributes[standardize, HoldFirst];
standardize[a_] := Module[{alpha, beta, gamma, x}, gamma = 2;
For[alpha = 1, alpha <= 4, alpha++,
For[x = 1, x <= 4, x++, beta = a[[alpha, x]];
If[beta >= gamma,
If[beta > gamma, a[[{gamma, beta}]] = a[[{beta, gamma}]];
a = (a /. {beta -> gamma, gamma -> beta});];
gamma++;];];];
a // MatrixForm]


and

 standardize[a]


gives

-
Ah, great. I have not used HoldFirst before so was unaware of it. Thanks very much! – Jimeree Aug 26 '12 at 15:47
@Jimeree, my pleasure.. – kglr Aug 26 '12 at 15:54

FWIW, here's a slightly shortened re-implementation of standardize[]:

standardize[a_] := Module[{atemp = a, beta, gamma = 2},
Do[
beta = atemp[[alpha, x]];
If[beta >= gamma,
If[beta > gamma,
atemp[[{gamma, beta}]] = atemp[[{beta, gamma}]];
atemp = (atemp /. {beta -> gamma, gamma -> beta})];
gamma++], {alpha, 4}, {x, 4}];
atemp]


Test it out:

standardize[{{2, 4, 2, 4}, {3, 1, 3, 1}, {4, 2, 4, 2}, {1, 3, 1, 3}}]
{{2, 3, 2, 3}, {4, 1, 4, 1}, {1, 4, 1, 4}, {3, 2, 3, 2}}


Append a // MatrixForm if need be.

Notes:

• A single doubly-indexed Do[] loop easily takes the place of the nested For[] loops. The routine also exploits the fact that Do[] loops start at 1 by default.

• As already mentioned, since the a_ in the function definition is at once replaced by the input matrix, lines like a[[{gamma, beta}]] = a[[{beta, gamma}]] are turned into {{2, 4, 2, 4}, {3, 1, 3, 1}, {4, 2, 4, 2}, {1, 3, 1, 3}}[[{gamma, beta}]] = ..., which is where the errors you saw came from, since you cannot assign to an explicit matrix. What you can do is to cache the matrix given to the routine into a variable within the routine (in this case, atemp) and then perform the needed modifications on that.

-
Yeah, that is nicer. Thanks very much! – Jimeree Aug 26 '12 at 17:29