## Archive for March, 2009

### Orbit-counting Lemma

31 March, 2009

Excercises in algebra

One application of actions of finite groups is in combinatorics, more precisely, counting objects that possess particular symmetries.

A classical example are $n$necklaces and $n$bracelets. These are words of length $n$ in a $k$-letter alphabet, with beginnings and ends of the words glued together and made invisible (so one can visualise them as regular $n-gons$ with letters from the alphabet placed at the vertices). Two necklaces are identical when one is obtained from another by rotations; two bracelets are identical when one can be obtained from another by rotation and a “flip”. One can view counting of necklaces and bracelets as counting of orbits of certain groups on the sets of “labelled” necklaces (resp. bracelets). For the necklace case, the group is $\mathbb{Z}_n,$ and for the bracelet case it is the dihedral group of order $2n.$
The set $\Omega$ of labelled necklaces/bracelets is just the set of words of length $n$ in a $k$-letter alphabet; so one has $|\Omega|=k^n.$

Orbit counting is often simplified by the following result, often attrubuted to Burnside, although it was certainly known to Frobenius.

Let a finite group $G$ act on a finite set $\Omega.$ Denote by $\Omega^g,$ for $g\in G,$ the set of elements of $\Omega$ fixed by $g.$ Then the number $N$ of orbits of $G$ on $\Omega$ is the average, over $G,$ of $|\Omega^g|,$ i.e.
$\displaystyle N=\frac{1}{|G|}\sum_{g\in G} |\Omega^g|.$

The proof involves counting of edges in the bipartite graph, with one part being $\Omega,$ and the other being $G;$ a pair $(\omega,g),$ for $\omega\in\Omega$ and $g\in G$ is an edge iff $\omega\in\Omega^g.$ Thus the total number of edges in this graph is $\sum_{g\in G} |\Omega^g|.$
On the other hand, a pair $(\omega,g)$ is an edge iff $g\in G_{\omega},$ the stabiliser of $\omega$ in $G.$ Thus, for a $G$-orbit $\Omega_\omega,$ one has the total number of edges leaving $\Omega_\omega$ equal to $|\Omega_\omega||G_\omega|=|G|.$ Summing over all the $G$-orbits, one obtains the total number of edges $N|G|,$ completing the proof.

Often it is easier to sum over distinctive representatives $R=\{g_1,\dots,g_t\}$ of the conjugacy classes $g^G=\{xgx^{-1}\mid x\in G\},$ as $|\Omega^g|=|\Omega^{xgx^{-1}}|.$ So one has
$\displaystyle N=\frac{1}{|G|}\sum_{g\in R } |\Omega^g||g^G|=\sum_{g\in R } \frac{|\Omega^g|}{|C_G(g)|},$
where $C_G(g):=\{x\in G\mid xgx^{-1}\}$ denoting the centraliser of $g$ in $G.$

Let us see how this can be applied to counting bracelets. For simplicity, let us assume that $n$ is prime. We consider natural the action of the dihedral group $G=D_{2n}$ on the set of $k^n$ words of a $k$-letter alphabet.

We know that $G$ is generated by the cyclic permutation $c=(1,2,\dots,n)$ and an order two “flip” permutation $f=(2,n)(3,n-1)\dots (\lfloor n/2\rfloor,\lceil n/2\rceil).$ The group can be decomposed into the union of cosets $G=\langle c\rangle\cup f\langle c\rangle.$
The only words fixed by a nonidentity element $x=c^m$ of the subgroup $\langle c\rangle$ are the “constant” ones, i.e. words consisting of a single letter, and so $|\Omega^x|=k.$ The coset $f\langle c\rangle$ equals $f^G$ (an unusual coincidence), and so it suffices to find
$\Omega^f.$ For a word $w$ to be in the latter set, it must have $w_2=w_n,$ $w_3=w_{n-1},$$w_{\lfloor n/2\rfloor}=w_{\lceil n/2\rceil},$ so there are $k^{(n+1)/2}$ possibilites.
Thus we count $N|G|=2nN=|\Omega|+(n-1)|\Omega^c|+n|\Omega^f|=k^n+(n-1)k+n k^{(n+1)/2}.$
E.g. for $n=5,$ $k=3$ one obtains $N=39.$

### Group actions

25 March, 2009

We have already seen abstract groups as permutation groups, or, more generally, as groups of bijections, in a number of contexts:

