УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ЛИНЕЙНОЕ ПРОСТРАНСТВО. Применение ТЕОРИЯ КОДИРОВАНИЯ


Линейные пространства над конечными полями

Здесь мы сравним свойства линейных пространств с конечным и бесконечным числом элементов.

Поле из двух элементов

Будем рассматривать упорядоченные наборы — строки1) (x_1,\dots,x_{n}) из n_{} чисел \{x_1,\dots,x_n\}\subset \{0,1\}. Множество таких наборов, рассматриваемое вместе с операцией умножения на константы 0_{} или 1_{} и операцией поразрядного сложения по модулю 2_{}:

(x_1,\dots,x_n)+(y_1,\dots,y_n)=(x_1+y_1 \pmod{2},\dots,x_n+y_n \pmod{2})

образует линейное пространство, которое мы будем обозначать \mathbb V^n, а собственно составляющие его наборы будем называть векторами.

§

Строго говоря, надо было бы говорить о векторах, элементами которых являются классы вычетов по модулю 2_{}, но я не буду заморачиваться излишним формализмом.

Свойства.

1. Это пространство состоит из конечного числа векторов2): \operatorname{Card} (\mathbb V^n)=2^n.

2. Любой вектор X\in \mathbb V^n является обратным самому себе:

X+X=2\,X \equiv \mathbb O \pmod{2} \qquad \Rightarrow \qquad -X=X \ .

3. Два вектора \{X,Y\}\subset \mathbb V^n линейно независимы тогда и только тогда, когда они различны (различаются хотя бы по одной координате).

4. Размерность пространства \mathbb V^n равна n_{}: \dim V^n = n_{}; в качестве базиса можно взять строки

\mathfrak e_j = \overbrace{[\underbrace{0,\dots,0,1}_j,0,\dots \,0]}^n \quad npu \ j \in \{1,\dots,n\} \ .

5. Если скалярное произведение в \mathbb V^n определить по аналогии с \mathbb R^{3}:

\langle (x_1,\dots,x_n),(y_1,\dots,y_n)\rangle =x_1y_1+\dots+x_ny_n \pmod{2} \ ,

то существуют ненулевые векторы X\in \mathbb V^n, ортогональные самим себе:

\langle (1,1,0), (1,1,0) \rangle =2 \equiv 0 \pmod{2} \ .

6. Пусть теперь во множестве \mathbb V^n определена операция умножения элементов по правилу, изложенному ЗДЕСЬ. Для векторов

\mathfrak a=(a_0,a_1,\dots,a_{n-1}) \quad и \quad \mathfrak b=(b_0,b_1,\dots,b_{n-1})

их произведение определяется как элемент

\mathfrak c=(c_0,c_1,\dots,c_{n-1}) ,

такой, что

c_0x^{n-1}+c_1x^{n-2}+\dots+c_{n-1} \equiv
\equiv (a_0x^{n-1}+a_1x^{n-2}+\dots+a_{n-1})(b_0x^{n-1}+b_1x^{n-2}+\dots+b_{n-1}) \quad (\operatorname{modd} \ 2,f(x)) ;

что означает: после выполнения умножения полиномов, мы вычисляем остаток этого произведения при делении его на некоторый полином f_{}(x) степени n_{} с коэффициентами из \{0,1\} , и, вдобавок, неприводимый над \mathbf{GF}(2); коэффициенты остатка приводятся по модулю 2_{}. Иными словами из линейного пространства \mathbb V^n сделали поле Галуа \mathbf{GF}(2^n). Существует элемент \mathfrak a_{} поля \mathbf{GF}(2^n) такой, что элементы поля

\mathfrak a, \mathfrak a^2, \mathfrak a^4,\dots, \mathfrak a^{2^{n-1}}

(каждый следующий является квадратом предыдущего) образуют базис пространства \mathbb V^n. Любой такой базис называется нормальным базисом.

П

Пример. Для поля \mathbf{GF}(2^4), порожденному полиномом f(x)=x^4+x+1 элемент \mathfrak a = (1,0,0,0) порождает нормальный базис. Действительно, указанному элементу соответствует полином x^3 и

\left(x^3\right)^2=x^6 \equiv x^3+x^2 \quad (\operatorname{modd} \ 2,f(x)),\ (x^3+x^2)^2 \equiv x^6+x^4 \equiv x^3+x^2+x+1 \quad (\operatorname{modd} \ 2,f(x)),
(x^3+x^2+x+1)^2 \equiv x^3+x \quad (\operatorname{modd} \ 2,f(x)) \ .

Векторы

(1,0,0,0),\ (1,1,0,0),\ (1,1,1,1),\ (1,0,1,0)

линейно независимы. В том же поле элемент (0,0,1,0) не порождает нормальный базис.

1) Можно рассматривать и столбцы — это непринципиально.
2) cardinalis (лат.) — 1) количественный; 2) главный, основной; 3) кардинал.

2018/02/17 09:09 редактировал au