Protected: a subgeometry of D_3-dual polar space

29 May, 2009 in Uncategorized | Tags: | Enter your password to view comments

This post is password protected. To view it please enter your password below:


Prime ideals and rings of fractions

10 April, 2009 in undergrad maths | Tags: , , | Leave a comment

The concept of prime ideal in a commutative ring R with 1 is one of several natural generalisations of the concept of prime integer number.

An ideal I\subset R is called prime if for any u,v\in R the following holds:
uv\in I implies that at least one of these elements, u and v, is in I.

E.g. the principal ideal (p)\subset \mathbb{Z} is prime if and only if p is prime.

A maximal ideal I\subset R is prime.

Indeed, let uv\in I. Assume that u\not\in I. We need to show that then v\in I. If this were not the case then u+I and v+I are two non-zero elements in the ring R/I such that (u+I)(v+I)\subseteq I. But this is not possible, as R/I is a field. Thus v\in I, as claimed.

Analysing this proof, one can easily see that

If I\subset R is prime then R/I has no zero-divisors, i.e. it is an integral domain.

Further important property of prime ideals is that they are radical, i.e.
I=\sqrt{I}, where the radical \sqrt{I} of the ideal I ideal is \sqrt{I}=\{x\in R\mid \exists k\geq 1 : x^k\in I\}. Indeed, x^k\in I implies that either x or x^{k-1} is in I, and we derive x\in I by applying this reduction.

Yet another interesting observation is that R\setminus I is multiplicatively closed.

Rings of fractions

A subset S\subset R is called multiplicatively closed (or multiplicative) if 0\not\in S, 1\in S, and uv\in S for any u,v\in S.

Given a multiplicatively closed set S\subset R, one defines
a relation on R\times S, as follows:

{\displaystyle (y,t)\equiv (x,s)\quad\text{iff there exists }u\in S: uys=uxt.}

It is not hard to show that \equiv is an equivalence relation.
To simplify the notation, write its equivalence class with representative (x,s) as \frac{x}{s}. We define

S^{-1}R=(R\times S)/\equiv is the ring of fractions of R w.r.t. S, with addition and multiplication given by the rules
\frac{x}{s}+\frac{y}{t}=\frac{xt+ys}{st}, \frac{x}{s}\cdot\frac{y}{t}=\frac{xy}{st}.

It is easy to check that this is well-defined. We also have

\phi: R\to S^{-1}R, so that \phi(x)=\frac{x}{1}, is a ring homomorphism.

Note that \phi need not be injective, i.e. \phi(R)\cong R need not hold. Indeed, if x\in R is a zero-divisor such that xu=0 for u\in S then (x,1)\equiv (0,1), and so \phi(x)=\frac{x}{1}=\frac{0}{1}=0_{S^{-1}R}.

The most well-known example is the case R being an integral domain, and S=R\setminus\{0\}. Then S^{-1}R is a field, called the field of fractions of R.

Examples:

  • \mathbb{Q} is the field of fractions of \mathbb{Z}
  • for the ring of polynomials \mathbb{F}[T] over a field \mathbb{F} the field \mathbb{F}(T) is the field of rational functions over \mathbb{F} .
  • Let x\in R be non-nilpotent. Then S=\{1,x,x^2,x^3,\dots\} isa multiplicative set. Moreover, then S^{-1}R\cong R[T]/(Tx-1) (it is not completely trivial to prove this, though). Intuitively, we make the variable T behave like the inverse of x, as Tx=1 in this ring.

Now let us look at the case S=R\setminus I, for I a nonzero prime ideal. In this case S^{-1}R is denoted by R_I and called the localisation of R at I.

Example: Let \mathbb{F}[T] be the ring of polynomials over a field \mathbb{F}, and a\in \mathbb{F}. Then I=(T-a) is prime, and R_I=\mathbb{F}[T]_{(T-a)} is equal to \{\frac{f}{g}\in \mathbb{F}(T)\mid (T-a)\not|\, g \}.