• $G$ acting on itself by (left) multiplication, when we associated with each $g\in G$ a bijection $L_g:G\to G$ by $L_g(x)=gx$
• $G$ acting on itself by conjugation, when we associated with each $g\in G$ a bijection $C_g:G\to G$ by $C_g(x)=gxg^{-1}$
• $G$ acting on the set of (left) cosets $G/H=\{gH\mid g\in G\}$ of a subgroup $H\leq G,$ when we associated with each $g\in G$ a bijection $M_g:G/H\to G/H$ by $M_g(xH)=gxH$

We have also seen matrix groups at work as permutation groups (e.g. on the set of subspaces), permutation groups becoming matrix groups (e.g. $S_n$ represented by $n\times n$ permutation matrices), etc.
What unites all these examples is the concept of a group action.

Let $G$ be a group and $\Omega$ be a set, with a group of bijections $S(\Omega).$ An action of $G$ on $\Omega$ is a homomorphism $\phi: G\to S(\Omega).$

There are many different types of actions, e.g. permutation actions when $\Omega$ is a finite set and $S(\Omega)$ the symmetric group (of all permutations of $\Omega,$
linear actions, when $\Omega$ is a vector space, and $S(\Omega)$ a group of its linear transformations (i.e. matrix groups), etc.

By the homomorphism theorem, $Im(\phi)\cong G/Ker(\phi).$ An action satisfying $Ker(\phi)=\{id\}$ is called faithful (or effective).
For instance, the action of $G$ on itself by (left) multiplication is always faithful, but the action on cosets of an $H\leq G$ need not be faithful. E.g. it will not be faithful if $G$ is commutative and $H\neq\{id\}.$

Orbits and point stabilisers
An action $\phi$ of $G$ on $\Omega$ defines an equivalence relation $\sim$ on $\Omega,$ as follows: $a\sim b$ iff there exists $g\in G$ such that $\phi(g)a=b.$ The equivalence classes of $\sim$ are called orbits (more precisely, orbits of $Im(\phi)$ on $\Omega$).
Let $\omega\in\Omega$ and $G\geq H=\{h\in G\mid \phi(h)\omega=\omega\}.$ Then $\phi(H)$ is called the stabiliser of $\omega$ in $\phi(G),$ and denoted $\phi(G)_\omega.$

Let $\omega'=g\omega$ for some $g\in \phi(G).$ What can be said about $\phi(G)_{\omega'}?$

