4
$\begingroup$

Since each finite group $G$ can be considered as a subgroup of the symmetric group, by Cayley's theorem, we might see the elements of $G$ as permutations $\pi$.

Consider for each $\pi \in G$ the set:

$$X(\pi) := \{ (\pi(i),\pi(j)) | 1 \le i < j \le |G| \}$$

Then the Jaccard similarity-kernel, which is positive definite, is:

$$J(\pi,\pi'):= \frac{ |X(\pi) \cap X(\pi')|}{|X(\pi) \cup X(\pi')|}$$

We can consider the matrix

$$M = (J(g,h)_{g,h \in G})$$

ordered somehow by an ordering of $G$.

Since $J$ is a kernel and a similarity, we can write the distance between two elements in $G$ as:

$$d(g,h) = \sqrt{J(g,g) + J(h,h)-2J(g,h)} = \sqrt{2-2J(g,h)}$$

A similarity $s:X\times X \rightarrow \mathbb{R}$ is defined in Encyclopedia of Distances as:

1) $s(x,y) \ge 0 \forall x,y \in X$

2) $s(x,y) = s(y,x) \forall x,y \in X$

3) $s(x,y) \le s(x,x) \forall x,x \in X$

4) $s(x,y) = s(x,x) \iff x=y$

A positive definite kernel $k$ is a positive definite function on some set $X$.

A "kernel-similarity" is a function $f$ which is a kernel and a similiarity.

One can prove that the above Jaccard function is a kernel-similarity.

My question is, if one can gain any insight for finite groups by studying properties of the Euclidean geometry of the embedded vectors $\phi(g)$.

For instance the matrix $M$ is a Gram-Matrix of linear independent vectors, hence one can look at the volume of these vectors:

$$\operatorname{vol}(G): = \sqrt{\det(M_G)}$$

Here is some SAGEMATH code which implements this:

from sage.matrix.operation_table import OperationTable
import itertools

def Jaccard(A,B):
    pairs = list(itertools.combinations(range(0, len(A)), 2))
    XA = set([ (A[x],A[y]) for x,y in pairs])
    XB = set([ (B[x],B[y]) for x,y in pairs])
    return QQ(len(XA.intersection(XB)))/QQ(len(XA.union(XB)))

def GramMatrix(finiteGroup):
    G = finiteGroup
    O = OperationTable(G,operator.mul,names="elements")
    M = matrix([[ Jaccard(Permutation([xx+1 for xx in x]),Permutation([yy+1 for yy in y])) for x in O.table()] for y in O.table()],ring=QQ) #RDF)
    return M

def regRepr(finiteGroup):
    G = finiteGroup
    O = OperationTable(G,operator.mul,names="elements")
    #print(O.table())
    ll = [ Permutation([xx +1 for xx in x]).to_matrix() for x in O.table()] 
    return ll

rD4 = (regRepr(DihedralGroup(4)))
#print(rD4)
GD4 = GramMatrix(DihedralGroup(4))
vecs = GD4.columns()
print(vecs)
for M in rD4:
    print("--")
    for v in vecs:
      print(v,M*v)
      print(M*v in vecs)

groups = [SymmetricGroup(2),CyclicPermutationGroup(3),CyclicPermutationGroup(4),KleinFourGroup(),CyclicPermutationGroup(5),CyclicPermutationGroup(6),SymmetricGroup(3),QuaternionGroup(),DihedralGroup(5),AlternatingGroup(4),SymmetricGroup(4),DihedralGroup(8)]
for G in groups: #G = DihedralGroup(4)
    print("Group G:=")
    print(G)
    M = GramMatrix(G)
    print("Gram-Matrix:")
    print(M)
    print("cholesky = ")
    print(M.cholesky())
    print("characteristic-polynomial of Gram-Matrix=")
    print(factor(M.charpoly()))
    print("Volume of G:")
    print(sqrt(M.det()))

Thanks for your help!

Edit Here is a more concrete question:

Is for all $g,h,x \in G$:

$$J(g,h) = J(gx,hx) = J(xg,xh)$$ ?

$\endgroup$
4
  • 1
    $\begingroup$ A related question by the poster, at least in the sense that it uses the same construction: mathoverflow.net/questions/362363/… . (Here as there, I ask the same question about to what extent these questions rely on the choice of permutation representation of $G$.) $\endgroup$
    – LSpice
    Commented Jun 7, 2020 at 16:59
  • 1
    $\begingroup$ @LSpice it is used a similar construction. I changed the definition of $X$, since in the previous question the matrix $M$ was the identity matrix for the Cayley embedding $\endgroup$
    – user6671
    Commented Jun 7, 2020 at 17:24
  • 1
    $\begingroup$ What is $\phi$? $\endgroup$
    – user44143
    Commented Jun 8, 2020 at 7:52
  • $\begingroup$ @MattF. The $\phi$ is the Cholesky vector $\phi(g)$ corresponding to a group element $g$ $\endgroup$ Commented Dec 7, 2020 at 6:54

0

You must log in to answer this question.