Skip to content

Preliminaries

Notation

  1. $\Z$ = Set of integers
  2. $Q$ = Set of rational numbers
  3. $\reals$ = Set of real numbers
  4. $\cnums$ = Set of complex numbers
  5. $M_n(\reals)$ = Set of n x n matrices with entries from $\reals$
  6. $GL_n(\reals)$ = Set of all invertible n x n matrices over $\reals$
  7. $SL_n(\reals) = \lbrace A \in M_n(\reals) \mid det A = 1 \rbrace$
  8. $O_n(\reals)$ = Set of all orthogonal matrices over $\reals$
  9. $S_n$ = Set of all permutations
  10. $A_n$ = Set of all even permutations

Well defined

Let A, B be two sets and $f : A \to B$ be a function and A = $A_1 \cup A_2$, then f is well defined if $A_1 \cap A_2 = \phi$.

Injective

f is injective if f is 1-1 i.e. if $f(x_1) = f(x_2) \implies x_1 = x_2$.

Surjective

f if surjective if every element in B has a pre-image in A.

Bijective

f is said to be bijective if f is 1-1 and onto.

Image and Pre-image

$f : A \to B$

$f(A) = \lbrace b \in B \mid b = f(a) for \, some a \in A \rbrace$ is a subset of B called the image of f.

Let $C \subset B$

$f^-1(A) = \lbrace a \in A \mid f(a) \in C \rbrace$ is called the pre-image of C under f.

Binary Relation

  1. A binary relation on a set A is a subset R of A x A and we write a ~ b if (a,b) $\in$ R.
  2. The relation ~ is reflexive if $\forall a \in A, a \sim a $.
  3. ~ is symmetric if $\forall a,b \in A, a \sim b \implies b \sim a$.
  4. ~ is transitive if $\forall a,b,c \in A, a \sim b$ and $ b \sim c \implies a \sim c$.

A relation is an equivalence relation if it is reflexive, symmetric, and transitive.

Equivalence class

Def 1.1

If $\sim$ defines an equivalence relation on A then equivalence class of $a \in A$ is defined to be $\lbrace x \in A \mid x \sim a \rbrace$.

We denote the equivalence class of a as $[a]$ and the set of equivalence classes of $\sim$ as $A / _\sim$.

Ex 1.1

a $\sim$ b is b - a is divisible by 5. This is an equivalence relation.

$$ [0] = \lbrace 0, 5, 10, ... \rbrace = 5k \\ [1] = \lbrace 1 + 5k \mid k \in \Z \rbrace \\ [2] = \lbrace 2 + 5k \mid k \in \Z \rbrace \\ [3] = \lbrace 3 + 5k \mid k \in \Z \rbrace \\ [4] = \lbrace 4 + 5k \mid k \in \Z \rbrace $$

Here $\Z/_\sim \,is$

$\Z/_{5\Z} \,or\, \Z_5$.

Partition

A partition of A is any collection $\lbrace A_i \mid i \in I \rbrace$ of non empty subsets of A s.t.

$$ (i) \quad A = \bigcup_{i \in I} A_i \\ (ii) \quad \forall i,j \in I, i \,\cancel=\, j. A_i \cap A_j = \phi $$

Let $A_1$ and $A_2$ be two equivalence classes. Let $x \in A_1 \cap A_2$. Then $A_1 = A_2$ i.e. either the two equivalence classes are disjoint or equal.

Propn 1.1

  1. If $\sim$ defines an equivalence relation on A then the set of equivalence classes of $\sim$ forms a partition on A.
  2. If $\lbrace A_i \mid i \in I \rbrace$ is a partition of A then there is a equivalence relation on A whose equivalence classes are precisely the sets $A_i$.

Euler Phi function

$\phi(n)$ denotes the number of positive integers $a \leq n$ s.t. gcd(a,n) = 1 where n is a positive integer.

$\phi(p) = p-1$, $\phi(p^\alpha) = p^\alpha - p^{\alpha-1}$

$\phi$ function has the property that if gcd(a,b) = 1 then $\phi(a.b) = \phi(a).\phi(b)$

Permutation

Let $\Omega$ be a non-empty set. Let $S_\Omega = \lbrace f : \Omega \to \Omega \mid \text{f is bijective} \rbrace$