$\phi(G)_{\omega'}=g\phi(G)_\omega g^{-1}.$

Indeed, the coset $g\phi(G)_\omega$ consists of the elements of $\phi(G)$ that map $\omega$ to $\omega'.$ Thus any $x\in H:=g\phi(G)_\omega g^{-1}$ fixes $\omega',$ and any $y$ that fixes $\omega'$ belongs to $H,$ as $g^{-1}yg\in \phi(G)_\omega.$

When we consider the action $C: G\to G$ of $G$ on itself by conjugation, the orbits are called conjugacy classes.
For instance, the conjugacy classes of $S_n,$ the symmetric group on $n$ letters, can be shown to be in 1-to-1 correspondence with the unordered partitions of $n$ into parts $1\leq p_1\leq p_2\leq\dots\leq p_k,$ where $n=p_1+\dots +p_k,$ as follows:
Let a permutation $\sigma=(i_{1,1},\dots,i_{1,p_1})\dots (i_{k,1},\dots,i_{k,p_k})$ be written in the cyclic notation. Then for any $\tau\in S_n$ one has

$\displaystyle \tau\sigma\tau^{-1}=(\tau(i_{1,1}),\dots,\tau(i_{1,p_1}))\dots (\tau(i_{k,1}),\dots,\tau(i_{k,p_k})),$

and so we can transform $\sigma$ to any permutation with cycles of the same lengths $p_1,\dots,p_k.$

Equivalent actions
When do two actions $\phi$ and $\psi$ of a group $G$ on, respectively, sets $\Omega$ and $\Sigma$ can be viewed as “the same”? Obviously we need a bijection $f:\Omega\to\Sigma$ to exist, that also “respects” $G,$ in the sense that $f(\phi(g)\omega)=\psi(g)f(\omega)$ for all $\omega\in\Omega$ and $g\in G.$ Such an $f$ is called a $G$equivariant bijection, and is said to define an isomorphism of actions.

An action that has just one orbit is called transitive.

Let $\phi$ be a transitive action of $G$ on $\Omega.$ Then $\phi$ is isomorphic to the action on $G/G_\omega=\{gG_\omega\mid g\in G\},$ for any $\omega\in\Omega,$ where we denoted by $G_\omega$ the preimage of $\phi(G)_\omega$ in $G.$

This isomorphism of actions is given by $f:\Omega\to G/G_\omega$ such that $f(\mu)=gG_\omega,$ where $\phi(g)(\omega)=\mu.$ Indeed,

1. $f$ is obviously a bijection
2. $\phi(h)\omega=\mu$ iff $\phi(g^{-1}h)\omega=\omega$ iff $g^{-1}h\in G_\omega$ iff $h\in gG_\omega$
3. $f$ is $G$-equivariant. Indeed, let $\phi(h)(\omega)=\mu.$ Then for any $g\in G$ one has $f(\phi(g)\mu)=f(\phi(gh)\omega)=(gh)G_\omega=g(hG_\omega)=\phi(g)f(\mu),$ as claimed.

Finally, for an action $\phi$ of $G$ on $\Omega$ we can characterise $Ker(\phi)$ as

$\displaystyle Ker(\phi)=\bigcap_{g\in G} gG_\omega g^{-1},$ for an $\omega\in\Omega.$

Actions of matrix groups (a.k.a. linear actions)
Subgroups of $GL_n(\mathbb{F}),$ the group, with respect to matrix multiplication, of invertible $n\times n$ matrices with entries in a field $\mathbb{F},$ have a number of natural actions, that all come one way or another from the vectorspace $V\cong \mathbb{F}^n.$ Indeed, each $g\in GL_n( \mathbb{F} )$ provides a bijection $V\to V$ by $v\mapsto gv$ for any $v\in V.$ Moreover, such a bijection is even an automorphism of the vectorspace $V.$ (Automorphisms of vectorspaces are defined just as these for groups and rings: these are bijections preserving the corresponding algebraic structure (i.e. operations, etc)).

Apart from the action $v\mapsto gv$ on the vectors of $V,$ (called the natural action (by left multiplication)) there is another action on the vectors, namely, by $v\mapsto vg^{-1}$ (which one can equivalently writen as $v\mapsto (g^{-1})^T v$). It is called contragradient action.
(Note that the map $f$ given by $v\mapsto vg$ is not always an action, as $f(gg')=f(g')f(g),$ and so $f$ is not a homomorphism, unless we have a commutative group.)

Natural and contragradient actions give a simple example of two non-equivalent faithful (i.e. with trivial kernel) actions of one group, say, $G=GL_n(\mathbb{F} )$, with $n\geq 2,$ on the same set $V.$ Indeed, if $f:V\to V$ were an equivalence of these actions, then $f(gv)=(g^{-1})^T (f(v))$ for all $v\in V$ and $g\in G.$
Let $n=2$ and $f(v)=u$ so that $u$ and $v$ are linearly independent. In the basis $(v,u)$, take $g=\begin{pmatrix} 1&1\\ 0& 1\end{pmatrix}.$ Then $(g^{-1})^T=\begin{pmatrix} 1&0\\ -1& 1\end{pmatrix}.$ We see that $f(gv)=f(v)=u\neq (g^{-1})^T(u),$ a contradiction.
If, on the other hand, $f(v)$ and $v$ are always linearly dependent,
we take the same $g$ in the standard basis $(v,w)$ and see that $f(gv)=f(v)=\alpha v=(g^{-1})^T (f(v))=\alpha (g^{-1})^T (v),$ for some $0\neq \alpha\in\mathbb{F},$ again a contradiction. The argument showing non-equivalence in the case $n\geq 3$ is similar. For $n=1$ these two actions are isomorphic, as $GL_1(\mathbb{F})$ is commutative.

Another important class of actions is the action on $G\leq GL_n(\mathbb{F} )$ on subspaces of $V.$ For simplicity, let us consider the action on the set $\Gamma_k(V)$ of subspaces of dimension $k.$ Given a $k$-dimensional subspace $U\subset V$ and $g\in G,$ we define $g(U)=\{gu\mid u\in U\}.$ Then $g(U)$ is a $k$-dimensional subspace, as can be seen by choosing a basis $u_1,\dots, u_k$ of $U$ and observing that $gu_1,\dots,gu_k$ is a basis of $g(U).$ Thus $g$ induces a bijection on $\Gamma_k(V).$
When $G$ fixes a $U\in\Gamma_k(V),$ we can choose a basis in such a way, that $G$ becomes a group of $2\times 2$ block matrices, discussed earlier here.In this case $G$ has a normal subgroup acting trivially on $U,$ that is the kernel of the action of $G$ on the quotient space $V/U.$

The centre $Z=Z(GL_n(\mathbb{F} ))$ of $GL_n(\mathbb{F} )$ acts trivially on $\Gamma_k(V),$ as it preserves every 1-dimensional subspace (indeed, any $g\in Z$ equals $\lambda I,$ with $0\neq\lambda\in\mathbb{F}$).

Projective line.
The simplest nontrivial $\Gamma_k(V)$ is $\Gamma_1(V)$ when $n=2.$ This set is called projective line and denoted $\mathbb{F}P^1,$ and can be viewed as the set of pairs $\{(1:\alpha)\mid \alpha\in \mathbb{F}\}\cup\{(0:1)\},$ as follows: every 1-dimensional subspace $(x:y)$ of $V$ can be described by equation $y=\alpha x$ or by equation $x=0.$
To understand the action of an element $g$ of $G=GL_2(V)$ on $\mathbb{F}P^1,$ consider $g=\begin{pmatrix} a& b\\ c& d\end{pmatrix}$ and $g((x:y))=(ax+by:cx+dy)$ just as if we multiply a vector by $g,$ and then normalize either to $\left(1:\frac{cx+dy}{ax+by}\right)$ or to $(0:1),$ depending upon whether or not $ax+by=0.$

### Strongly regular graphs and generalised quadrangles

16 March, 2009

A generalised quadrangle with lines of size $s+1$ and with $t+1$ points on each line (a $GQ(s,t)$, for short) has a lot of “regularity” – and as we learned from a previous post, any finite “non-degenerate” GQ is a $GQ(s,t)$ for some $s,t\geq 2.$ This regularity allows for the use of quite a bit of linear algebra and algebraic graph theory in investigating them.
One considers the collinearity graph of the GQ $(P,L).$

The collinearity graph of a GQ $(P,L)$ is the graph with the vertex set $P,$ two vertices $u,v$ are adajcent iff they are collinear, i.e. if there exists $\ell\in L$ such that $u,v\in \ell.$

For a $GQ(s,t),$ such a graph is strongly regular, see wikipedia for a good short intro.
Basically, a graph $\Gamma=(V,E)$ is strongly regular if it is

• regular, i.e. each vertex is adjacent to $k$ other vertices;
• for each edge $(u,v)\in E,$ there are exactly $\lambda$ vertices $w\in V$ such that $(u,w),(v,w)\in E;$
• for each non-edge $(u,v)\in \binom{V}{2}-E,$ there are exactly $\mu$ vertices $w\in V$ such that $(u,w),(v,w)\in E.$

One says that when $\Gamma$ is as above, one has an $srg(|V|,k,\lambda,\mu).$ One famous example of a srg is the Petersen graph. It is an $srg(10,3,0,1).$

Exercise.

1. Prove that the collinearity graph of an $GQ(s,t)$ $(P,L)$ is an $srg(|P|,s(t+1),s-1,t+1).$
2. Compute $|P|$ as a function of $s$ and $t.$ (namely, it is $(s+1)(st+1)$)

An important tool in studying srg’s, and graphs in general, is the

Adjacency matrix of a graph $\Gamma=(V,E)$ is the $|V|\times |V|$ matrix $A=A(\Gamma)$ that has $A_{uv}=1$ for each $(u,v)\in E$ and otherwise $A_{uv}=0.$

In particular $A=A^T$ and the $v$-th row sum is the number of vertices adjacent to $v.$ This means that the all-1 vector is an eigenvector of $A$ with eigenvalue $k.$ In fact, this is the largest eigenvalue, and for the connected graphs it has 1-dimensional eigenspace. For srgs, much more can be said.

For a connected $\Gamma$ an $srg(v,k,\lambda,\mu),$ the adjacency matrix $A$ has at most 3 distinct eigenvalues, namely $k$ and $(\lambda-\mu\pm\sqrt{(\lambda-\mu)^2-4(k-\mu)})/2.$

This follows from the fact that multiplication of 0-1 matrices boils down to computing certain combinatorial parameters of underlying graphs. E.g. $(A^2)_{uv}$ is the number of length 2 walks from $u$ to $v.$ In our case we have

$\displaystyle A^2=kI+\lambda A+\mu (J-I-A),$

where $I$ is the identity matrix and $J$ the all-1 matrix. Any eigenvector $z$ with eigenvalue $\theta\neq k$ must be orthogonal to the $k$-eigenvector, in particular $Jz=0.$ Thus

$\displaystyle A^2z=kIz+\lambda Az-\mu (I+A)z,$

and this translates into $\theta^2=k+\lambda\theta-\mu-\mu\theta,$

a quadratic equation! It remains to compute its solutions to establish the claim.

Moreover, one can compute the multiplicities of the eigenvalues of $A.$
Indeed, we know that $k$ has multiplicity $1,$ and so the other two eigenvalues have multiplicities $m_1$ and $m_2$ that satisfy

• $m_1+m_2=v-1$ (by just discussed) and
• $m_1\theta_1+m_2\theta_2+k=0$ (as the trace of $A$ is 0.)

We can solve these two linear equations to obtain

$m_{1,2}=\left(v-1\pm\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2-4(k-\mu)}}\right)/2.$

