Localization, Hurwitz Numbers and the Witten Conjecture

NLOS Identification and Mitigation for Localization Based on UWB Experimental Data Stefano Maran`o,Student Member,IEEE,Wesley M.Gifford,Student Member,IEEE,Henk Wymeersch,Member,IEEE,Moe Z.Win,Fellow,IEEEAbstract—Sensor networks can benefit greatly from location-awareness,since it allows information gathered by the sensors to be tied to their physical locations.Ultra-wide bandwidth(UWB) transmission is a promising technology for location-aware sensor networks,due to its power efficiency,fine delay resolution,and robust operation in harsh environments.However,the presence of walls and other obstacles presents a significant challenge in terms of localization,as they can result in positively biased distance estimates.We have performed an extensive indoor measurement campaign with FCC-compliant UWB radios to quantify the effect of non-line-of-sight(NLOS)propagation.From these channel pulse responses,we extract features that are representative of the propagation conditions.We then develop classification and regression algorithms based on machine learning techniques, which are capable of:(i)assessing whether a signal was trans-mitted in LOS or NLOS conditions;and(ii)reducing ranging error caused by NLOS conditions.We evaluate the resulting performance through Monte Carlo simulations and compare with existing techniques.In contrast to common probabilistic approaches that require statistical models of the features,the proposed optimization-based approach is more robust against modeling errors.Index Terms—Localization,UWB,NLOS Identification,NLOS Mitigation,Support Vector Machine.I.I NTRODUCTIONL OCATION-AW ARENESS is fast becoming an essential aspect of wireless sensor networks and will enable a myr-iad of applications,in both the commercial and the military sectors[1],[2].Ultra-wide bandwidth(UWB)transmission [3]–[8]provides robust signaling[8],[9],as well as through-wall propagation and high-resolution ranging capabilities[10], [11].Therefore,UWB represents a promising technology for localization applications in harsh environments and accuracy-critical applications[10]–[15].In practical scenarios,however, a number of challenges remain before UWB localization and communication can be deployed.These include signal Manuscript received15May2009;revised15February2010.This research was supported,in part,by the National Science Foundation under grant ECCS-0901034,the Office of Naval Research Presidential Early Career Award for Scientists and Engineers(PECASE)N00014-09-1-0435,the Defense University Research Instrumentation Program under grant N00014-08-1-0826, and the MIT Institute for Soldier Nanotechnologies.S.Maran`o was with Laboratory for Information and Decision Systems (LIDS),Massachusetts Institute of Technology(MIT),and is now with the Swiss Seismological Service,ETH Z¨u rich,Z¨u rich,Switzerland(e-mail: stefano.marano@sed.ethz.ch).H.Wymeersch was with LIDS,MIT,and is now with Chalmers University of Technology,G¨o teborg,Sweden(e-mail:henkw@chalmers.se).Wesley M.Gifford and Moe Z.Win are with LIDS,MIT,Cambridge,MA 02139USA(e-mail:wgifford@,moewin@).Digital Object Identifier10.1109/JSAC.2010.100907.acquisition[16],multi-user interference[17],[18],multipath effects[19],[20],and non-line-of-sight(NLOS)propagation [10],[11].The latter issue is especially critical[10]–[15]for high-resolution localization systems,since NLOS propagation introduces positive biases in distance estimation algorithms, thus seriously affecting the localization performance.Typical harsh environments such as enclosed areas,urban canyons, or under tree canopies inherently have a high occurrence of NLOS situations.It is therefore critical to understand the impact of NLOS conditions on localization systems and to develop techniques that mitigate their effects.There are several ways to deal with ranging bias in NLOS conditions,which we classify as identification and mitigation. NLOS identification attempts to distinguish between LOS and NLOS conditions,and is commonly based on range estimates[21]–[23]or on the channel pulse response(CPR) [24],[25].Recent,detailed overviews of NLOS identification techniques can be found in[22],[26].NLOS mitigation goes beyond identification and attempts to counter the positive bias introduced in NLOS signals.Several techniques[27]–[31]rely on a number of redundant range estimates,both LOS and NLOS,in order to reduce the impact of NLOS range estimates on the estimated agent position.In[32]–[34]the geometry of the environment is explicitly taken into account to cope with NLOS situations.Other approaches,such as[35],attempt to detect the earliest path in the CPR in order to better estimate the TOA in NLOS prehensive overviews of NLOS mitigation techniques can be found in[26],[36]. The main drawbacks of existing NLOS identification and mitigation techniques are:(i)loss of information due to the direct use of ranges instead of the CPRs;(ii)latency incurred during the collection of range estimates to establish a history; and(iii)difficulty in determining the joint probability distribu-tions of the features required by many statistical approaches. In this paper,we consider an optimization-based approach. In particular,we propose the use of non-parametric ma-chine learning techniques to perform NLOS identification and NLOS mitigation.Hence,they do not require a statistical characterization of LOS and NLOS channels,and can perform identification and mitigation under a common framework.The main contributions of this paper are as follows:•characterization of differences in the CPRs under LOS and NLOS conditions based on an extensive indoor mea-surement campaign with FCC-compliant UWB radios;•determination of novel features extracted from the CPR that capture the salient properties in LOS and NLOS conditions;0733-8716/10/$25.00c 2010IEEE•demonstration that a support vector machine (SVM)clas-si fier can be used to distinguish between LOS and NLOS conditions,without the need for statistical modeling of the features under either condition;and•development of SVM regressor-based techniques to mit-igate the ranging bias in NLOS situations,again without the need for statistical modeling of the features under either condition.The remainder of the paper is organized as follows.In Section II,we introduce the system model,problem statement,and describe the effect of NLOS conditions on ranging.In Section III,we describe the equipment and methodologies of the LOS/NLOS measurement campaign and its contribu-tion to this work.The proposed techniques for identi fication and mitigation are described in Section IV,while different strategies for incorporating the proposed techniques within any localization system are discussed in Section V.Numerical performance results are provided in Section VI,and we draw our conclusions in Section VII.II.P ROBLEM S TATEMENT AND S YSTEM M ODEL In this section,we describe the ranging and localization algorithm,and demonstrate the need for NLOS identi fication and mitigation.A.Single-node LocalizationA network consists of two types of nodes:anchors are nodes with known positions,while agents are nodes with unknown positions.For notational convenience,we consider the point of view of a single agent,with unknown position p ,surrounded by N b anchors,with positions,p i ,i =1,...,N b .The distance between the agent and anchor i is d i = p −p i .The agent estimates the distance between itself and the anchors,using a ranging protocol.We denote the estimateddistance between the agent and anchor i by ˆdi ,the ranging error by εi =ˆdi −d i ,the estimate of the ranging error by ˆεi ,the channel condition between the agent and anchor i by λi ∈{LOS ,NLOS },and the estimate of the channelcondition by ˆλi .The mitigated distance estimate of d i is ˆd m i=ˆd i −ˆεi .The residual ranging error after mitigation is de fined as εm i =ˆd m i −d i .Given a set of at least three distance estimates,the agent will then determine its position.While there are numerous positioning algorithms,we focus on the least squares (LS)criterion,due to its simplicity and because it makes no assumptions regarding ranging errors.The agent can infer its position by minimizing the LS cost functionˆp=arg min p(p i ,ˆdi )∈Sˆd i − p −p i 2.(1)Note that we have introduced the concept of the set of useful neighbors S ,consisting of couplesp i ,ˆdi .The optimization problem (1)can be solved numerically using steepest descent.B.Sources of ErrorThe localization algorithm will lead to erroneous results when the ranging errors are large.In practice the estimated distances are not equal to the true distances,because of a number of effects including thermal noise,multipath propa-gation,interference,and ranging algorithm inaccuracies.Ad-ditionally,the direct path between requester and responder may be obstructed,leading to NLOS propagation.In NLOS conditions,the direct path is either attenuated due to through-material propagation,or completely blocked.In the former case,the distance estimates will be positively biased due to the reduced propagation speed (i.e.,less than the expected speed of light,c ).In the latter case the distance estimate is also positively biased,as it corresponds to a re flected path.These bias effects can be accounted for in either the ranging or localization phase.In the remainder of this paper,we focus on techniques that identify and mitigate the effects of NLOS signals during the ranging phase.In NLOS identi fication,the terms in (1)corre-sponding to NLOS distance estimates are omitted.In NLOS mitigation,the distance estimates corresponding to NLOS signals are corrected for improved accuracy.The localization algorithm can then adopt different strategies,depending on the quality and the quantity of available range estimates.III.E XPERIMENTAL A CTIVITIESThis section describes the UWB LOS/NLOS measurement campaign performed at the Massachusetts Institute of Tech-nology by the Wireless Communication and Network Sciences Laboratory during Fall 2007.A.OverviewThe aim of this experimental effort is to build a large database containing a variety of propagation conditions in the indoor of fice environment.The measurements were made using two FCC-compliant UWB radios.These radios repre-sent off-the-shelf transceivers and therefore an appropriate benchmark for developing techniques using currently available technology.The primary focus is to characterize the effects of obstructions.Thus,measurement positions (see Fig.1)were chosen such that half of the collected waveforms were cap-tured in NLOS conditions.The distance between transmitter and receiver varies widely,from roughly 0.6m up to 18m,to capture a variety of operating conditions.Several of fices,hallways,one laboratory,and a large lobby constitute the physical setting of this campaign.While the campaign was conducted in one particular indoor of fice envi-ronment,because of the large number of measurements and the variety of propagation scenarios encountered,we expect that our results are applicable in other of fice environments.The physical arrangement of the campaign is depicted in Fig.1.In each measurement location,the received waveform and the associated range estimate,as well as the actual distance are recorded.The waveforms are then post-processed in order to reduce dependencies on the speci fic algorithm and hardware,e.g.,on the leading edge detection (LED)algorithm embedded in the radios.Fig.1.Measurements were taken in clusters over several different rooms and hallways to capture different propagation conditions.B.Experimental ApparatusThe commercially-available radios used during the data collection process are capable of performing communications and ranging using UWB signals.The radio complies with the emission limit set forth by the FCC[37].Specifically, the10dB bandwidth spans from3.1GHz to6.3GHz.The radio is equipped with a bottom fed planar elliptical antenna. This type of dipole antenna is reported to be well matched and radiation efficient.Most importantly,it is omni-directional and thus suited for ad-hoc networks with arbitrary azimuthal orientation[38].Each radio is mounted on the top of a plastic cart at a height of90cm above the ground.The radios perform a round-trip time-of-arrival(RTOA)ranging protocol1and are capable of capturing waveforms while performing the ranging procedure.Each waveform r(t)captured at the receiving radio is sampled at41.3ps over an observation window of190ns.C.Measurement ArrangementMeasurements were taken at more than one hundred points in the considered area.A map,depicting the topological organization of the clusters within the building,is shown 1RTOA allows ranging between two radios without a common time reference;and thus alleviates the need for networksynchronization.Fig.2.The measurement setup for collecting waveforms between D675CA and H6around the corner of the WCNS Laboratory.in Fig.1,and a typical measurement scenario is shown in Fig.2.Points are placed randomly,but are restricted to areas which are accessible by the carts.The measurement points are grouped into non-overlapping clusters,i.e.,each point only belongs to a single cluster.Typically,a cluster corresponds to a room or a region of a hallway.Within each cluster,measurements between every possible pair of points were captured.When two clusters were within transmission range, every inter-cluster measurement was collected as well.Overall, more than one thousand unique point-to-point measurements were performed.For each pair of points,several received waveforms and distance estimates are recorded,along with the actual distance.During each measurement the radios remain stationary and care is taken to limit movement of other objects in the nearby surroundings.D.DatabaseUsing the measurements collected during the measurement phase,a database was created and used to develop and evaluate the proposed identification and mitigation techniques. It includes1024measurements consisting of512waveforms captured in the LOS condition and512waveforms captured in the NLOS condition.The term LOS is used to denote the existence of a visual path between transmitter and receiver,i.e., a measurement is labeled as LOS when the straight line be-tween the transmitting and receiving antenna is unobstructed. The ranging estimate was obtained by an RTOA algorithm embedded on the radio.The actual position of the radio during each measurement was manually recorded,and the ranging error was calculated with the aid of computer-aided design(CAD)software.The collected waveforms were then processed to align thefirst path in the delay domain using a simple threshold-based method.The alignment process creates a time reference independent of the LED algorithm embedded on the radio.IV.NLOS I DENTIFICATION AND M ITIGATIONThe collected measurement data illustrates that NLOS prop-agation conditions significantly impact ranging performance. For example,Fig.3shows the empirical CDFs of the ranging error over the ensemble of all measurements collected under the two different channel conditions.In LOS conditions a ranging error below one meter occurs in more than95%of the measurements.On the other hand,in NLOS conditions a ranging error below one meter occurs in less than30%of the measurements.Clearly,LOS and NLOS range estimates have very dif-ferent characteristics.In this section,we develop techniques to distinguish between LOS and NLOS situations,and to mitigate the positive biases present in NLOS range estimates. Our techniques are non-parametric,and rely on least-squares support-vector machines(LS-SVM)[39],[40].Wefirst de-scribe the features for distinguishing LOS and NLOS situa-tions,followed by a brief introduction to LS-SVM.We then describe how LS-SVM can be used for NLOS identification and mitigation in localization applications,without needing to determine parametric joint distributions of the features for both the LOS and NLOS conditions.A.Feature Selection for NLOS ClassificationWe have extracted a number of features,which we expect to capture the salient differences between LOS and NLOS signals,from every received waveform r(t).These featuresFig.3.CDF of the ranging error for the LOS and NLOS condition. were selected based on the following observations:(i)in NLOS conditions,signals are considerably more attenuated and have smaller energy and amplitude due to reflections or obstructions;(ii)in LOS conditions,the strongest path of the signal typically corresponds to thefirst path,while in NLOS conditions weak components typically precede the strongest path,resulting in a longer rise time;and(iii)the root-mean-square(RMS)delay spread,which captures the temporal dispersion of the signal’s energy,is larger for NLOS signals. Fig.4depicts two waveforms received in the LOS and NLOS condition supporting our observations.We also include some features that have been presented in the literature.Taking these considerations into account,the features we will consider are as follows:1)Energy of the received signal:E r=+∞−∞|r(t)|2dt(2) 2)Maximum amplitude of the received signal:r max=maxt|r(t)|(3) 3)Rise time:t rise=t H−t L(4) wheret L=min{t:|r(t)|≥ασn}t H=min{t:|r(t)|≥βr max},andσn is the standard deviation of the thermal noise.The values ofα>0and0<β≤1are chosen empirically in order to capture the rise time;in our case, we usedα=6andβ=0.6.4)Mean excess delay:τMED=+∞−∞tψ(t)dt(5) whereψ(t)=|r(t)|2/E r.Fig.4.In some situations there is a clear difference between LOS(upper waveform)and NLOS(lower waveform)signals.5)RMS delay spread:τRMS=+∞−∞(t−τMED)2ψ(t)dt(6)6)Kurtosis:κ=1σ4|r|TT|r(t)|−μ|r|4dt(7)whereμ|r|=1TT|r(t)|dtσ2|r|=1TT|r(t)|−μ|r|2dt.B.Least Squares SVMThe SVM is a supervised learning technique used both for classification and regression problems[41].It represents one of the most widely used classification techniques because of its robustness,its rigorous underpinning,the fact that it requires few user-defined parameters,and its superior performance compared to other techniques such as neural networks.LS-SVM is a low-complexity variation of the standard SVM, which has been applied successfully to classification and regression problems[39],[40].1)Classification:A linear classifier is a function R n→{−1,+1}of the forml(x)=sign[y(x)](8) withy(x)=w Tϕ(x)+b(9) whereϕ(·)is a predetermined function,and w and b are unknown parameters of the classifier.These parameters are de-termined based on the training set{x k,l k}N k=1,where x k∈R n and l k∈{−1,+1}are the inputs and labels,respectively.In the case where the two classes can be separated the SVM determines the separating hyperplane which maximizes the margin between the two classes.2Typically,most practical problems involve classes which are not separable.In this case,the SVM classifier is obtained by solving the following optimization problem:arg minw,b,ξ12w 2+γNk=1ξk(10)s.t.l k y(x k)≥1−ξk,∀k(11)ξk≥0,∀k,(12) where theξk are slack variables that allow the SVM to tolerate misclassifications andγcontrols the trade-off between minimizing training errors and model complexity.It can be shown that the Lagrangian dual is a quadratic program(QP) [40,eqn.2.26].To further simplify the problem,the LS-SVM replaces the inequality(11)by an equality:arg minw,b,e12w 2+γ12Nk=1e2k(13)s.t.l k y(x k)=1−e k,∀k.(14) Now,the Lagrangian dual is a linear program(LP)[40,eqn.3.5],which can be solved efficiently by standard optimization toolboxes.The resulting classifier can be written asl(x)=signNk=1αk l k K(x,x k)+b,(15)whereαk,the Lagrange multipliers,and b are found from the solution of the Lagrangian dual.The function K(x k,x l)=ϕ(x k)Tϕ(x l)is known as the kernel which enables the SVM to perform nonlinear classification.2)Regression:A linear regressor is a function R n→R of the formy(x)=w Tϕ(x)+b(16) whereϕ(·)is a predetermined function,and w and b are unknown parameters of the regressor.These parameters are determined based on the training set{x k,y k}N k=1,where x k∈R n and y k∈R are the inputs and outputs,respectively. The LS-SVM regressor is obtained by solving the following optimization problem:arg minw,b,e12w 2+γ12e 2(17)s.t.y k=y(x k)+e k,∀k,(18) whereγcontrols the trade-off between minimizing training errors and model complexity.Again,the Lagrangian dual is an LP[40,eqn.3.32],whose solution results in the following LS-SVM regressory(x)=Nk=1αk K(x,x k)+b.(19)2The margin is given by1/ w ,and is defined as the smallest distance between the decision boundary w Tϕ(x)+b=0and any of the training examplesϕ(x k).C.LS-SVM for NLOS Identi fication and MitigationWe now apply the non-parametric LS-SVM classi fier to NLOS identi fication,and the LS-SVM regressor to NLOS mitigation.We use 10-fold cross-validation 3to assess the performance of our features and the SVM.Not only are we interested in the performance of LS-SVM for certain features,but we are also interested in which subsets of the available features give the best performance.1)Classi fication:To distinguish between LOS and NLOS signals,we train an LS-SVM classi fier with inputs x k and corresponding labels l k =+1when λk =LOS and l k =−1when λk =NLOS .The input x k is composed of a subset of the features given in Section IV-A.A trade-off between classi fier complexity and performance can be made by using a different size feature subset.2)Regression:To mitigate the effect of NLOS propagation,we train an LS-SVM regressor with inputs x k and corre-sponding outputs y k =εk associated with the NLOS signals.Similar to the classi fication case,x k is composed of a subset of features,selected from those given in Section IV-A and therange estimate ˆdk .Again,the performance achieved by the regressor will depend on the size of the feature subset and the combination of features used.V.L OCALIZATION S TRATEGIESBased on the LS-SVM classi fier and regressor,we can develop the following localization strategies:(i)localization via identi fication ,where only classi fication is employed;(ii)localization via identi fication and mitigation ,where the re-ceived waveform is first classi fied and error mitigation is performed only on the range estimates from those signals identi fied as NLOS;and (iii)a hybrid approach which discards mitigated NLOS range estimates when a suf ficient number of LOS range estimates are present.A.Strategy 1:StandardIn the standard strategy,all the range estimates ˆdi from neighboring anchor nodes are used by the LS algorithm (1)for localization.In other words,S S =p i ,ˆd i :1≤i ≤N b .(20)B.Strategy 2:Identi ficationIn the second strategy,waveforms are classi fied as LOS or NLOS using the LS-SVM classi fier.Range estimates are used by the localization algorithm only if the associated waveform was classi fied as LOS,while range estimates from waveforms classi fied as NLOS are discarded:S I = p i ,ˆd i:1≤i ≤N b ,ˆλi =LOS .(21)Whenever the cardinality of S I is less than three,the agent isunable to localize.4In this case,we set the localization error to +∞.3InK -fold cross-validation,the dataset is randomly partitioned into K parts of approximately equal size,each containing 50%LOS and 50%NLOS waveforms.The SVM is trained on K −1parts and the performance is evaluated on the remaining part.This is done a total of K times,using each of the K parts exactly once for evaluation and K −1times for training.4Note that three is the minimum number of anchor nodes needed to localize in two-dimensions.TABLE IF ALSE ALARM PROBABILITY (P F ),MISSED DETECTION PROBABILITY (P M ),AND OVERALL ERROR PROBABILITY (P E )FOR DIFFERENT NLOSIDENTIFICATION TECHNIQUES .T HE SET F i IDENOTES THE SET OF i FEATURES WITH THE SMALLEST P E USING THE LS-SVM TECHNIQUE .Identi fication Technique P F P M P E Parametric technique given in [42]0.1840.1430.164LS-SVM using features from [42]0.1290.1520.141F 1I ={r max }0.1370.1230.130F 2I ={r max ,t rise }0.0920.1090.100F 3I ={E r ,t rise ,κ}0.0820.0900.086F 4I={E r ,r max ,t rise ,κ}0.0820.0900.086F 5I ={E r ,r max ,t rise ,τMED ,κ}0.0860.0900.088F 6I={E r ,r max ,t rise ,τMED ,τRMS ,κ}0.0920.0900.091C.Strategy 3:Identi fication and MitigationThis strategy is an extension to the previous strategy,wherethe received waveform is first classi fied as LOS or NLOS,and then the mitigation algorithm is applied to those signals with ˆλi =NLOS .For this case S IM =S I ∪S M ,where S M = p i ,ˆd m i :1≤i ≤N b ,ˆλi =NLOS ,(22)and the mitigated range estimate ˆd m iis described in Sec.II.This approach is motivated by the observation that mitigation is not necessary for range estimates associated with LOS waveforms,since their accuracy is suf ficiently high.D.Strategy 4:Hybrid Identi fication and Mitigation In the hybrid approach,range estimates are mitigated as in the previous strategy.However,mitigated range estimates are only used when less than three LOS anchors are available:5S H =S I if |S I |≥3S IMotherwise(23)This approach is motivated by the fact that mitigated range es-timates are often still less accurate than LOS range estimates.Hence,only LOS range estimates should be used,unless there is an insuf ficient number of them to make an unambiguous location estimate.VI.P ERFORMANCE E VALUATION AND D ISCUSSION In this section,we quantify the performance of the LS-SVM classi fier and regressor from Section IV,as well as the four localization strategies from Section V.We will first consider identi fication,then mitigation,and finally localization.For every technique,we will provide the relevant performance measures as well as the quantitative details of how the results were obtained.5Inpractice the angular separation of the anchors should be suf ficiently large to obtain an accurate estimate.If this is not the case,more than three anchors may be needed.TABLE IIM EAN AND RMS VALUES OF RRE FOR LS-SVM REGRESSION -BASEDMITIGATION .T HE SET F i MDENOTES THE SET OF i FEATURES WHICH ACHIEVES THE MINIMUM RMS RRE.Mitigation Technique with LS-SVM RegressionMean [m]RMS [m ]No Mitigation2.63223.589F 1M={ˆd}-0.0004 1.718F 2M ={κ,ˆd }-0.0042 1.572F 3M ={t rise ,κ,ˆd }0.0005 1.457F 4M ={t rise ,τMED ,κ,ˆd }0.0029 1.433F 5M={E r ,t rise ,τMED ,κ,ˆd }0.0131 1.425F 6M ={E r ,t rise ,τMED ,τRMS ,κ,ˆd }0.0181 1.419F 7M={E r ,r max ,t rise ,τMED ,τRMS ,κ,ˆd}0.01801.425A.LOS/NLOS Identi ficationIdenti fication results,showing the performance 6for eachfeature set size,are given in Table I.For the sake of compari-son,we also evaluate the performance of the parametric identi-fication technique from [42],which relies on three features:the mean excess delay,the RMS delay spread,and the kurtosis of the waveform.For fair comparison,these features are extracted from our database.The performance is measured in terms of the misclassi fication rate:P E =(P F +P M )/2,where P F is the false alarm probability (i.e.,deciding NLOS when the signal was LOS),and P M is the missed detection probability (i.e.,deciding LOS when the signal was NLOS).The table only lists the feature sets which achieved the minimum misclassi fication rate for each feature set size.We observe that the LS-SVM,using the three features from [42],reduces the false alarm probability compared to the parametric technique.It was shown in [43]that the features from [42],in fact,give rise to the worst performance among all possible sets of size three considered ing the features from Section IV-A and considering all feature set sizes,our results indicate that the feature set of size three,F 3I ={E r ,t rise ,κ},provides the best pared to the parametric technique,this set reduces both the false alarm and missed detection probabilities and achieves a correct classi fication rate of above 91%.In particular,among all feature sets of size three (results not shown,see [43]),there are seven sets that yield a P E of roughly 10%.All seven of these sets have t rise in common,while four have r max in common,indicating that these two features play an important role.Their importance is also corroborated by the presence of r max and t rise in the selected sets listed in Table I.For the remainder of this paper we will use the feature set F 3I for identi fication.B.NLOS MitigationMitigation results,showing the performance 7for different feature set sizes are given in Table II.The performance is measured in terms of the root mean square residual ranging6Wehave used an RBF kernel of the form K (x ,x k )=exp “− x −x k 2”and set γ=0.1.Features are first converted to the log domain in order to reduce the dynamic range.7Here we used a kernel given by K (x ,x k )=exp “− x −x k2/162”and set γ=10.Again,features are first converted to the log domain.Fig.5.CDF of the ranging error for the NLOS case,before and after mitigation.error (RMS RRE): 1/N N i =1(εm i )2.A detailed analysis ofthe experimental data indicates that large range estimates are likely to exhibit large positive ranging errors.This means that ˆditself is a useful feature,as con firmed by the presence of ˆdin all of the best feature sets listed in the table.Increasing the feature set size can further improve the RMS RRE.Thefeature set of size six,F 6M={E r ,t rise ,τMED ,τRMS ,κ,ˆd },offers the best performance.For the remainder of this paper,we will use this feature set for NLOS mitigation.Fig.5shows the CDF of the ranging error before and after mitigation using this feature set.We observe that without mitigation around 30%of the NLOS waveforms achieved an accuracy of less than one meter (|ε|<1).Whereas,after the mitigation process,60%of the cases have an accuracy less than 1m.C.Localization Performance1)Simulation Setup:We evaluate the localization perfor-mance for fixed number of anchors (N b )and a varying prob-ability of NLOS condition 0≤P NLOS ≤1.We place an agent at a position p =(0,0).For every anchor i (1≤i ≤N b ),we draw a waveform from the database:with probability P NLOS we draw from the NLOS database and with probability 1−P NLOS from the LOS database.The true distance d i corre-sponding to that waveform is then used to place the i th anchor at position p i =(d i sin(2π(i −1)/N b ),d i cos(2π(i −1)/N b )),while the estimated distance ˆdi is provided to the agent.This creates a scenario where the anchors are located at different distances from the agent with equal angular spacing.The agent estimates its position,based on a set of useful neighbors S ,using the LS algorithm from Section II.The arithmetic mean 8of the anchor positions is used as the initial estimate of the agent’s position.2)Performance Measure:To capture the accuracy and availability of localization,we introduce the notion of outage probability .For a certain scenario (N b and P NLOS )and a8Thisis a fair setting for the simulation,as all the strategies are initialized inthe same way.Indeed,despite the identical initialization,strategies converge to signi ficantly different final position estimates.In addition,we note that such an initial position estimate is always available to the agent.。