$\Omega = [n] = \lbrace 1,2,...,n \rbrace$

$S_n = \lbrace f : [n] \to [n] \mid \text{f is bijective} \rbrace$

The elements of $S_n$ are called permutations and we can define composition operation on $S_n$. $\vert S_n \vert = n!$

$$ S_6 \quad\text{let}\, \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 3 & 6 & 1 & 2 \end{pmatrix} \in S_6 \\ \sigma = (1\;5)(2\;4\;6) $$

Composition

$$ \text{let}\, \sigma_1 = (1\;2\;3) , \,\sigma_2 = (1\;2)(3\;4) \\ \sigma_1 . \sigma_2 = (1\;2\;3) . (1\;2)(3\;4) = (1\;3\;4) $$

Inverse

$$ \text{let}\, \sigma = (1\;5)(2\;4\;6) \\ \quad \sigma^{-1} = (5\;1)(6\;4\;2) $$

Def 1.2

The permutation $(a_1\;a_2 ... a_k)$ where $a_i \in [n]$ are distinct is called k-cycle.

Ex 1.2

Every permutation if a product of disjoint cycles and disjoint cycles commute with each other.

Def 1.3

A cycle of length 2 is called a transposition.

Ex 1.3

Every k-cycle is a product of transpositions.

Def 1.4

A permutation in $S_n$ is called an even permutation if it is a product of even number of transpositions. Otherwise it is called an odd permutation.

Consider the polynomial $P(x_1,...,x_n) = \prod_{1 \leq j < i \leq n}(x_i-x_j) $

Let $\sigma \in S_n$ define $\sigma P(x_1,...,x_n) = \prod_{1 \leq j < i \leq n}(x_{\sigma (i)}-x_{\sigma (j)})$

If $\sigma$ is a transposition then $\sigma P = -P$

Binary Operations

Def 1.5

A law of composition or binary operation on a set A is a map $$ f : A \times A \longrightarrow A \\ (a,b) \longmapsto f(a,b) $$

Ex 1.4

$$ \reals \times \reals \longrightarrow \reals \\ (a,b) \longmapsto a+b \\ (a,b) \longmapsto a.b $$

$$ M_n(\reals) \times M_n(\reals) \longrightarrow M_n(\reals) \\ (A,B) \longmapsto A+B \\ (A,B) \longmapsto A.B $$

$$ S_n \times S_n \longrightarrow S_n \\ (\sigma_1,\sigma_2) \longmapsto \sigma_1.\sigma_2 $$

Properties of binary operations

  1. A binary operation is said to be associative if $\forall a,b,c \in A,\, a.(b.c) = (a.b).c$
  2. A binary operation is said to be commutative if $\forall a,b \in A,\, a.b = b.a$
  3. An element $e \in A$ is said to be identity element if $\forall a \in A,\, a.e = e.a = a$
  4. Suppose there is an identity element in A wrt binary operation $.$, then an element $a \in A$ is called invertible if $\exists b \in A$ s.t. $a.b = b.a = 1$

Remarks

We usually use the following notations to denote binary operations: $$a.b, a+b, a\ast b, a \times b, ab$$

We usually denote the additive identity by $0$ and the multiplicative identity by $1$.

If an element is invertible then its inverse is unique.

If we use $+$ to denote the binary operation then we use $-a$ to denote the inverse of $a\in A$.

If we use $.$ to denote the binary operation then we use $a^{-1}$ to denote the inverse of $a\in A$.

Ex 1.5

  1. $\mathbb{Z}, \mathbb{Q} , \mathbb{R} , \mathbb{C} $ wrt $+$ binary operation.
  2. $\mathbb{Q}^\times, \mathbb{R} ^ \times, \mathbb{C} ^ \times $ where $A^\times = A \backslash \lbrace 0 \rbrace$ wrt $.$ operation.
  3. $GL_n(\reals) = \lbrace A \in M_n(\reals) \mid det A \cancel= 0 \rbrace$ and $SL_n(\reals)$ wrt $.$ operation.
  4. $(S_n, .)$ wrt composition operation.
  5. $\Z_n$ wrt $+$ operation.