These are powerful conditions that rule out large sets of tuples $(v,k,\lambda,\mu),$ as $m_1,m_2$ must be nonnegative integers!

For an srg arising from a $GQ(s,t),$ one can compute that the eigenvalues of $A$ are $s(t+1),$ $s-1,$ and $-t-1.$

This gives one, by computing the multiplicities, that for $s=2$ one has $t\in\{1,2,4,10\}.$ With more work (one needs e.g. the Krein bound) the case $t=10$ can be ruled out.

### Cosets and normal subgroups

11 March, 2009

Just as in the case of abelian groups, each subgroup $H\leq G$ gives rise to a coset decomposition of $G,$ or, more precisely, to two decompositions, into left cosets i.e.

$\displaystyle \{gH\mid g\in G\},$

and right cosets, i.e.

$\displaystyle \{Hg\mid g\in G\}.$

It is proved by the same argument as in the case of abelian groups that one indeed has decompositions of $G$ in this way.
Unlike in the case of abelian groups, these two decompositions need not be the same: an example is given by $S_3\geq H\cong S_2.$
The following is an important and elementary implication of the fact that all the cosets of $H$ have the same cardianlity:

Let $|G|<\infty,$ and $H\leq G.$ Then $|H|$ divides $|G|.$

An extremely important case (and, in fact, the only case) when these two decompositions are the same is when $H=Ker(\phi),$ where $\phi: G\to F$ is a group homomorphism. (Just as in the case of abelian groups, one can show that $Ker (\phi)\leq G$ and $Im(\phi)\leq F.$)
We need to show that for any $g\in G$ and $k\in Ker(\phi)$ one has $gk=k'g$ for some $k'\in Ker(\phi).$ We compute $\phi(gk)=\phi(g)\cdot 1_F=\phi(k')\phi(g)=\phi(k'g).$ Hence $gK=Kg.$

