Cayley Graphs and Spectra of Semidirect Products

From CanisiusmathWiki

I am working on analyzing Cayley graphs and spectra of semidirect products. First, I will analyze dihedral groups, as they are the simplest semidirect products.

Table of contents

1 Abstract

2 Dihedral Groups

3 Semidirect Products of Cyclic Groups of Odd Prime Order

4 Proof Outline/Progress for Conjecture 2

5 Generalized Dihedral Groups

6 Generalized Semidirect Products of Prime Cyclic Groups

7 Semidirect Products of a Z/p and Z/p-1

8 Results in Representation Theory

9 Results Relating to Schreier Graphs

10 Useful Programs

11 Related Projects

12 Resources

[edit]

Abstract

The spectrum of a graph is the set of eigenvalues of its adjacency matrix. A group, together with a set of generators, gives a Cayley graph, and a semidirect product is an interesting way of producing new groups. Beginning with the simplest examples, dihedral groups, I compared the spectra of cyclic groups to those of their semidirect products. It was found that many of the interesting identities that result can be described through graph coverings, number theory, representation theory, and even field theory.

[edit]

Dihedral Groups

Directed Cayley Graph of D10 with generators x and y.

Undirected Cayley Graph of C5 with generator x

Let $C\left(G,S\right)$ be the Cayley Graph for group $G$ using set $S$ to produce the edges, and let $\chi\left(X\right)=\det\left(\lambda I-A\left(X\right)\right)$ , where $X$ is a directed graph and $A\left(X\right)$ means the adjacency matrix of $A$ . (In other words, $\chi\left(X\right)$ is the characteristic polynomial of $X$ .) Also, let $D_{2n}=\left<x,y: x^{n}=e, y^{2}=e, yxy^{-1}=x^{-1}\right>$ , that is, the dihedral group with $2n$ elements. In the paper, "Combinatorics of the Figure Equation on Directed Graphs (http://www.rose-hulman.edu/mathjournal/v7n2.php)," Taylor Coon states the following:

Theorem 1: $\chi\left(C\left(D_{2n}, \left\{x, y\right\}\right)\right)=\lambda^{n}\chi\left(C\left(\mathbb{Z}/n, \left\{\pm1\right\}\right)\right)$

For a proof of Theorem 1, see Theorem on Spectra of Dihedral Groups.

[edit]

Semidirect Products of Cyclic Groups of Odd Prime Order

Directed Cayley Graph of Z/3 semidirect product Z/7 with generators x and y.

Another view of directed Cayley Graph of Z/3 semidirect product Z/7 with generators x and y.

Directed Cayley Graph of Z/21 with generators x^3 and x^7, for comparison purposes.

