2.1 We considerRnf1g; ?, where

2 Linear Algebra Exercises 2.1 We consider(Rnf1g; ?), where

a ? b:=ab+a+b; a; b2Rnf1g (2.1)

• Show that(Rnf1g; ?)is an Abelian group.
• Solve

3? x ? x= 15 in the Abelian group(Rnf1g; ?), where?is dened in (2.1).

• First, we show thatRnf1gis closed under?: For alla; b2Rnf1g:

a ? b=ab+a+b+ 11 = (a+ 1) |{z} 6=0 (b+ 1) |{z} 6=0 16=1 )a ? b2Rnf1g Next, we show the group axioms Associativity:For alla; b; c2Rnf1g: (a ? b)? c= (ab+a+b)? c = (ab+a+b)c+ (ab+a+b) +c =abc+ac+bc+ab+a+b+c =a(bc+b+c) +a+ (bc+b+c) =a ?(bc+b+c) =a ?(b ? c)

Commutativity:

8a; b2Rnf1g:a ? b=ab+a+b=ba+b+a=b ? a

Neutral Element:n= 0is the neutral element since

8a2Rnf1g:a ?0 =a= 0? a

Inverse Element:We need to nda, such thata ?a= 0 = a ? a.

a ? a= 0()aa+a+ a= 0 ()a(a+ 1) =a a6=1 ()a= a a+ 1 =1 + 1 a+ 1 6=12Rnf1g 468 This material will be published by Cambridge University Press asMathematics for Machine Learn- ingby Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong. This pre-publication version is free to view and download for personal use only. Not for re-distribution, re-sale or use in deriva- tive works.cby M. P. Deisenroth, A. A. Faisal, and C. S. Ong, 2020.https://mml-book.com.There are no Questions for Solution in Chapter 1.Mathematics For Machine Learning, 1e By Cheng Soon, Marc Peter, Deisenroth, Aldo Faisal Solution Manual 1 / 4

Exercises469 b.3? x ? x= 15()3?(x 2 +x+x) = 15 ()3x 2

• 6x+ 3 +x

2

• 2x= 15

()4x 2

• 8x12 = 0

()(x1)(x+ 3) = 0 ()x2 f3;1g 2.2 nbe inNnf0g. Letk; xbe inZ. We dene the congruence class

kof the integerkas the set k=fx2Zjxk= 0 (modn)g =fx2Zj 9a2Z: (xk=na)g: We now deneZ=nZ(sometimes writtenZn) as the set of all congruence classes modulon. Euclidean division implies that this set is a nite set con-

tainingnelements:

Zn=f0;1; : : : ;n1g For alla;b2Zn, we dene

ab:=a+b

• (Zn;)is a group. Is it Abelian?

b.for allaandbinZnas ab=ab ;(2.2) whereabrepresents the usual multiplication inZ.Letn= 5. Draw the times table of the elements ofZ5nf0gunder, i.e., calculate the productsabfor allaandbinZ5nf0g.Hence, show thatZ5nf0gis closed underand possesses a neutral element for. Display the inverse of all elements inZ5nf0gunder.Conclude that(Z5nf0g;)is an Abelian group.

• (Z8nf0g;)is not a group.

d.´ezout theorem states that two integersaandbare relatively prime (i.e.,gcd(a; b) = 1) if and only if there exist two integers uandvsuch thatau+bv= 1. Show that(Znnf0g;)is a group if and only ifn2Nnf0gis prime.a.Closure: Leta;bbe inZn. We have: ab=a+b =(a+b) modn by denition of the congruence class, and since[(a+b) modn]2 f0; : : : ; n1g, it follows thatab2Zn. Thus,Znis closed under.c2020 M. P. Deisenroth, A. A. Faisal, C. S. Ong. To be published by Cambridge University Press. 2 / 4

470Linear Algebra Associativity: Letcbe inZn. We have: (ab)c= (a+b)c=(a+b) +c=a+ (b+c) =a(b+c) =a(bc) so thatis associative.

