A vector space is a non-empty set consisting of elements called vectors which can be added and multiplied by scalars.
The scalars that operate on vectors in a vector space form a field $\mathbb{F}$, where addition $+$ and multiplication $\cdot$ over $\mathbb{F}$ are performed between scalars.
Prerequisites
Groups (another algebraic structure)
A group, denoted by $(G, \cdot)$, is a non-empty set (finite or infinite) $G$ with a binary operator $\cdot$ such that the following four properties are satisfied:
Closure: if $a$ and $b$ belong to $G$, then $a\cdot b$ also belongs to $G$;
Associative: $a\cdot (b\cdot c)=(a\cdot b)\cdot c$ for all $a,b,c \in G$;
Identity element: there is an element $e \in G$ such that $a\cdot e=e\cdot a=a$ for every element $a \in G$;
Inverse element: for every element $a$ in $G$, there's an element $a'$ such that $a\cdot a'=e$ where $e$ is the identity element.
In general, a group is not necessarily commutative, namely $a\cdot b=b\cdot a$ for all $a,b \in G$. When it does, the group is an abelian group. If $G$ has finitely many elements, $G$ is said to be a finite group. The order of $G$ is the number of elements in $G$; it is denoted by $|G|$ or $\#G$.
Examples
Let's consider the set of integers, $\mathbb{Z}$ with addition and multiplication.
$\small \begin{array}{c|c|c} & \text{Addition} & \text{Multiplication} \\ \hline \text{Closure} & \text{a+b is an integer} & \text{a*b is an integer} \\ \text{Associativity} & a+(b+c)=(a+b)+c & a*(b*c)=(a*b)*c \\ \text{Existence of an identity element} & a+0=a & a*1=a \\ \text{Existence of inverse elements} & a+(-a)=0 & \color{blue}{\text{only for 1 and -1}: 1*1=1,\: -1*(-1)=1} \\ \text{Commutativity} & a+b=b+a & a*b=b*a \end{array}$
$(\mathbb{Z}, +)$ is an infinite abelian group but $(\mathbb{Z}, *)$ is not a group.
$(\mathbb{Z}, *)$ is not a group because most of the elements do not have inverses.
Now consider the set of remainders modulo a positive integer $n$, $\mathbb{Z}_n$ or $Z/nZ$, namely $\{0,1,2,\cdots,n-1\}$ with addition modulo $n$ and multiplication modulo $n$.
$\small \begin{array}{c|c|c} & \text{Addition mod n} & \text{Multiplication mod n} \\ \hline \text{Closure} & a+b \equiv c\:\text{mod n},\: 0\leq c\leq n-1 & a*b \equiv c\:\text{mod n},\: 0\leq c\leq n-1 \\ \text{Associativity} & a+(b+c)=(a+b)+c\:\text{mod n} & a*(b*c)=(a*b)*c\:\text{mod n} \\ \text{Existence of an identity element} & a+0=a\:\text{mod n} & a*1=a\:\text{mod n} \\ \text{Existence of inverse elements} & a+(n-a)=0\:\text{mod n} & \color{blue}{\text{only when a is coprime to n}} \\ \text{Commutativity} & a+b=b+a\:\text{mod n} & a*b=b*a\:\text{mod n}\end{array}$
$(\mathbb{Z}_n, +)$ is a finite abelian group with order $n$ but $(\mathbb{Z}_n, *)$ is not a group. Note that $0$ is an element of $\mathbb{Z}_n$ and $0$ is not coprime to any number so there is no inverse for $0$. Therefore $(\mathbb{Z}_n, *)$ is not a group.
Lastly, consider the set of remainders coprime to the modulus $n$. For example, when $n=10$, the set is $\{1,3,5,7,9\}$. In particular, when $n$ is a prime number, the set is $\{1,2,\cdots,n-1\}$. Let's call this set Coprime-n with addition modulo $n$ and multiplication modulo $n$.
$\small \begin{array}{c|c|c} & \text{Addition mod n} & \text{Multiplication mod n} \\ \hline \text{Closure} & \color{blue}{a+b\: \text{may not be in Coprime-n.}} & a*b \equiv c\:\text{mod n},\: \text{c is in Coprime-n} \\ \text{Associativity} & a+(b+c)=(a+b)+c\:\text{mod n} & a*(b*c)=(a*b)*c\:\text{mod n} \\ \text{Existence of an identity element} & \color{blue}{\text{null}} & a*1=a\:\text{mod n} \\ \text{Existence of inverse elements} & \color{blue}{\text{null}} & \text{exists for every a in Coprime-n} \\ \text{Commutativity} & a+b=b+a\:\text{mod n} & a*b=b*a\:\text{mod n}\end{array}$
Now (Coprime-n, +) is not a group and (Coprime-n, *) is a group. (Coprime-n, *) is abelian and finite. When $n$ is a prime number, the order of (Coprime-n, *) is $n-1$. Note that this only holds when $n$ is a prime number. For example, when $n=10$, the order of (Coprime-10, *) is $5$ not $9$.
A field is a non-empty set $F$ with two binary operators which are usually denoted by $+$ and $*$ (or omitted), that satisfy the field axioms:
(1) Closure: If $a,b \in \mathbb{F}$, then $a+b \in \mathbb{F}$ and $ab \in \mathbb{F}$.
(2) Commutativity: If $a,b \in \mathbb{F}$, there hold $a+b=b+a$ and $ab=ba$.
(3) Associativity: If $a,b \in \mathbb{F}$, there hold $(a+b)+c=a+(b+c)$ and $a(bc)=(ab)c$.
(4) Distributivity: For $a,b,c \in \mathbb{F}$, there hold $a(b+c)=ab+ac$.
(5) Existence of zero: There is a scalar, called zero, denoted by 0, such that $a+0=a$ for any $a \in \mathbb{F}$.
(6) Existence of unity: There is a scalar different from zero, called one, denoted by $1$, such that $1a=a$ for any $a \in \mathbb{F}$.
(7) Existence of additive inverse: For any $a \in \mathbb{F}$, there is a scalar, denoted by $-a$, such that $a+(-a)=0$.
(8) Existence of multiplicative inverse: For any $a \in \mathbb{F}\setminus \{0 \}$, there is a scalar, denoted by $a^{-1}$, such that $aa^{-1}=1$.
If the set $F$ is finite, then the field is said to be a finite field. The order of a finite field is the number of elements in the finite field. Finite fields have practical applications in coding theory, cryptography, algebraic geometry and number theory.
Examples of fields: $\mathbb{Q}, \mathbb{R}, \mathbb{C}$
Nonexample of fields: $(\mathbb{Z}, +, *)$ does not form a field because there are no multiplicative inverses for its non-unit elements. (For any $a \in \mathbb{Z}$, $a^{-1}$ is not included in $\mathbb{Z}$.)
$(\mathbb{Z}_n, +, *)$ in general is not a finite field. For example, $\mathbb{Z}_8 \setminus \{0\}=\{1,2,3,4,5,6,7\}$ along with modulo $8$ multiplication does not form a group. However, when $n$ is a prime number, say $5$, $\mathbb{Z}_5 \setminus \{0\}=\{1,2,3,4\}$ along with modulo $5$ multiplication forms the abelian group $\mathbb{Z}_5^*$. Therefore, $(\mathbb{Z}_5, +, *)$ is a finite field. [...]
A set $U$ is a vector space over a field $\mathbb{F}$ if $U$ is non-empty and there is addition between the elements of $U$, called vectors, and scalar multiplication between elements in $\mathbb{F}$, called scalars, and vectors, such that the following axioms hold.
(1) (Closure) For $u,v \in U$, we have $u+v \in U$. For $u \in U$ and $a \in \mathbb{F}$, we have $au \in U$.
(2) (Commutativity) For $u,v \in U$, we have $u+v=v+u$.
(3) (Associativity) For $u,v,w \in U$, we have $u+(v+w)=(u+v)+w$.
(4) (Existence of zero vector) There is a vector, called zero and denoted by $0$ such that $u+0=u$ for any $u \in U$.
(5) (Existence of additive inverse) For any $u \in U$, there is a vector, denoted by $(-u)$, such that $u+(-u)=0$.
(6) (Associativity of scalar multiplication) For any $a,b \in \mathbb{F}$ and $u \in U$, we have $a(bu)=(ab)u$.
(7) (Property of unit scalar) For any $u \in U$, we have $1u=u$.
(8) (Distributivity) For any $a,b \in \mathbb{F}$ and $u,v \in U$, we have $(a+b)u=au+bu$ and $a(u+v)=au+av$.
Reference:
http://www.doc.ic.ac.uk/~mrh/330tutor/index.html
More to explore:
http://www.math.uconn.edu/~kconrad/blurbs/galoistheory/finitefields.pdf
http://aix1.uottawa.ca/~jkhoury/coding.htm
Application of finite fields: coding theory
http://mathworld.wolfram.com/Error-CorrectingCode.html
No comments:
Post a Comment