A subgroup $H\leq G$ satisfying $gH=Hg$ for all $g\in G$ is called normal (notation: $H\unlhd G,$ or $H\lhd G,$ when $H\neq G.$)

Often it is more convenient to work with the equivalent condition for normality, namely that $gHg^{-1}=H$ for all $g\in G.$

Examples of normal subgroups.

• The subgroup generated by $\begin{pmatrix}1&2&3\\3&1&2\end{pmatrix}$ in $S_3$ is normal.
• $H\leq G=GL(n,\mathbb{F})$ defined by $H=\{x\in G\mid\det x=1\}$ is normal.
• $H\leq G$ of index 2 (i.e. the one that has exactly 2 left cosets in $G$) is normal.

The 1st is easy to establish directly (it also follows from the 3rd).The 2nd follows from the identity $\det x=\det (gxg^{-1}).$
The 3rd follows from the equality $G=H\sqcup gH=H\sqcup Hg',$ and an observation that $g\in Hg',$ so $Hg'=Hg.$

Cosets play an important role in constructing “easier” groups from “complicated” ones, by the quotient group construction. The difference with the case of abelian groups is that only normal subgroups can be kernels of homomorphism.

Let $H\unlhd G.$ Then $G/H:=\{gH\mid g\in G\}$ is a group with operation $(gH)(g'H)=(gg')H,$ and $g\mapsto gH$ a group homomorphism $\phi: G\to G/H$ with the kernel $Ker\phi=H.$