Course311:Michaelmas Term1999Part II:Topics in Group TheoryD.R.WilkinsCopyright c David R.Wilkins1997Contents2Topics in Group Theory22.1Groups (2)2.2Examples of Groups (3)2.3Cayley Tables (4)2.4Elementary Properties of Groups (5)2.5The General Associative Law (6)2.6Subgroups (8)2.7Cyclic Groups (9)2.8Cosets and Lagrange’s Theorem (11)2.9Normal Subgroups and Quotient Groups (12)2.10Homomorphisms (16)2.11The Isomorphism Theorems (18)2.12Direct products of groups (19)2.13Cayley’s Theorem (20)2.14Group Actions,Orbits and Stabilizers (21)2.15Conjugacy (21)2.16Permutations and the Symmetric Groups (22)2.17The Alternating Groups (26)2.18Normal Subgroups of the Symmetric Groups (29)2.19Finitely Generated Abelian Groups (30)2.20The Class Equation of a Finite Group (33)2.21Cauchy’s Theorem (34)2.22The Structure of p-Groups (34)2.23The Sylow Theorems (35)2.24Solvable Groups (37)12Topics in Group Theory2.1GroupsA binary operation∗on a set G associates to elements x and y of G a third element x∗y of G.For example,addition and multiplication are binary operations of the set of all integers.Definition A group G consists of a set G together with a binary operation∗for which the following properties are satisfied:•(x∗y)∗z=x∗(y∗z)for all elements x,y,and z of G(the Associative Law);•there exists an element e of G(known as the identity element of G) such that e∗x=x=x∗e,for all elements x of G;•for each element x of G there exists an element x of G(known as the inverse of x)such that x∗x =e=x ∗x(where e is the identity element of G).The order|G|of afinite group G is the number of elements of G.A group G is Abelian(or commutative)if x∗y=y∗x for all elements x and y of G.One usually adopts multiplicative notation for groups,where the product x∗y of two elements x and y of a group G is denoted by xy.The inverse of an element x of G is then denoted by x−1.The identity element is usually denoted by e(or by e G when it is necessary to specify explicitly the group to which it belongs).Sometimes the identity element is denoted by1.Thus, when multiplicative notation is adopted,the group axioms are written as follows:-•(xy)z=x(yz)for all elements x,y,and z of G(the Associative Law);•there exists an element e of G(known as the identity element of G) such that ex=x=xe,for all elements x of G;•for each element x of G there exists an element x−1of G(known as the inverse of x)such that xx−1=e=x−1x(where e is the identity element of G).2The group G is said to be Abelian(or commutative)if xy=yx for all elements x and y of G.It is sometimes convenient or customary to use additive notation for cer-tain groups.Here the group operation is denoted by+,the identity element of the group is denoted by0,the inverse of an element x of the group is denoted by−x.By convention,additive notation is only used for Abelian groups.When expressed in additive notation the axioms for a Abelian group are as follows:•x+y=y+x for all elements x and y of G(the Commutative Law);•(x+y)+z=x+(y+z)for all elements x,y,and z of G(the Associative Law);•there exists an element0of G(known as the identity element or zero element of G)such that0+x=x=x+0,for all elements x of G;•for each element x of G there exists an element−x of G(known as the inverse of x)such that x+(−x)=0=(−x)+x(where0is the identity element of G).We shall usually employ multiplicative notation when discussing general properties of groups.Additive notation will be employed for certain groups (such as the set of integers with the operation of addition)where this notation is the natural one to use.2.2Examples of GroupsThe sets of integers,rational numbers,real numbers and complex numbers are Abelian groups,where the group operation is the operation of addition.The sets of non-zero rational numbers,non-zero real numbers and non-zero complex numbers are also Abelian groups,where the group operation is the operation of multiplication.For each positive integer m the set Z m of congruence classes of integers modulo m is a group,where the group operation is addition of congruence classes.For each positive integer m the set Z∗m of congruence classes modulo m ofintegers coprime to m is a group,where the group operation is multiplication of congruence classes.In particular,for each prime number p the set Z∗p of congruence classesmodulo p of integers not divisible by p is a group,where the group operation is multiplication of congruence classes.3For each positive integer n the set of all nonsingular n×n matrices is a group,where the group operation is matrix multiplication.These groups are not Abelian when n≥2.The set of all transformations of the plane that are of the form(x,y)→(ax+by,cx+dy)with ad−bc=0is a group with respect to the operation of composition of transformations.This group includes all rotations about the origin,and all reflections in lines passing through the origin.It is not Abelian.Consider a regular n-sided polygon centered at the origin.The symme-tries of this polygon(i.e.,length-and angle-preserving transformations of the plane that map this polygon onto itself)are rotations about the origin through an integer multiple of2π/n radians,and reflections in the n axes of symmetry of the polygon.The symmetries of the polygon constitute a group of order2n.This group is referred to as the dihedral group of order2n.The symmetries of a rectangle that is not a square constitute a group of order4.This group consists of the identity transformation,reflection in the axis of symmetry joining the midpoints of the two shorter sides,reflection in the axis of symmetry joining the two longer sides,and rotation though an angle ofπradians(180◦).If I denotes the identity transformation,A and B denote the reflections in the two axes of symmetry,and C denotes the rotation throughπradians then A2=B2=C2=I,AB=BA=C, AC=CA=B and BC=CB=A.This group is Abelian:it is often referred to as the Klein4-group(or,in German,Kleinsche Viergruppe).The symmetries of a regular tetrahedron in3-dimensional space constitute a group.Any permutation of the vertices of the tetrahedron can be effected by an appropriate symmetry of the tetrahedron.Moreover each symmetry is completely determined by the permutation of the vertices which it induces. Therefore the group of symmetries of a regular tetrahedron is of order24, since there are24permutations of a set with four elements.It turns out that this group is non-Abelian.2.3Cayley TablesThe algebraic structure of afinite group can be exhibited using a Cayley table,provided that the number of elements in the group is sufficiently small. The rows and columns of the Cayley table are labelled by the elements of the group,and each entry in the table is the product xy of the element x labelling its row with the element y labelling its column.Example Let D6be the group of symmetries of an equilateral triangle with vertices labelled A,B and C in anticlockwise order.The elements of D64consist of the identity transformation I,an anticlockwise rotation R about the centre through an angle of2π/3radians(i.e.,120◦),a clockwise rotation S about the centre through an angle of2π/3radians,and reflections U,V and W in the lines joining the vertices A,B and C respectively to the midpoints of the opposite edges.Calculating the compositions of these rotations,we obtain the following Cayley table:I R S U V WI I R S U V WR R S I W U VS S I R V W UU U V W I R SV V W U S I RW W U V R S I.Thus,for example,VU=S(i.e.,the reflection U followed by the reflection V is the rotation S),and UV=R.Note that each element of the group occurs exactly once in each row and in each column in the main body of the table(excluding the labels at the left of each row and at the head of each column),This is a general property of Cayley tables of groups which can be proved easily from the group axioms.2.4Elementary Properties of GroupsIn what follows,we describe basic properties of a group G,using multiplica-tive notation and denoting the identity element of the group by the letter e.Lemma2.1A group G has exactly one identity element e satisfying ex= x=xe for all x∈G.Proof Suppose that f is an element of G with the property that fx=x for all elements x of G.Then in particular f=fe=e.Similarly one can show that e is the only element of G satisfying xe=x for all elements x of G. Lemma2.2An element x of a group G has exactly one inverse x−1.Proof We know from the axioms that the group G contains at least one element x−1which satisfies xx−1=e and x−1x=e.If z is any element of G which satisfies xz=e then z=ez=(x−1x)z=x−1(xz)=x−1e=x−1. Similarly if w is any element of G which satisfies wx=e then w=x−1.In particular we conclude that the inverse x−1of x is uniquely determined,as required.5Lemma2.3Let x and y be elements of a group G.Then(xy)−1=y−1x−1. Proof It follows from the group axioms that(xy)(y−1x−1)=x(y(y−1x−1))=x((yy−1)x−1)=x(ex−1)=xx−1=e. Similarly(y−1x−1)(xy)=e,and thus y−1x−1is the inverse of xy,as re-quired.Note in particular that(x−1)−1=x for all elements x of a group G,since x has the properties that characterize the inverse of the inverse x−1of x.Given an element x of a group G,we define x n for each positive integer n by the requirement that x1=x and x n=x n−1x for all n>1.We also define x0=e,where e is the identity element of the group,and we define x−n to be the inverse of x n for all positive integers n.Theorem2.4Let x be an element of a group G.Then x m+n=x m x n and x mn=(x m)n for all integers m and n.Proof The identity x m+n=x m x n clearly holds when m=0and when n=0. The identity x m+n=x m x n can be proved for all positive integers m and n by induction on n.The identity when m and n are both negative then follows from the identity x−m−n=x−n x−m on taking inverses.The result when m and n have opposite signs can easily be deduced from that where m and n both have the same sign.The identity x mn=(x m)n follows immediately from the definitions when n=0,1or−1.The result when n is positive can be proved by induction on n.The result when n is negative can then be obtained on taking inverses.If additive notation is employed for an Abelian group then the notation ‘x n’is replaced by‘nx’for all integers n and elements x of the group.The analogue of Theorem2.4then states that(m+n)x=mx+nx and(mn)x= m(n(x))for all integers m and n.2.5The General Associative LawLet x1,x2,...,x n be elements of a group G.We define the product x1x2···x n as follows:-x1x2x3=(x1x2)x3x1x2x3x4=(x1x2x3)x4=((x1x2)x3)x4x1x2x3x4x5=(x1x2x3x4)x5=(((x1x2)x3)x4)x5...x1x2x3···x n=(x1x2···x n−1)x n=(···((x1x2)x3)···x n−1)x n.6(Thus if p j=x1,x2,...,x j for j=1,2,...,n then p j=p j−1x j for eachj>1.)Now an arbitrary product of n elements of G is determined by an expres-sion involving n elements of G together with equal numbers of left and rightparentheses that determine the order in which the product is evaluated.TheGeneral Associative Law ensures that the value of such a product is deter-mined only by the order in which the elements of the group occur within thatproduct.Thus a product of n elements of G has the value x1x2···x n,where x1,x2,...,x n are the elements to be multiplied,listed in the order in whichthey occur in the expression defining the product.Example Given four elements x1,x2,x3and x4of a group,the products ((x1x2)x3)x4,(x1x2)(x3x4),(x1(x2x3))x4,x1((x2x3)x4),x1(x2(x3x4)) all have the same value.(Note that x1x2x3x4is by definition the value of the first of these expressions.)The General Associative Law for products of four or more elements of agroup can be verified by induction on the number on the number of elementsinvolved.Consider a product of n elements of the group G,where n>3.Let theseelements be x1,x2,...,x n when listed in the order in which they occur in theexpression for the product.Suppose also that it is known that the GeneralAssociative Law holds for all products involving fewer than n elements(i.e.,any two products with fewer than n elements have the same value wheneverthe same elements of G occur in both products in the same order).We mustshow that the value of the product is x1x2···x n,wherex1x2···x n=(...(((x1x2)x3)x4)···)x nNow thefirst step in evaluating the product will involve multiplying someelement x r with the succeeding element x r+1.The subsequent steps will thenevaluate a product of n−1elements,namely the elements x i for1≤i<r,the element x r x r+1,and the elements x i for r+1<i≤n.The validity of theGeneral Associative Law for products of fewer than n elements then ensuresthat the value p of the product is given byp=(x1x2)x3···x n if r=1;x1(x2x3)x4···x n if r=2;x1x2(x3x4)x5···x n if r=3(and n>4);...x1x2···x n−2(x n−1x n)if r=n−1.7Also the General Associativity Law for products of fewer than n elements ensures that if r<n−1thenx1x2···x r−1(x r x r+1)=x1x2···x r+1and thus p=x1x2···x n.Thus in order to verify the General Associative Law for products of n elements it only remains to verify thatx1x2···x n−2(x n−1x n)=x1x2···x n.The case when n=3is the Associative Law for products of three elements. For n>3let y be the product x1x2,···x n−2of the elements x1,x2,...,x n−2 (with y=x1x2in the case when n=4).Thenx1x2···x n−2(x n−1x n)=y(x n−1x n)=(yx n−1)x n=(x1x2···x n−1)x n=x1x2···x n.We have thus shown that if the General Associative Law holds for all products involving fewer than n elements of the group G,then it holds for all products involving n elements of G.The validity of the General Associative Law therefore follows by induction on the number of elements occurring in the product in question.Note that the only group axiom used in verifying the General Associative Law is the Associative Law for products of three elements.It follows from this that the General Associative Law holds for any binary operation on a set that satisfies the Associative Law for products of three elements.(A set with a binary operation satisfying the Associative Law is referred to as a semigroup—the General Associative Law holds in all semigroups.)2.6SubgroupsDefinition Let G be a group,and let H be a subset of G.We say that H is a subgroup of G if the following conditions are satisfied:•the identity element of G is an element of H;•the product of any two elements of H is itself an element of H;•the inverse of any element of H is itself an element of H.Lemma2.5Let x be an element of a group G.Then the set of all elements of G that are of the form x n for some integer n is a subgroup of G.8Proof Let H={x n:n∈Z}.Then the identity element belongs to H,since it is equal to x0.The product of two elements of H is itself an element of H,since x m x n=x m+n for all integers m and n(see Theorem2.4).Also the inverse of an element of H is itself an element of H since(x n)−1=x−n for all integers n.Thus H is a subgroup of G,as required.Definition Let x be an element of a group G.The order of x is the smallest positive integer n for which x n=e.The subgroup generated by x is the subgroup consisting of all elements of G that are of the form x n for some integer n.Lemma2.6Let H and K be subgroups of a group G.Then H∩K is also a subgroup of G.Proof The identity element of G belongs to H∩K since it belongs to the subgroups H and K.If x and y are elements of H∩K then xy is an element of H(since x and y are elements of H),and xy is an element of K,and therefore xy is an element of H∩K.Also the inverse x−1of an element x of H∩K belongs to H and to K and thus belongs to H∩K,as required.More generally,the intersection of any collection of subgroups of a given group is itself a subgroup of that group.2.7Cyclic GroupsDefinition A group G is said to be cyclic,with generator x,if every element of G is of the form x n for some integer n.Example The group Z of integers under addition is a cyclic group,generated by1.Example Let n be a positive integer.The set Z n of congruence classes of integers modulo n is a cyclic group of order n with respect to the operation of addition.Example The group of all rotations of the plane about the origin through an integer multiple of2π/n radians is a cyclic group of order n for all integers n. This group is generated by an anticlockwise rotation through an angle of 2π/n radians.Lemma2.7Let G be afinite cyclic group with generator x,and let j and k be integers.Then x j=x k if and only if j−k is divisible by the order of the group.9Proof First we show that x m=e for some strictly positive integer m,wheree is the identity element of G.Now x j=x k for some integers j and k withj<k,since G isfinite.Let m=k−j.Then m>0and x m=x k(x j)−1=e.Let n be the smallest strictly positive integer for which x n=e.Now anyinteger i can be expressed in the form i=qn+r,where q and r are integersand0≤r<n.(Thus q is the greatest integer for which qn≤i.)Thenx i=(x n)q x r=x r(since x n=e).Now the choice of n ensures that x r=e if0<r<n.It follows that an integer i satisfies x i=e if and only if ndivides i.Let j and k be integers.Now x j=x k if and only if x j−k=e,sincex j−k=x j(x k)−1.It follows that x j=x k if and only if j−k is divisible by n.Moreover n is the order of the group G,since each element of G is equal toone of the elements x i with0≤i<n and these elements are distinct.We now classify all subgroups of a cyclic group G.Let x be a generatorof G.Given a subgroup H of G with more than one element,let m be thesmallest strictly positive integer for which x m∈H.Suppose that x i∈H for some integer i.Now i can be expressed in the form i=qm+r,where q and r are integers and0≤r<m.(Thus q is the greatest integer for which qm≤i.)But then x r=x i−qm=x i(x m)−q,where x i∈H and x m∈H, and therefore x r∈H.The choice of m now ensures that r=0,and hence i=qm.Thus x i∈H if and only if i is some integer multiple of m.This shows that H is the cyclic group generated by x m,where m is the smallest strictly positive integer for which x m∈H.Let us consider the case when the cyclic group G isfinite.Let s be theorder of G.Then x s=e,and hence x s belongs to the subgroup H.Itfollows that s must be some integer multiple of m,where m is the smalleststrictly positive integer for which x m∈H.Thus the subgroups of afinite cyclic group G with generator g are the trivial subgroup{e}and the cyclic subgroups generated by x m for each divisor m of the order of G.Consider now the case when the cyclic group G is infinite.For each posi-tive integer m,the element x m generates a subgroup of G,and moreover m isthe smallest strictly positive integer for which x m belongs to that subgroup.Thus if G is an infinite cyclic group with generator x then the subgroups ofG are the trivial subgroup{e}and the cyclic subgroups generated by x m foreach positive integer m.We have thus classified all subgroups of a cyclic group.In particular wesee that any subgroup of a cyclic group is itself a cyclic group.102.8Cosets and Lagrange’s TheoremDefinition Let H be a subgroup of a group G.A left coset of H in G is a subset of G that is of the form xH,where x∈G andxH={y∈G:y=xh for some h∈H}.Similarly a right coset of H in G is a subset of G that is of the form Hx, where x∈G andHx={y∈G:y=hx for some h∈H}.Note that a subgroup H of a group G is itself a left coset of H in G. Lemma2.8Let H be a subgroup of a group G.Then the left cosets of H in G have the following properties:—(i)x∈xH for all x∈G;(ii)if x and y are elements of G,and if y=xa for some a∈H,then xH=yH;(iii)if x and y are elements of G,and if xH∩yH is non-empty then xH= yH.Proof Let x∈G.Then x=xe,where e is the identity element of G.But e∈H.It follows that x∈xH.This proves(i).Let x and y be elements of G,where y=xa for some a∈H.Then yh=x(ah)and xh=y(a−1h)for all h∈H.Moreover ah∈H and a−1h∈H for all h∈H,since H is a subgroup of G.It follows that yH⊂xH and xH⊂yH,and hence xH=yH.This proves(ii).Finally suppose that xH∩yH is non-empty for some elements x and y of G.Let z be an element of xH∩yH.Then z=xa for some a∈H,and z=yb for some b∈H.It follows from(ii)that zH=xH and zH=yH. Therefore xH=yH.This proves(iii).Lemma2.9Let H be afinite subgroup of a group G.Then each left coset of H in G has the same number of elements as H.Proof Let H={h1,h2,...,h m},where h1,h2,...,h m are distinct,and let x be an element of G.Then the left coset xH consists of the elements xh j for j=1,2,...,m.Suppose that j and k are integers between1and m for which xh j=xh k.Then h j=x−1(xh j)=x−1(xh k)=h k,and thus j=k,since h1,h2,...,h m are distinct.It follows that the elements xh1,xh2,...,xh m are distinct.We conclude that the subgroup H and the left coset xH both have m elements,as required.11Theorem2.10(Lagrange’s Theorem)Let G be afinite group,and let H be a subgroup of G.Then the order of H divides the order of G.Proof Each element of G belongs to at least one left coset of H in G,and no element can belong to two distinct left cosets of H in G(see Lemma2.8). Therefore every element of G belongs to exactly one left coset of H.Moreover each left coset of H contains|H|elements(Lemma2.9).Therefore|G|= n|H|,where n is the number of left cosets of H in G.The result follows.Definition Let H be a subgroup of a group G.If the number of left cosets of H in G isfinite then the number of such cosets is referred to as the index of H in G,denoted by[G:H].The proof of Lagrange’s Theorem shows that the index[G:H]of a sub-group H of afinite group G is given by[G:H]=|G|/|H|.Corollary2.11Let x be an element of afinite group G.Then the order of x divides the order of G.Proof Let H be the set of all elements of G that are of the form x n for some integer n.Then H is a subgroup of G(see Lemma2.5),and the order of H is the order of x.But the order of H divides G by Lagrange’s Theorem (Theorem2.10).The result follows.Corollary2.12Anyfinite group of prime order is cyclic.Proof Let G be a group of prime order,and let x be some element of G that is not the identity element.Then the order of x is greater than one and divides the order of G.But then the order of x must be equal to the order of G,since the latter is a prime number.Thus G is a cyclic group generated by x,as required.2.9Normal Subgroups and Quotient GroupsLet A and B be subsets of a group G.The product AB of the sets A and B is defined byAB={xy:x∈A and y∈B}.We denote{x}A and A{x}by xA and Ax,for all elements x of G and subsets A of G.The Associative Law for multiplication of elements of G ensures that(AB)C=A(BC)for all subsets A,B and C of G.We can therefore use the notation ABC to denote the products(AB)C and A(BC);12and we can use analogous notation to denote the product of four or more subsets of G.If A,B and C are subsets of a group G,and if A⊂B then clearly AC⊂BC and CA⊂CB.Note that if H is a subgroup of the group G and if x is an element of G then xH is the left coset of H in G that contains the element x.Similarly Hx is the right coset of H in G that contains the element x.If H is a subgroup of G then HH=H.Indeed HH⊂H,since the product of two elements of a subgroup H is itself an element of H.Also H⊂HH since h=eh for any element h of H,where e,the identity element of G,belongs to H.Definition A subgroup N of a group G is said to be a normal subgroup of G if xnx−1∈N for all n∈N and x∈G.The notation‘N G’signifies‘N is a normal subgroup of G’.Definition A group G is said to be simple if the only normal subgroups of G are the whole of G and the trivial subgroup{e}whose only element is the identity element e of G.Lemma2.13Every subgroup of an Abelian group is a normal subgroup.Proof Let N be a subgroup of an Abelian group G.Thenxnx−1=(xn)x−1=(nx)x−1=n(xx−1)=ne=nfor all n∈N and x∈G,where e is the identity element of G.The result follows.Example Let S3be the group of permutations of the set{1,2,3},and let H be the subgroup of S3consisting of the identity permutation and the transposition(12).Then H is not normal in G,since(23)−1(12)(23)= (23)(12)(23)=(13)and(13)does not belong to the subgroup H.Proposition2.14A subgroup N of a group G is a normal subgroup of G if and only if xNx−1=N for all elements x of G.Proof Suppose that N is a normal subgroup of G.Let x be an element of G.Then xNx−1⊂N.(This follows directly from the definition of a normal subgroup.)On replacing x by x−1we see also that x−1Nx⊂N,and thus N=x(x−1Nx)x−1⊂xNx−1.Thus each of the sets N and xNx−1is contained in the other,and therefore xNx−1=N.Conversely if N is a subgroup of G with the property that xNx−1=N for all x∈G,then it follows immediately from the definition of a normal subgroup that N is a normal subgroup of G.13Corollary2.15A subgroup N of a group G is a normal subgroup of G if and only if xN=Nx for all elements x of G.Proof Let N be a subgroup of G,and let x be an element of G.If xNx−1= N then xN=(xNx−1)x=Nx.Conversely if xN=Nx then xNx−1= Nxx−1=Ne=N,where e is the identity element of G.Thus xN=Nx if and only if xNx−1=N.It follows from Proposition2.14that a subgroup N of G is normal if and only if xN=Nx for all elements x of G,as required.Let N be a normal subgroup of G.Corollary2.15shows that a subset of G is a left coset of N in G if and only if it is a right coset of N in G.We may therefore refer to the left and right cosets of a normal subgroup N as cosets of N in G(since it is not in this case necessary to distinguish between left and right cosets).Lemma2.16Let N be a normal subgroup of a group G and let x and y be elements of G.Then(xN)(yN)=(xy)N.Proof If N is a normal subgroup of G then Ny=yN,and therefore (xN)(yN)=x(Ny)N=x(yN)N=(xy)(NN).But NN=N,since N is a subgroup of G.Therefore(xN)(yN)=(xy)N,as required.Proposition2.17Let G be a group,and let N be a normal subgroup of G.Then the set of all cosets of N in G is a group under the operation of multiplication.The identity element of this group is N itself,and the inverse of a coset xN is the coset x−1N for any element x of G.Proof Let x,y and z be any elements of G.Then the product of the cosets xN and yN is the coset(xy)N.The subgroup N is itself a coset of N in G, since N=eN.Moreover(xN)N=(xN)(eN)=(xe)N=xN,N(xN)=(eN)(xN)=(ex)N=xN,(xN)(x−1N)=(xx−1)N=N,(x−1N)(xN)=(x−1x)N=N.for all elements x of G.Thus the group axioms are satisfied.Definition Let N be a normal subgroup of a group G.The quotient group G/N is defined to be the group of cosets of N in G under the operation of multiplication.14Example Consider the dihedral group D8of order8,which we represent as the group of symmetries of a square in the plane with corners at the points whose Cartesian co-ordinates are(1,1),(−1,1),(−1,−1)and(1,−1).ThenD8={I,R,R2,R3,T1,T2,T3,T4},where I denotes the identity transformation,R denotes an anticlockwise rotation about the origin through a right angle,and T1,T2,T3and T4denote the reflections in the lines y=0,x=y,x=0and x=−y respectively.Let N={I,R2}.Then N is a subgroup of D8.The left cosets of N in D8are N,A,B and C,whereA={R,R3},B={T1,T3},C={T2,T4}.Moreover N,A,B and C are also the right cosets of N in D8,and thus N is a normal subgroup of D8.On multiplying the cosets A,B and C with one another wefind that AB=BA=C,AC=CA=B and BC=CB=A. Therefore the quotient group D8/N is a group of order4with Cayley tableN A B CN N A B CA A N C BB BC N AC C B A N.This is the Cayley table of the Klein4-group V4.There is an alternative approach to the construction of quotient groups which utilises the basic properties of equivalence relations.Let G be a group, and let H be a subgroup of G.Define a relation∼H on G,where elements x and y of G satisfy x∼H y if and only if there exists some element h of H satisfying x=yh.Now x=xe,where e,the identity element of G,is an element of H.It follows that x∼H x for all elements x of G.Thus the relation∼H is reflexive.If elements x and y of G satisfy x∼H y then they also satisfy y∼H x,for if x=yh,where h is an element of H,then y=xh−1. Thus the relation∼H is symmetric.If x,y and z are elements of G satisfying x∼H y and y∼H z then x∼H z,for if x=yh and y=zk,where h and k belong to H,then x=zkh,and kh belongs to H.Thus the relation∼H is transitive.We conclude that the relation∼H is an equivalence relation.One can readily verify that its equivalence classes are the left cosets of H in G.Now suppose that the subgroup H is normal in G.Let x,y,u and v be elements of G,where x∼H u and y∼H v.Then there exist elements h and15。