Neutral element: We have

a+0 =a+ 0 =a=0 +a so0is the neutral element for.

Inverse element: We have

a+(a) =aa=0 =(a) +a and we know that(a)is equal to(a) modnwhich belongs toZn and is thus the inverse ofa.

Commutativity: Finally, the commutativity of(Zn;)follows from

that of(Z;+)since we have ab=a+b=b+a=ba ; which shows that(Zn;)is an Abelian group.

b.Z5nf0gunder:

1234 11234 22413 33142 44321 We can notice that all the products are inZ5nf0g, and that in particular, none of them is equal to0. Thus,Z5nf0gis closed under. The neutral element is1and we have(1) 1

=1,(2)

1

=3,(3)

1 =2, and(4) 1 =4.Associativity and commutativity are straightforward and(Z5nf0g;)is an Abelian group.c.2and4belong toZ8nf0g, but their product24 =8 =0 does not. Thus, this set is not closed underand is not a group.d.Let us assume thatnis not prime and can thus be written as a product n=abof two integersaandbinf2; : : : ; n1g. Both elementsa andbbelong toZnnf0gbut their productab=n=0does not.Thus, this set is not closed underand(Znnf0g;)is not a group.Letnbe a prime number. Letaandbbe inZnnf0gwithaandbin f1; : : : ; n1g. Asnis prime, we know thatais relatively prime ton, and so isb. Let us then take four integersu; v; u

andv

, such that au+nv= 1 bu

+nv

= 1:

We thus have that(au+nv)(bu

+nv

• = 1, which we can rewrite as

ab(uu

• +n(auv

+vbu

+nvv

• = 1

Draft (2020-02-23) of “Mathematics for Machine Learning”. Feedback:https://mml-book.com. 3 / 4

Exercises471 By virtue of the B´ezout theorem, this implies thatabandnare rela- tively prime, which ensures that the productabis not equal to0 and belongs toZnnf0g, which is thus closed under.The associativity and commutativity ofare straightforward, but we need to show that every element has an inverse. First, the neutral element is1. Let us again consider an elementainZnnf0gwithain f1; : : : ; n1g. Asaandnare coprime, the B´ezout theorem enables us to dene two integersuandvsuch that au+nv= 1;(2.3) which implies thatau= 1nvand thus au= 1 modn ;(2.4) which means thatau=au=1, or thatuis the inverse ofa. Over- all,(Znnf0g;)is an Abelian group. Note that the B´ezout theorem ensures the existence of an inverse without yielding its explicit value, which is the purpose of the extended Euclidean algorithm.

2.3Gof33matrices dened as follows:

G= 8 <

:

2 4 1x z

• 1y
• 0 1

3 52R 33

x; y; z2R 9 = ; We deneas the standard matrix multiplication.Is(G;)a group? If yes, is it Abelian? Justify your answer.

Closure: Leta; b; c; x; yandzbe inRand let us deneAandBinGas

A= 2 4 1x z

• 1y
• 0 1

3 5; B= 2 4 1a c

• 1b
• 0 1

3

5:

Then, AB= 2 4 1x z

• 1y
• 0 1

3 5 2 4 1a c

• 1b
• 0 1

3 5= 2 4 1a+x c+xb+z

• 1 b+y
• 0 1

3

5:

Sincea+x,b+yandc+xb+zare inRwe haveAB2 G. Thus,Gis closed under matrix multiplication.

Associativity: Let; andbe inRand letCinGbe dened as

C= 2 4 1

• 1
• 0 1

3

5:

It holds that

(AB)C=

2 4 1a+x c+xb+z

• 1 b+y
• 0 1

3 5 2 4 1

• 1
• 0 1

3 5 = 2 4 1+a+x ++x+c+xb+z

• 1+b+y
• 0 1

3

5:

c2020 M. P. Deisenroth, A. A. Faisal, C. S. Ong. To be published by Cambridge University Press.

• / 4