We need to use $gH=Hg$ to establish that the multiplication in $G/H$ is well-defined: $(gH)(g'H)=(gH)(Hg')=g(HH)g'=g(Hg')=(gg')H.$
Then $G/H$ is a group with the identity element $H,$ as associativity in $G/H$ follows from the associativity in $G,$ and $(gH)^{-1}=(g^{-1})H.$
It can be readily checked that $\phi$ is a homomorphism, and that $H= Ker\phi.$ Indeed, $\phi(gg')=(gg')H=(gH)(g'H).$ Also, $\phi(h)=hH=H$ for $h\in H,$ and so $H\leq Ker\phi.$ On the other hand if $g\in G-H$ then $\phi(g)=gH\neq H,$ and so $H\geq Ker\phi.$

Matrix groups
Subgroups of $GL_n(\mathbb{F}),$ the group, with respect to matrix multiplication, of invertible $n\times n$ matrices with entries in a field $\mathbb{F},$ provide a rich playground for various examples of normal subgroups and quotient groups. To this end, we will work with block matrices, i.e. we will partition our matrices into rectangular blocks of appropriate size, so that this block decomposition is preserved under the matrix multiplication. The simplest case is the following partition into 4 blocks (i.e. $2\times 2$ block matrices).

Given an $n\times n$ matrix $A$ and positive integer $p we can view $A$ as $A=\begin{pmatrix} A_{11}&A_{12}\\A_{21} & A_{22}\end{pmatrix},$ where $A_{11}$ is a $p\times p$ matrix, $A_{22}$ a $(n-p)\times (n-p)$ matrix (and certainly $A_{12}$ and $A_{21}^T$ being of size $p\times (n-p)$).

Let us fix $n$ and $p.$
First, we need to convince ourselves (an easy exercise in matrix multiplication) that the following multiplication law works for two block matrices $A$ and $B$:
$\displaystyle AB=C=\begin{pmatrix} A_{11} B_{11}+A_{12}B_{21}& A_{11}B_{12}+A_{12}B_{22}\\ A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{pmatrix}$
It should of course look very familiar, as this is exactly how two $2\times 2$ matrices are multiplied.
When $A_{21}=B_{21}=0,$ we see that the shape is preserved, i.e. $C_{21}=0.$ More precisely
$\displaystyle AB=C=\begin{pmatrix} A_{11} B_{11}& A_{11}B_{12}+A_{12}B_{22}\\ 0 &A_{22}B_{22}\end{pmatrix}$
We see that the blocks with indices 11 and 22 behave as if “nothing around them matters”, as if they sit in their own groups $G_p(\mathbb{F})$ and $G_{n-p}(\mathbb{F})$ (that is, assuming the matrices we talk about are invertible). We can formalise this observation as follows.

Let $H be a subgroup of $2\times 2$ block matrices, with diagonal blocks of sizes $p\times p$ and $(n-p)\times (n-p),$ and such that $A_{21}=0$ for all $A\in H.$ Then

1. the maps
$\phi_1 : H\to GL_p(\mathbb{F}):\quad A\mapsto A_{11}$ and
$\phi_2 : H\to GL_{n-p}(\mathbb{F}):\quad A\mapsto A_{22}$
are group homomorphisms.
2. $Ker(\phi_k)=\{A\in H\mid A_{kk}=I\}$ for $k=1,2.$

The reader is encouraged to provide a proof.
More generally, this result can be interpreted in terms of the actions of $H$ on the $n-$dimensional vectorspace $V$ over $\mathbb{F}.$

Exercise. Prove that the intersection of two normal subgroups of a group is a normal subgroup. Based on this, describe $Ker(\phi_1)\cap Ker(\phi_2),$ and derive that $\{A\in H\mid A_{11}=I, A_{22}=I\}$ is a normal subgroup of $H.$

Note that $Im(\phi_k)$ (where $k=1$ or $K=2$) cannot be obtained by simply setting the remaining off-diagonal block of $H$ to 0, and the remaining diagonal block to the identity matrix. For instance, let $H be generated by the matrix $X=\begin{pmatrix} \mathbf{i}&0\\ 0& -1\end{pmatrix},$ where $\mathbf{i}=\sqrt{-1}.$ Then $H$ is a cyclic group of order 4, and it satisfies the conditions of the above lemma with $n=2,$ $p=1.$ It is easy to see that $\phi_1$ is an isomorphism, and $\phi_2$ is a homomorphism with the kernel generated by $X^2.$

Let us denote $K_k=Ker(\phi_k),$ and $K_{12}=K_1\cap K_2.$
As $|H|=|K_k||Im(\phi_k)|,$ by the usual argument involving decomposition of $H$ into the cosets of $K_k,$ computing $|H|$ for $\mathbb{F}= \mathbb{Z}_q,$ for $q$ prime, can be accomplished by computing $|K_k|$ and $|Im(\phi_k)|$ separately. In turn, $|K_k|=|K_{12}||Im(\phi_{3-k}|,$ so we can simplify the task of computing $|K_k|,$ too.

To illustrate this principle, let us compute the order of
$\displaystyle H=\{A\in GL_n( \mathbb{Z}_q)\mid A_{21}=0.\}\qquad\qquad (1)$
First we derive the following:

$|GL_m( \mathbb{Z}_q)|=(q^m-1)(q^m-q)(q^m-q^2)\dots (q-1),$ where $q$ is prime.

Indeed, we can fill in the 1st row of an $m\times m$ matrix in $q^m-1$ way (everything goes, except all zeros). Fixing this 1st row vector $v_1,$ we can again fill in the 2nd row with entries of any vector $v_2,$ which is linearly independent (to get an invertible matrix) of $v_1,$ i.e. lies outside of the subspace $V_1$ spanned by $v_1.$ As $|V_1|=q,$ we get $q^m-q$ ways to choose $v_2.$ Now we fix $v_2,$ as well, and fill in the 3rd row with entries of any vector $v_3,$ which is linearly independent of $v_1$ and $v_2,$ i.e. lies outside of the subspace $V_2$ spanned by $v_1$ and $v_2.$ As $|V_2|=q^2,$ we get $q^m-q^2$ ways to choose $v_2.$
So when filling the $(\ell+1)$-th row, we have $q^m-q^\ell$ choices, giving us the formula above.

Now, we claim that $|K_{12}|=q^{p(n-p)}.$ Indeed, $K_{12}$ consists of $A$ such that $A_{21}=0,$ $A_{11}=I,$ $A_{22}=I,$ whereas we can fill the entries of $A_{12}$ without any strings attached – the result will be invertible. Thus we have
$|H|=(q^p-1)(q^p-q)\dots (q-1) q^{p(n-p)} (q^{n-p}-1)(q^{n-p}-q)\cdots (q-1).$

Excercise. Compute $|H'|$ for $H'=\{A\in H\mid \det A=1\}$ and $H$ as in (1).
(Hint: use the fact that $\det$ is a group homomorphism.)

### Existence of maximal ideals

11 March, 2009

Let $R$ be a commutative ring with 1. Then there exists a maximal ideal in $R,$ i.e. a proper ideal $I$ such that the only ideal that contains $I$ is $R$ itself.

We did not discuss this in the class, and the main reason is that it requires a form of the Axiom of Choice. We will use its form, known as Zorn’s Lemma

Every partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.

We take the set $\mathcal{I}$ of all proper ideals of $R$ as the set ordered by inclusion, i.e. $K\leq J$ iff $K\subseteq J,$ for $K,J\in\mathcal{I}.$
Any chain is then a set of ideals $\mathcal{J}$ such that for any $K\neq J\in \mathcal{J}$ either $K\subset J$ or $J\subset K.$ We need to check that $\mathcal{J}$ has an upper bound, i.e. $U\in\mathcal{I}$ such that $K\subseteq U$ for any $K\in\mathcal{J}.$ Set $U=\cup_{K\in\mathcal{J}} K.$
We need to check that $U\in\mathcal{J},$ i.e. that it is a proper ideal. As $1\not\in U,$ we only need to check that it is an ideal. It suffices, and is easy, to see that

• for any $x,y\in U$ there exists $K\in\mathcal{J}$ such that $x,y\in K,$ and thus $x+y\in K\subseteq U.$ (Indeed, there exists $K',K''\in\mathcal{J}$ such that $x\in K',$ $y\in K'',$ and w.l.o.g $K'\subseteq K''=K,$ as $\mathcal{J}$ is a chain)
• for any $x\in U$ and $r\in R$ here exists $K\in\mathcal{J}$ such that $rx\in K,$ and thus $rx\in U.$ (Indeed, there exists $K\in\mathcal{J}$ such that $x\in K,$ and $rx\in K,$ as $K$ is an ideal.)

Thus Zorn’s Lemma is applicable to $\mathcal{J}$, so it has maximal element, that is obviously a maximal proper ideal in $R.$ QED.

As a corollary, we see that every proper ideal $K\subseteq R$ is contained in a maximal proper ideal $I.$ Indeed, $R/K$ contains a maximal proper ideal $F,$ and $F=J/I$ for a maximal ideal $J\supset I.$
In particular, any non-invertible element $x\in R$ is contained in such an ideal, by applying the latter construction to $K=(x).$

### we had a midterm last week…

10 March, 2009

more animals

9 March, 2009

For the purposes of classifying “single-bonded” root systems, we would like to consider the following (finite) incidence structure, known as generalised quadrangle

A pair $(P,L),$ with $P$ a set (elements of $P$ are referred to as points) and $L\subset 2^P$ (elements of $L$ are referred to as lines) is called a generalised quadrangle provided the following holds:

1. the lines are of size at least 2
2. for every point there is at least one line containing it
3. for every point $p$ and every line $\ell$ there exists unique line $m\ni p$ such that $\ell\cap m\neq\emptyset.$

The 3rd axiom implies that two lines intersect in a most one point, and so indeed can be visualised as such. This permits one to talk about collinearity of points: two points are collinear iff there exists a line containing them both. Also, note that it implies that in $(P,L)$ there are no “triangles”, i.e. triples of lines each two of which intersect, so that there are 3 non-collinear intersection points in total.

Examples

1. a “line” $(P,\{P\}),$ i.e. there is just one line on all the points
2. a “claw”, i.e. $(P,L)$ such that there exists $p\in P$ such that $p\in\ell$ for all $\ell \in L$ (and so any $x\in P-\{p\}$ is on just one line)
3. a complete bipartite graph, i.e. $(P,L)$ with $P$ being the set of vertices of a complete bipartite graph and $L$ being the set of its edges (so in particular every line contains just 2 points)
4. a “grid”, i.e. $(P,L)$ with $L$ being two sets of parallel lines in $\mathbb{R}^2$ and $P$ being their pairwise intersections
5. for $\Omega=\{1,\dots,6\}$ let $(P,L)$ with $P$ being the set $\binom{\Omega}{2}$ of unordered pairs of elements of $\Omega,$b and $L$ the set of partitions of $\Omega$ into three pairs; in particular $|P|=|L|=15.$

Note that the 3rd and the 4th examples are dual to each other in the following sense.
In $(L,P)$ the points are the lines of $(P,L)$ and the lines are the sets of lines collinear to a point $p,$ for each $p\in P.$

Let $(P,L)$ be a generalised quadrangle. Then its dual, the incidence system $(L,P),$ is also a generalised quadrangle, provided that it is neither a “line” nor a “claw”.

We have to exclude “lines” and “claws” as their duals have lines of size 1.

To emphasise the roles of points and lines as dual to each other, we say that $p\in P$ and $\ell\in L$ are incident if $p\in\ell.$
It is an interesting exercise to show that the 5th example is self-dual, i.e. there exists a bijection $\phi:P\to L$ preserving the incidence point-line relation.

Regularity
The 3rd axiom implies that for any two skew (i.e. non-intersecting) lines $\ell,\ell'$ there is a bijection $\psi_{\ell,\ell'}$ between the sets of points incident to them. This means that any two lines $\ell,\ell'$ without $\psi_{\ell,\ell'}$ must intersect. One can show that more than two different cardinalities are only possible for a “claw”, as follows:
Three lines $a,b,c$ with three different cardinalities must have a common intersection point, say $p.$ A line $\ell$ that is not on $p$ can intersect at most one of the three lines, say $a.$ Therefore there are bijections $\psi_{b,\ell}$ and $\psi_{\ell,c},$ and $\psi_{b,\ell}\circ\psi_{\ell,c}$ is a bijection between points on $b$ and points on $c,$ contradiction proving the claim.

Similarly, one can show that two different cardinalities are only possible for a “grid” or a “claw”. Indeed, let $a,b$ be two skew lines, and $c$ a line of a different cardinality. Then every line $c'\neq c$ that joins a point on $a$ to a point on $b$ must have the same cardinality as $c.$ On the other hand, every line of a cardinality different from the one of $a$ intersects both $a$ and $b.$ In particular these lines do not intersect. Similarly, the lines with the same cardinality as $a$ intersect $c$ and $c'.$ It follows that we have a “grid”.

It is also not hard to see that when all the lines are of size 2 we have the complete bipartite graph example.

From now on let us assume that all the lines has the same cardinality $s,$and that $(P,L)$ has the dual. Looking at the dual, we either encounter one of the “easy” cases as above, or derive that all the dual lines must have the same cardinality $t.$ Such $(P,L)$ are called regular.