The ring R_I has unique maximal ideal IR_I.

It suffices to show that \frac{x}{s} is invertible in R_I iff {x}\not\in I. Indeed, if x\in S then \frac{x}{s}\frac{s}{x}=1. On the other hand, if \frac{x}{s}\frac{y}{t}=1 then there exists u\in S such that uxy=ust. Thus uxy\not\in I, and so x\not\in I (if it was, uxy would be in I, as I is an ideal).

Dual spaces

5 April, 2009 in undergrad maths | Tags: , , | 1 comment

There is one glaring omission in our Linear Algebra curriculum – it avoids talking about the dual space of a vector space. This makes talking about relationship between subspaces and equations that define them exceedingly difficult. Better late than never, so here it comes.

Let V be a vector space over a field \mathbb{F}. Denote by V^* the set of linear functions V\to \mathbb{F}.

Examples
Let V=C[a,b], the space of continuous functions on [a,b]. Then the function \int: V\to V given by f\mapsto \int_a^b f(x) dx is linear on V.

Let V=\mathbb{R}[x] be the vector space of polynomials with real coefficients.
Then the function V\to V given by f\mapsto \frac{df}{dx}(0) is linear on V.

Note that as f\in V^* is linear, one has f(\alpha v)=\alpha f(v) for any v\in V, \alpha\in \mathbb{F}. Thus we have m_\alpha:V^*\to V^* defined by m_\alpha(f)(v)=f(\alpha v) so that m_\alpha(m_\beta(f))=(m_\alpha m_\beta)(f). To simplify notation, we will write \alpha f instead m_\alpha(f). As well, we can define (f+g)(v)=f(v)+g(v) for any f,g\in V^*, and more generally, (\alpha f+\beta g)(v)=\alpha f(v)+\beta g(v). And there is the zero function 0(v)=0 for any v\in V. Thus we have all the ingredients of a vector space, as can be easily checked.

V^* is a vector space over \mathbb{F}. It is called the dual space of V.

So far, we haven’t used the linearity of our functions at all (we actually did not need the fact that \alpha f(v)=f(\alpha v)). Indeed, any closed under addition and multiplication set of functions V\to V would form a vector space.
What makes the dual space so special is that to define f\in V^* it suffices to define f(e_i) on a basis \{e_i\} of V. Indeed, f(\sum_i \alpha_i e_i)=\sum_i \alpha_i f(e_i), so we can compute f(v) for any v=\sum_i \alpha_i e_i, once we know the f(e_i)’s.

Thus for a finite-dimensional vector space V one sees a (dependent upon the choice of a basis in V) bijection between V and V^*. This bijection, that is even an isomorphism of vector spaces, is defined by the dual basis of V^* given by coordinate functions x_i=\epsilon_i(x), where x_i’s are the coefficients of x\in V is the decomposition of x in the basis \{ e_i\}.

Finite-dimensionality is crucial here. E.g. let us consider the vector space of polynomials \mathbb{Z}[x]. It is a countable space: one can view it as the set of infinite 0-1 strings, with only finitely many 1’s occurring in each string. On the other hand, V^* can be viewed as the set of all the infinite 0-1 strings, which is uncountable, so there cannot be a bijection between V and V^*.

Given v\in V, one can define a function f_v:V^*\to \mathbb{F}, as follows: f_v(g):=g(v). It is linear, as f_v(\alpha g+\beta h)=\alpha g(v)+\beta h(v)=\alpha f_v(g)+\beta f_v(h). Here we do not see any dependence on the choice of a basis in V, and we have

The vector space V^{**} of linear functions on V^* is (canonically) isomorphic to V, via the mapping v\mapsto f_v.