Let $p_{1}$ and $p_{2}$ be odd primes with $p_{1}<p_{2}$ and $p_{1}\mid p_{2}-1$ . Let $x$ be a generator of $\mathbb{Z}/p_{2}$ , and let $y$ be a generator of $\mathbb{Z}/p_{1}$ . Let $G=H_{p_{1}p{2}}=\mathbb{Z}/p_{2}\rtimes\mathbb{Z}/p_{1}=\left<x,y\mid x^{p_{2}}=e, y^{p_{1}}=e, yxy^{-1}=x^k\right>$ .
Proposition 1: $\chi\left(C\left(G,\left\{x,y\right\}\right)\right)=\left(\lambda-2\right)r\left(\lambda\right)q\left(\lambda\right)$ , where $\left(\lambda-2\right)r\left(\lambda\right)=\left(1-\lambda\right)^{n}+1$ . Additionally, the roots of $\left(1-\lambda\right)^{p_{1}}+1$ are of the form $\omega_{p_{1}}^{j}+1$ for $j=1,\ldots,p_{1}$ , where $\omega_{p_{1}}$ is a primitive $p_{1}^{th}$ root of unity. (All but (the root) 2 are also roots of $r\left(\lambda\right)$ .)
Proof of Proposition 1: First of all, substitute $1+\omega_{p_{1}}^{j}$ into $\left(1-\lambda\right)^{p_{1}}+1$ . This yields $\left(1-\left(1+\omega_{p_{1}}^{j}\right)\right)^{p_{1}}+1=\left(-\omega_{p_{1}}^{j}\right)^{p_{1}}+1=(-1)^{p_{1}}\omega_{p_{1}}^{p_{1}}+1=-1+1=0$ . Thus, the roots of that polynomial are as proposed. By the above and Julia Lazenby's Theorem, $\left(1-\lambda\right)^{p_{1}}+1=\chi\left(C\left(\mathbb{Z}/p_{1},\left\{0,1\right\}\right)\right)$ .
The other part of the proposition can be proven via the theorem discussed in the note on Lemma 1.3, if $X$ and $Y$ are graphs and there exists a covering map $\varphi: X\rightarrow Y$ , then $\chi\left(Y\right)\mid\chi\left(X\right)$ . Since $G/\left(\mathbb{Z}/p_{2}\right)=\mathbb{Z}/p_{1}$ is a quotient group, there is a covering map $\varphi: C\left(G\right)\rightarrow C\left(\mathbb{Z}/p_{1},\left\{0,1\right\}\right)$ given by $\varphi\left(x\right)=e$ , $\varphi\left(y\right)=y$ . From the definition, it is clear that this is a covering. By the theorem, this means that $\chi\left(C\left(\mathbb{Z}/p_{1},\left\{0,1\right\}\right)\right)\mid\chi\left(C\left(G\right)\right)$ . We already discovered that $\left(1-\lambda\right)^{p_{1}}+1=\chi\left(C\left(\mathbb{Z}/p_{1},\left\{0,1\right\}\right)\right)$ , so the proposition is true. $\square$
Conjecture 1: $\chi\left(C\left(G,\left\{x,y\right\}\right)\right)=\left(\lambda-2\right)r\left(\lambda\right)q\left(\lambda\right)$ as in Proposition 1, and $q\left(\lambda\right)$ is irreducible over $\mathbb{Q}$ .
This conjecture is very false, caused by a (now fixed) bug in the program that converts a group to a Cayley graph.
Conjecture 2: $\chi\left(C\left(G,\left\{x,y\right\}\right)\right)=\left(\left(1-\lambda\right)^{p_{1}}+1\right)q\left(\lambda\right)^{p_{1}}$ , where $q\left(\lambda\right)$ is of degree $p_{2}-1$ (but possibly reducible over $\mathbb{Q}$ ). Additionally, if $p_{1}=3$ , the largest coefficient in $q$ (in absolute value) is the constant term, and in all cases the coefficients of the $p_{1}$ terms of highest degree in $q$ are all one. Also, the constant coefficient's value is $-2^{\frac{p_{2}-1}{p_{1}}}$ .
Note on Conjecture 2:
Originally, the conjecture stated: " The largest coefficient in $q$ (in absolute value) is the constant term." For $p_{1}=5$ and $p_{2}=31$ , $q=64+32 \lambda-16 \lambda^{2}-40 \lambda^{3}+72 \lambda^{5}+60 \lambda^{6}+30 \lambda^{7}+54 \lambda^{8}+52 \lambda^{9}+69 \lambda^{10}+119 \lambda^{11}+139 \lambda^{12}+91 \lambda^{13}+$
$35 \lambda^{14}+7 \lambda^{15}+28 \lambda^{16}+41 \lambda^{17}+52 \lambda^{18}+60 \lambda^{19}+54 \lambda^{20}+20 \lambda^{21}+6 \lambda^{22}-\lambda^{23}-4 \lambda^{24}-5 \lambda^{25}+\lambda^{26}+\lambda^{27}+$
$\lambda^{28}+\lambda^{29}+\lambda^{30}$ , which is a counterexample to this portion of the original conjecture.
For a proof of most of Conjecture 2, see Theorem on Spectra of Semidirect Products of Cyclic Groups of Odd Prime Order.
Conjecture 3: $q\left(\lambda\right)$ is irreducible if and only if $p_{2}>2p_{1}+1$ .
This conjecture is false. For $p_{1}=11$ and $p_{2}=23$ , $q\left(\lambda\right)$ is irreducible. Also, for $p_{1}=7$ and $p_{2}=43$ , $q\left(\lambda\right)$ is reducible.

[edit]

Proof Outline/Progress for Conjecture 2

1. Investigate change of basis using the group ring as a vector space.-COMPLETE
2. Investigate complex-valued matrices related to the resulting block matrices.-COMPLETE
3. Find a closed form for the characteristic polynomial of such a matrix.-COMPLETE
4. Show that all the interior coefficients in that polynomial are of degree $\frac{p_{2}-1}{3}$ .-COMPLETE
5. Show that characteristic polynomial divides a polynomial of degree $p_{2}-1$ with integer coefficients.-COMPLETE
6. Show that the block matrix satisfies this polynomial.-COMPLETE
7. Show that the block matrix has characteristic polynomial equal to this polynomial to the $p_{1}$ power.-COMPLETE
8. Write up a formal proof.-COMPLETE
9. Solve/prove minor remaining elements of conjecture.-IN PROGRESS
10. Report on wiki unused discoveries about these block matrices.-IN PROGRESS

