2.6. Bài toán tương đương các linear code¶

2.6.1. Hoán vị và tác động của chúng lên tập hợp¶

Định nghĩa 2.75 (Hoán vị)

Xét \(N\) là tập hợp có \(n\) phần tử. Khi đó một hoán vị (hay permutation, постановка) \(\sigma: N \to N\) là một song ánh từ \(N\) tới \(N\).

Tập hợp tất cả hoán vị trên tập \(N\) được kí hiệu là \(\mathcal{S}_N\). Nếu \(N = \{ 1, 2, \ldots, n \}\) thì ta có thể viết \(\mathcal{S}_N = \mathcal{S}_n\).

Đặt \(\sigma \in \mathcal{S}_n\) là một hoán vị trên tập \(\{ 1, \ldots, n \}\). Khi đó ta định nghĩa tác động của hoán vị \(\sigma\) lên vector \(\bm{x} \in V_n(q)\). Giả sử vector \(\bm{x} = (x_1, \ldots, x_n) \in V_n(q)\), ta định nghĩa tác động của hoán vị \(\sigma\) lên vector \(\bm{x}\) như sau:

\[\bm{x}^\sigma = (x_{\sigma(1)}, x_{\sigma(2)}, \ldots, x_{\sigma(n)}).\]

Có thể thấy tác động của \(\sigma\) lên \(V_n(q)\) là tuyến tính, nghĩa là với mọi \(\alpha, \beta \in \mathbb{F}_q\) và với mọi vector \(\bm{x}, \bm{y} \in V_n(q)\) ta có:

\[(\alpha \cdot \bm{x} + \beta \cdot \bm{y})^\sigma = \alpha \cdot \bm{x}^\sigma + \beta \cdot \bm{y}^\sigma.\]

Nếu \(U \subseteq V_n(q)\) thì kí hiệu \(U^\sigma\) là tác động của hoán vị \(\sigma\) lên mỗi vector trong \(U\), nghĩa là \(U^\sigma = \{ \bm{x}^\sigma : \bm{x} \in U \}\).

Do tính tuyến tính của tác động từ \(\mathcal{S}_n\) lên \(V_n(q)\), nếu \(\mathcal{C}\) là \([n, k, d]_q\) code thì \(\mathcal{C}^\sigma\) cũng là \([n, k, d]_q\) code.

Mỗi hoán vị \(\sigma \in \mathcal{S}_n\) có thể được viết thành dạng ma trận \(n \times n\) là \(\bm{P}_\sigma = (p_{ij})\). Khi đó phần tử \(p_{ij} = 1\) nếu \(\sigma(j) = i\), các vị trí còn lại bằng \(0\).

Ví dụ 2.21

Với hoán vị \(\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 1 & 5 & 3 & 2 \end{pmatrix}\) thì ma trận tương ứng là:

\[\begin{split}\bm{P}_\sigma = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}.\end{split}\]

Khi đó tác động của \(\sigma\) lên vector \(\bm{x}\) là \(\bm{x}^\sigma = \bm{x} \cdot \bm{P}_\sigma\).

Như vậy, với mọi vector \(\bm{x} = (x_1, x_2, x_3, x_4, x_5)\), dưới tác động của \(\sigma\) bên trên ta có:

\[\bm{x}^\sigma = (x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}, x_{\sigma(4)}, x_{\sigma(5)}) = (x_4, x_1, x_5, x_3, x_2).\]

Ta cũng thấy phép nhân vector \(\bm{x}\) với ma trận \(\bm{P}_\sigma\) cho kết quả:

\[\bm{x} \cdot \bm{P}_\sigma = (x_4, x_1, x_5, x_3, x_2).\]

2.6.2. Mã tương đương và nhóm các tự đẳng cấu của linear code¶

Định nghĩa 2.76

Hai \([n]_q\) code \(\mathcal{C}_1\) và \(\mathcal{C}_2\) được gọi là tương đương (hay tương đương hoán vị, перестановочно эквивалентные) nếu tồn tại một hoán vị \(\sigma \in \mathcal{S}_n\) sao cho \(\mathcal{C}_1 = \mathcal{C}_2^\sigma\).

Định nghĩa 2.77

Hai ma trận \(\bm{G}_1\) và \(\bm{G}_2\) kích thước \(k \times n\) gọi là tương đương hoán vị nếu tồn tại ma trận \(\bm{M}\) cỡ \(k \times k\) và hoán vị \(\sigma \in \mathcal{S}_n\) sao cho \(\bm{M} \cdot \bm{G}_1 = \bm{G}_2 \cdot \sigma\).

2.6.3. Nhóm các tự đẳng cấu của code¶

Định nghĩa 2.78

Tự đẳng cấu của \((n)_q\) code \(\mathcal{C}\) là hoán vị \(\sigma\) sao cho \(\mathcal{C} = \mathcal{C}^\sigma\). Tập hợp tất cả tự đẳng cấu của code \(\mathcal{C}\) được kí hiệu là nhóm \(\mathrm{PAut}(\mathcal{C})\) và được gọi là nhóm tự đẳng cấu hoán vị hoặc đơn giản hơn là nhóm tự đẳng cấu của code \(\mathcal{C}\).

2.6.4. Bài toán về tính tương đương giữa các linear code nhị phân¶

Định nghĩa 2.79

Bài toán về tính tương đương giữa các linear code là bài toán nhận dạng tính chất tương đương giữa hai linear code \([n]_q\) \(\mathcal{C}_1\) và \(\mathcal{C}_2\) với ma trận sinh tương ứng là \(\bm{G}_1\) và \(\bm{G}_2\).

Input: hai ma trận \(\bm{G}_1\) và \(\bm{G}_2\) cỡ \(k \times n\).

Output: hai ma trận \(\bm{G}_1\) và \(\bm{G}_2\) có tương đương hoán vị hay không.

Sau đây chúng ta xem xét code nhị phân, tức \(q = 2\).

2.6.5. Định lí về polynomial-time reduction của bài toán đẳng cấu đồ thị đến bài toán sự tương đương của code¶

Định nghĩa 2.80

Ma trận kề (hay матрица инцидентности) là ma trận nhị phân \(\bm{D} = (d_{ev})\) cỡ \(\lvert E \rvert \times \lvert V \rvert\), với \(d_{ev} = 1\) nếu \(e = (u, v)\) với \(v\) nào đó thuộc \(V\), nghĩa là \(d_{ev} = 1\) khi và chỉ khi trên đồ thị có cạnh \(e\) xuất phát từ đỉnh \(v\).

Định nghĩa về sự đẳng cấu của hai đồ thị đã được giới thiệu ở Định nghĩa 29, ở đây mình giới thiệu lại.

Quan trọng

Đồ thị đẳng cấu

Hai đồ thị \((E_1, V_1)\) và \((E_2, V_2)\) được gọi là đẳng cấu (hay isomorphism) nếu tồn tại song ánh \(\varphi : V_1 \to V_2\) sao cho với mọi cặp đỉnh \((u, v) \in E_1\) thì cặp \((\varphi(u), \varphi(v)) \in E_2\).

Định nghĩa 2.81

Bài toán xác định hai đồ thị, xác định bởi ma trận kề, có đẳng cấu với nhau hay không.

Input: hai ma trận nhị phân \(\bm{D}_1\) và \(\bm{D}_2\) cỡ \(k \times n\).

Output: có tồn tại hay không các hoán vị \(\gamma \in \mathcal{S}_k\) và \(\sigma \in \mathcal{S}_n\) sao cho \(\bm{D}_1 = \gamma \cdot \bm{D}_2 \cdot \sigma\).