Indeed, we see immediately that f_{\alpha v+\beta w}=\alpha f_v+\beta f_w, and so we need only to check that this mapping is bijective. Let \{e_i\} be a basis in V and \{\epsilon_i\} its dual basis in V^*. Then f_{e_i}(\epsilon_j)=1 if i=j and 0 otherwise. Thus \{ f_{e_i}\} is the basis of V^{**}, which is dual to the basis \{\epsilon_i\} of V^*, and the mapping v\mapsto f_v sends the vector with coordinates v_i to the vector with the same coordinates in
the basis \{ f_{e_i}\} of V^{**}. Hence the latter is bijective.

In view of the latter, we can identify V with V^{**}, and write v(g) instead f_v(g). The set of g\in V^* such that v(g)=0 is a subspace, called annihilator of v, of dimension n-1=dim(V)-1. More generally, the following holds.

Let U be a subspace of V, and U^0:=\{g\in V^*\mid g(u)=0\text{ for all } u\in U\}. Then the annihilator U^0 of U is a subspace of V^* of dimension dim(V)-dim(U).

Indeed, we can choose a basis \{e_i\} in V so that \{e_1,\dots,e_{k} is a basis of U, where dim(U)=k. Then we have the dual basis \{\epsilon_i\} of V^*, and U^0 is the subspace with the basis \{e_{k+1},\dots,e_n\}.

In view of this, each U can be obtained as the set of solutions of a system of homogeneous linear equations g(u)=0, for g\in U^0, of rank dim(V)-dim(U).

Dual spaces and annihilators under a basis change
Let X\in GL_n(\mathbb{F}) be a linear transformation of V, and U a subspace of V. Then X(U)=\{ Xu\mid u\in U\} is a subspace. How can one look at g(U^0)? By writing out u=\sum_i u_i e_i in a basis \{e_i\}, for any g=\sum_i g_i\epsilon_i\in U^0 in the dual basis \{\epsilon_i\}, we get equation \sum_i g_i u_i =0. Thus, considering X as a matrix, we get g^T YX u=0, where Y denotes the action of X on V^*. It follows that YX=1_{GL_n}, i.e. Y=X^{-1}. We have, considering that Y acts on V^* by right multiplication, and not by left ones, to take the transpose, too.

X\in GL_n(\mathbb{F}) acts on V^* as (X^{-1})^T.

An example.
Let V=\mathbb{F}^3. We work in the standard basis \{e_1,e_2,e_3\} of V. Then the dual basis of V^* is \{\epsilon_1,\epsilon_2,\epsilon_3\}, so that \epsilon_i((u_1,u_2,u_3)^T)=u_i.
Let G be the group of matrices G=\left\{ \begin{pmatrix} 1&x&y\\ 0&z&u\\ 0&t&w \end{pmatrix} \mid x,y,z,u,t,w\in\mathbb{F} \right\}<GL_3(\mathbb{F}). It fixes, in its left action on V by multiplication, the vector e_1=(100)^T.. Let U be the 1-dimensional subspace of V generated by e_1. Then U^0 is generated by \epsilon_2 and \epsilon_3. The group G preserves U^0, in its action on V^*. As U_0 is 2-dimensional, there should be a nontrivial kernel in this action, and indeed, it consists of the elements of the form \begin{pmatrix} 1&x&y\\ 0&1&0\\ 0&0&1 \end{pmatrix}.

A particularly simple case is \mathbb{F} = \mathbb{Z}_2. Then G is isomorphic to S_4, the symmetric group on 4 letters, as can be seen in its action on the 4 elements of V^* outside U^0. On the other hand, it acts on the 3 nonzero elements of U^0 as S_3.

Orbit-counting Lemma

31 March, 2009 in undergrad maths | Tags: , , , | Leave a comment

Excercises in algebra

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 in undergrad maths | Tags: , , | Leave a comment

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 in undergrad maths | Tags: , , , | Leave a comment

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 in undergrad maths | Tags: , , | Leave a comment

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<n, 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<GL_n(\mathbb{F}) 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<GL_2(\mathbb{C}) 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.)