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

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

Định nghĩa 3.39 (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ụ 3.1 (Biểu diễn hoán vị bằng ma trận)

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).\]

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

Định nghĩa 3.40 (Hai mã tương đương hoán vị)

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 3.41 (Hai ma trận tương đương hoán vị)

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 \bm{P}_\sigma\).

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

Định nghĩa 3.42 (Nhóm tự đẳng cấu hoán vị)

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}\).

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

Định nghĩa 3.43 (Bài toán tương đương mã tuyến tính)

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\).

3.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 3.44 (Ma trận liên thuộc)

Ma trận liên thuộc (hay incidence matrix) là ma trận nhị phân \(\bm{D} = (d_{ev})\) cỡ \(\lvert E \rvert \times \lvert V \rvert\), với \(d_{ev} = 1\) khi và chỉ khi cạnh \(e\) kề với đỉnh \(v\); các phần tử còn lại bằng \(0\).

Ta sử dụng định nghĩa đẳng cấu đồ thị sau đây.

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 3.45 (Bài toán đẳng cấu đồ thị)

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\).