03.2 Finite Fields and Vector Spaces

We want to have algebraic structure into code design / decoding

Field

A field is a triplet $(\mathcal{K},+,\times )$

• $\mathcal{K}$ is a set
• $+,\times$ are two binary operators, for which we have
  • Associativity
  • Commutativity
  • Identity under $+$
  • Inverse under $+$
  • Identity under $\times$
  • Inverse under $\times$
  • Distributivity: $a\times (b+c)=(a\times b)+(a\times c)$

If $(\mathcal{K},+,\times )$ is finite ⇒ finite field

We can of course denote the operations as any other symbol

$ab=a\times b$, $a-b=a+(-b)$

For a positive integer $n$, we have

• $nb$ ⇒ $b+b+\cdots +b$ ← $n$ times ⇒ $n$ times $b$
• $a^n$ ⇒ $a\times a\times \cdots \times a$ ← $n$ times

Every field contains the special number $1$

• For a finite field, the order of $1$ with respect to $+$ is a prime number $p$ — called the field characteristic

Definition

Isomorphism ⇐> between two finite fields $\mathbb{F}=(\mathcal{F},+,\times )$ and $\mathbb{K}=(\mathcal{K},\oplus ,\otimes )$ is a bijection

$\varphi :\mathcal{F}\to \mathcal{K}$

Such that for all $a,b\in \mathcal{F}$

$$\begin{array}{c}\varphi (a+b)=\varphi (a)\oplus \varphi (b)\\ \varphi (a\times b)=\varphi (a)\otimes \varphi (b)\end{array}$$

Theorem

1. The cardinality of a finite field is an integer power of its characteristic $p^m$ for some prime $p$
2. All finite fields of the same cardinality are isomorphic
3. For every prime number $p$, and positive integer $m$, there exists a finite field of cardinality $p^m$

This is self sufficient:

$(\mathbb{Z}/k\mathbb{Z},+,\cdot )$ is a finite field ⇐> $k$ is prime

Finite Dimensional Vector spaces

From linear algebra (last semester)

Definition

A nonempty set $V$ is set to be vector space over a finite field $\mathbb{F}$ if

1. There exists an operation called addition that associates each pair $\vec{u},\vec{v}\in V$ a vector $\vec{u}+\vec{v}\in V$
2. There exists an operation called the scalar multiplication that associates each $\alpha \in \mathbb{F}$ and $\vec{v}\in V$ a new vector $\alpha \vec{v}\in V$

Definition

We have a vector space over a field $\mathbb{F}$ denoted as $(V,+,\times )$ if

1. $(V,+)$ is a commutative group
2. The binary operator $\times$ is between an element of $V$ and one of $\mathbb{F}$

If $V$ is a vector space $S\subset V$ with the property that $S$ is closed under vector addition and multiplication by a scalar, then it it a vector space too

We call this a subspace of $V$

The set of all linear combinations of $({\vec{v}}_1,\dots ,{\vec{v}}_n)$ is called the span

A vector space is called finite-dimensional if there is a list of vectors which spans the whole space

Theorem

A list $({\vec{v}}_1,\dots ,{\vec{v}}_n)$ in $V$ is a basis of $V$ ⇐> every $\vec{v}\in V$ can be written uniquely in the form

$$\vec{v}=\sum _{i=1}^n{\lambda }_i{\vec{v}}_i$$

Theorem

Every spanning list in a vector space can be reduced to a basis of the vector space

Theorem

Any two bases of a finite dimensional vector space have the same length

Theorem

The set of solutions in $V={\mathbb{F}}^n$ of $m$ linear homogeneous equations in $n$ variables is a subspace $S$ of $V$

Let $r$ be the dimensionality of the vector space spanned by the coefficient vectors. We therefore have $\dim (S)=n-r$

In particular, if the $m$ vectors of coefficients are linearly independent, then $\dim (S)=n-m$

Conversely if $S$ is a subspace of $V$ of dimension $k$. There exists a set of $n-k$ linear equations with coefficients that form linearly independent vectors in $V$, the solution of which are the vectors in $S$

Theorem

An $n$-dimensional vector space $V$ over a finite field $\mathbb{F}$

• is finite
• has cardinality $\text{card}(V)=[\text{card}(\mathbb{F}){]}^n$

03.3 Linear Codes