[edit]

Generalized Dihedral Groups

Directed Cayley Graph of the generalized dihedral group of order 12 with cycle 4.

Directed Cayley Graph of the generalized dihedral group of order 28 with cycle 4.

Directed Cayley Graph of the generalized dihedral group of order 30 with cycle 6.

Definition 1:

Let the group $\Delta_{m,2mn}=\left<x,y\mid x^{n}=e, y^{2m}=e, yxy^{-1}=x^{-1}\right>=\mathbb{Z}/n\rtimes\mathbb{Z}/2m$ be called the generalized dihedral group of order mn with cycle 2m. It is clear that this gives the definition of a group. (Note that $\Delta_{1,2n}=D_{2n}$ and $\left|\Delta_{m,2mn}\right|=2mn$ .)

For conjectures on generalized dihedral groups, click here.

[edit]

Generalized Semidirect Products of Prime Cyclic Groups

In all cases, let $k$ be an integer such that $k^{p_{1}}\equiv1\left(\mathrm{mod}\:p_{2}\right)$ and $k\not\equiv1\left(\mathrm{mod}\:p_{2}\right)$ .

Theorem 6: Let $p_{2}>p_{1}$ be odd primes where $p_{1}\mid p_{2}-1$ . For all $m,n\in\mathbb{N}$ , there is a well-defined, non-abelian group of order $mnp_{1}p_{2}$ , which we will denote $\eta_{m,n,mnp_{1}p_{2}}=\mathbb{Z}/mp_{2}\rtimes\mathbb{Z}/np_{1}=\left<x,y\mid x^{mp_{2}}=e,y^{np_{1}},yxy^{-1}=x^{\kappa}\right>$ for some $\kappa$ such that $\kappa^{np_{1}}\equiv1\left(\mathrm{mod}\:mp_{2}\right)$

For the proof of this theorem, click here.

For conjectures on generalized dihedral groups, click here.

[edit]

Semidirect Products of a Z/p and Z/p-1

By Fermat's Little Theorem, taking $k$ to be any integer allows for a semidirect product between $\mathbb{Z}/p$ and $\mathbb{Z}/p-1$ for $p$ prime. I hope to investigate these groups if there is enough time.

[edit]

Results in Representation Theory

Here are some theorems connecting representation theory with algebraic graph theory.

[edit]

Results Relating to Schreier Graphs

Here are some results about Schreier graphs and how they relate to representation theory and semidirect products of cyclic groups.

[edit]

Useful Programs

Mathematica program that, given a graph, will return its spectrum (http://www3.canisius.edu/~prasside/reu-programs/grapheigs.txt)

Mathematica program that, given information about a group, will return its Cayley graph (http://www3.canisius.edu/~prasside/reu-programs/groups.txt)

Mathematica program that, given a graph in list form, converts it to a Combinatorica graph has been removed, as there already exists the Mathematica function ToCombinatoricaGraph.

Java program that converts LaTeX files to text files that will require less work to integrate into the wiki (http://www3.canisius.edu/~prasside/reu-programs/TexToWiki.java)

Java program that converts wiki text to LaTeX code, effectively inverting the previous program (http://www3.canisius.edu/~prasside/reu-programs/WikiToTex.java)

Mathematica program that does stuff with symmetric groups. (http://www3.canisius.edu/~prasside/reu-programs/CayleyGraphs-source-mod.nb) Modified Wolfram Demonstration. Please save this file as a .nb, or it won't work.

Combinatorica Graph Editor (http://www.cs.sunysb.edu/~skiena/combinatorica/grapheditor/), or, alternatively (better alternative), use the function call GraphEdit[] in Mathematica after calling Needs["GraphUtilities`"];.

Some useful code for graph drawing (Mathematica):
Needs["GraphUtilities`"]; g = GraphEdit[]; GraphPlot[g[[2]][[2]], {VertexCoordinateRules -> g[[3]][[2]], VertexLabeling -> True}]

Instructions for using Mathematica code: (first two links)
1. Click on the link.
2. Paste the code into text editor, and save with extension .txt. (Alternatively, steps 1 and 2 can be combined by right-clicking on the link and saving the destination.)
3. Open Mathematica. Write <<"Filepath"; in Mathematica and evaluate to import the file, where Filepath is the full path of the text file you saved. It may appear that there were errors, but there actually were not.
4. Write ?function, where function is the function you want to work with (cayleyGraph in groups.txt, graphEigenvalues in grapheigs.txt) and evaluate. This will give you instructions on how to use the function.