# Invariants

## The Standard Form

A ${\mathbb{Z}}_4$-linear code is in *standard form* if its generator matrix is of the form:

$$
\begin{pmatrix}I_{k_1} & A        & B \\ 0       & 2I_{k_2} & 2C\end{pmatrix}
$$

where $I_{k_1}$ and $I_{k_2}$ are the $k_1\times k_1$ and $k_2\times k_2$ identity matrices, respectively, $A$ and $C$ are ${\mathbb{Z}}_2$-matrices, and $B$ is a ${\mathbb{Z}}_4$-matrix. Any ${\mathbb{Z}}_4$-linear code $C$ is permutation-equivalent to a code $S$ which is in standard form. Furthermore, the integers $k_1$ and $k_2$, defined above, are unique [[Wan, 1997](../../references.md#cite-wan-z4), Prop. 1.1].

### `StandardForm(C): Code -> Code, Map`

This function, given any ${\mathbb{Z}}_4$-linear code $C$, returns a permutation-equivalent code $S$ in standard form, together with the corresponding isomorphism from $C$ onto $S$.

### `Example: Standard Form (ex-48fad2)`

The standard form is computed for a small ${\mathbb{Z}}_4$ code. Note that the number of rows in the generator matrix of the standard code may be less than that in the original code.

```magma
> Z4 := IntegerRing(4);
> C := LinearCode<Z4, 4 | [2,2,1,1], [0,2,0,2]>;
> C;
[4, 3, 2] Linear Code over IntegerRing(4)
Generator matrix:
[2 0 1 3]
[0 2 0 2]
[0 0 2 2]
> S, f := StandardForm(C);
> S;
[4, 2, 2] Linear Code over IntegerRing(4)
Generator matrix:
[1 1 2 2]
[0 2 2 0]
> #S;
8
> #C;
8
> f(C.1);
(1 3 0 2)
> f(C.2);
(0 2 2 0)
> f(C.3);
(2 2 0 0)
> S.1@@f;
(2 2 1 1)
> S.2@@f;
(0 2 0 2)

```

### `StandardFormDual(C): CodeLinRng -> CodeLinRng, Map`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, return the dual of a permutation-equivalent code $S$ in standard form, together with the corresponding isomorphism from the dual of $C$ onto the dual of $S$. Since $S$ is generated by a matrix of the form

$$
\begin{pmatrix}I_{k_1} & A        & B \\ 0       & 2I_{k_2} & 2C\end{pmatrix}
$$

the dual of $S$ is generated by the matrix

$$
\begin{pmatrix}-(AC+B)^t & C^t & I_{n-k_1-k_2} \\ 2A^t & 2I_{k_2} & 0\end{pmatrix}
$$

where $I_{k_1}$ and $I_{k_2}$ are the $k_1 \times k_1$ and $k_2 \times k_2$ identity matrices, respectively, $A$ and $C$ are ${\mathbb{Z}}_2$-matrices, and $B$ is a ${\mathbb{Z}}_4$-matrix.

## Structures Associated with the Gray Map

### `MinRowsGeneratorMatrix(C): CodeLinRng -> ModMatRngElt`

A generator matrix for the code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, with the minimum number of rows, that is with $\gamma + \delta$ rows: $\gamma$ rows of order two and $\delta$ rows of order four. It also returns the parameters $\gamma$ and $\delta$.

### `MinRowsParityCheckMatrix(C): CodeLinRng -> ModMatRngElt`

A parity check matrix for the code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, with the minimum number of rows, that is, with $\gamma$ rows of order two and $n-\gamma-\delta$ rows of order four. This function should be faster for most codes over ${\mathbb{Z}}_4$ than the general function `ParityCheckMatrix(C)` for codes over finite rings. Another parity check matrix for the code $C$ can be obtained as the generator matrix of the dual of $C$ with the minimum number of rows, that is, as `MinRowsGeneratorMatrix(DualZ4(C))`.

### `DualZ4(C): CodeLinRng -> CodeLinRng`

The dual $D$ of the code $C$ over ${\mathbb{Z}}_4$ of length $n$. The dual consists of all codewords in the ${\mathbb{Z}}_4$-space $V={\mathbb{Z}}_4^n$ which are orthogonal to all codewords of $C$. This function should be faster for most codes over ${\mathbb{Z}}_4$ than the general function `Dual(C)` for codes over finite rings.

### `Example: New Invar (ex-3b2558)`

```magma
> C := HadamardCodeZ4(3, 11);
> G, gamma, delta := MinRowsGeneratorMatrix(C);
> Nrows(G) eq gamma + delta;
true
> deltaH := Length(C) - gamma - delta;
> H1 := MinRowsParityCheckMatrix(C);
> Nrows(H1) eq gamma + deltaH;
true
> H2 := MinRowsGeneratorMatrix(DualZ4(C));
> Nrows(H2) eq gamma + deltaH;
true

> time D := Dual(C);
Time: 24.660
> time D4 := DualZ4(C);
Time: 0.340
> D eq D4, D4 eq LinearCode(H1), D4 eq LinearCode(H2);
true true true

> DualS, f := StandardFormDual(C);
> DualS eq LinearCode(Matrix([f(H1[i]) : i in [1..Nrows(H1)]]));
true

```

### `SpanZ2CodeZ4(C): CodeLinRng -> CodeLinFld`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, return $S_C=\Phi^{-1}(S_{bin})$ as a code over ${\mathbb{Z}}_4$, and the linear span of $C_{bin}$, $S_{bin}=\langle C_{bin} \rangle$, as a binary linear code of length $2n$, where $C_{bin}=\Phi(C)$ and $\Phi$ is the Gray map.

### `KernelZ2CodeZ4(C): CodeLinRng -> CodeLinRng`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, return its kernel $K_C$ as a subcode over ${\mathbb{Z}}_4$ of $C$, and $K_{bin}=\Phi(K_C)$ as a binary linear subcode of $C_{bin}$ of length $2n$, where $C_{bin}=\Phi(C)$ and $\Phi$ is the Gray map.

The kernel $K_C$ contains the codewords $v$ such that $2v*u \in C$ for all $u \in C$, where $*$ denotes the component-wise product. Equivalently, the kernel $K_{bin}=\Phi(K_C)$ contains the codewords $c\in C_{bin}$ such that $c+C_{bin}=C_{bin}$, where $C_{bin}=\Phi(C)$ and $\Phi$ is the Gray map.

### `KernelCosetRepresentatives(C): CodeLinRng -> SeqEnum, SeqEnum`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, return the coset representatives $[c_1,\ldots, c_t]$ as a sequence of codewords of $C$, such that $C=K_C \cup \bigcup_{i=1}^t \big( K_C+c_i \big)$, where $K_C$ is the kernel of $C$ as a subcode over ${\mathbb{Z}}_4$. It also returns the coset representatives of the corresponding binary code $C_{bin}=\Phi(C)$ as a sequence of binary codewords $[\Phi(c_1), \ldots, \Phi(c_t)]$, such that $C_{bin}=K_{bin} \cup \bigcup_{i=1}^t \big( K_{bin}+\Phi(c_i)\big)$, where $K_{bin}=\Phi(K_C)$ and $\Phi$ is the Gray map.

### `DimensionOfSpanZ2(C): CodeLinRng -> RngIntElt`

### `RankZ2(C): CodeLinRng -> RngIntElt`

Given a code $C$ over ${\mathbb{Z}}_4$, return the dimension of the linear span of $C_{bin}$, that is, the dimension of $\langle C_{bin} \rangle$, where $C_{bin}=\Phi(C)$ and $\Phi$ is the Gray map.

### `DimensionOfKernelZ2(C): CodeLinRng -> RngIntElt`

Given a code $C$ over ${\mathbb{Z}}_4$, return the dimension of the Gray map image of its kernel $K_C$ over ${\mathbb{Z}}_4$, that is the dimension of $K_{bin}=\Phi(K_C)$, where $\Phi$ is the Gray map. Note that $K_{bin}$ is always a binary linear code.

### `Example: Spain Z4 5 (ex-bb9d15)`

```magma
> C := ReedMullerCodeRMZ4(0,3,5);
> DimensionOfKernelZ2(C);
20
> DimensionOfSpanZ2(C);
27
> K, Kb := KernelZ2CodeZ4(C);
> S, Sb := SpanZ2CodeZ4(C);
> K subset C;
true
> C subset S;
true
> Dimension(Kb) eq DimensionOfKernelZ2(C);
true
> Dimension(Sb) eq DimensionOfSpanZ2(C);
true

```

## Coset Representatives

### `CosetRepresentatives(C): CodeLinRng -> SeqEnum`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, with ambient space $V={\mathbb{Z}}_4^n$, return a set of coset representatives (not necessarily of minimal weight in their cosets) for $C$ in $V$ as an indexed set of vectors from $V$. The set of coset representatives $\{c_0, c_1, \ldots, c_t \}$ satisfies the two conditions that $c_0$ is the zero codeword, and $V=\bigcup_{i=0}^t \big( C+c_i \big)$. Note that this function is only applicable when $V$ and $C$ are small.

### `CosetRepresentatives(C, S): CodeLinRng, CodeLinRng -> SeqEnum, SeqEnum`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, and a subcode $S$ over ${\mathbb{Z}}_4$ of $C$, return a set of coset representatives (not necessarily of minimal weight in their cosets) for $S$ in $C$ as an indexed set of codewords from $C$. The set of coset representatives $\{c_0, c_1, \ldots, c_t \}$ satisfies the two conditions that $c_0$ is the zero codeword, and $C= \bigcup_{i=0}^t \big( S+c_i \big)$. Note that this function is only applicable when $S$ and $C$ are small.

### `Example: Spain Z4 7 (ex-551655)`

```magma
> C := LinearCode<Integers(4), 4 | [[1,0,0,3],[0,1,1,3]]>;
> L := CosetRepresentatives(C);
> Set(RSpace(Integers(4),4)) eq {v+ci : v in Set(C), ci in L};
true

> K := KernelZ2CodeZ4(C);
> L := CosetRepresentatives(C, K);
> {C!0} join Set(KernelCosetRepresentatives(C)) eq L;
true
> Set(C) eq {v+ci : v in Set(K), ci in L};
true

```

## Information Space and Information Sets

### `InformationSpace(C): CodeLinRng -> ModTupRng, ModTupFld, Map, Map`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, return the ${\mathbb{Z}}_4$-submodule of ${\mathbb{Z}}_4^{\gamma+\delta}$ isomorphic to ${\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^\delta$ such that the first $\gamma$ coordinates are of order two, that is, the space of information vectors for $C$. The function also returns the $(\gamma+2\delta)$-dimensional binary vector space, which is the space of information vectors for the corresponding binary code $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map. Finally, for the encoding process, it also returns the corresponding isomorphisms $f$ and $f_{bin}$ from these spaces of information vectors onto $C$ and $C_{bin}$, respectively.

### `Example: Spain Z4 9 (ex-5fc04a)`

```magma
> C := LinearCode<Integers(4), 4 | [[2,0,0,2],[0,1,1,3]]>;
> R, V, f, fbin := InformationSpace(C);
> G := MinRowsGeneratorMatrix(C);

> (#R eq #C) and (#V eq #C);
true
> Set([f(i) : i in R]) eq Set(C);
true
> Set([i*G : i in R]) eq Set(C);
false

> i := R![2,3];
> c := f(i);
> c;
(2 3 3 3)
> c in C;
true
> i*G eq c;
false

> ibin := V![1,1,0];
> cbin := fbin(ibin);
> cbin;
(1 1 1 0 1 0 1 0)
> cbin in GrayMapImage(C);
true
> cbin eq GrayMap(C)(c);
true

```

### `InformationSet(C): CodeLinRng -> ModTupRng, ModTupFld, Map, Map`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, return an information set $I=[i_1,\ldots,i_{\gamma+\delta}] \subseteq \{1,\ldots,n\}$ for $C$ such that the code $C$ punctured on $\{1,\ldots,n\} \backslash \{i_{\gamma+1},\ldots, i_{\gamma+\delta} \}$ is of type $4^\delta$, and the corresponding information set $\Phi(I)=[2i_1-1,\ldots, 2i_\gamma-1, 2i_{\gamma+1}-1, 2i_{\gamma+1},  \ldots, 2i_{\gamma+\delta}-1, 2i_{\gamma+\delta}] \subseteq \{1,\ldots,2n\}$ for the binary code $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map. The information sets $I$ and $\Phi(I)$ are returned as a sequence of $\gamma+\delta$ and $\gamma+2\delta$ integers, giving the coordinate positions that correspond to the information set of $C$ and $C_{bin}$, respectively.

An information set $I$ for $C$ is an ordered set of $\gamma+\delta$ coordinate positions such that $|C^I|=2^{\gamma}4^\delta$, where $C^I=\{v^I : v\in C \}$ and $v^I$ is the vector $v$ restricted to the $I$ coordinates. An information set $J$ for $C_{bin}$ is an ordered set of $\gamma+2\delta$ coordinate positions such that $|{C^{J}_{bin}}|=2^{\gamma+2\delta}$.

### `IsInformationSet(C, I): CodeLinRng, [RngIntElt] -> BoolElt, BoolElt`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$ and a sequence $I \subseteq \{1,\ldots,n \}$ or $I \subseteq \{1,\ldots,2n \}$, return `true` if and only if $I\subseteq \{1,\ldots,n \}$ is an information set for $C$. This function also returns another boolean, which is `true` if and only if $I \subseteq \{1,\ldots,2n \}$ is an information set for the corresponding binary code $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map.

An information set $I$ for $C$ is an ordered set of $\gamma+\delta$ coordinate positions such that $|C^I|=2^{\gamma}4^\delta$, where $C^I=\{v^I : v\in C \}$ and $v^I$ is the vector $v$ restricted to the $I$ coordinates. An information set $J$ for $C_{bin}$ is an ordered set of $\gamma+2\delta$ coordinate positions such that $|{C^{J}_{bin}}|=2^{\gamma+2\delta}$.

### `Example: Spain Z4 10 (ex-1d41b7)`

```magma
> C := HadamardCodeZ4(3,6);
> C;
((32, 4^3 2^1)) Linear Code over IntegerRing(4)
Generator matrix:
[1 0 3 2 0 3 2 1 3 2 1 0 2 1 0 3 1 0 3 2 0 3 2 1 3 2 1 0 2 1 0 3]
[0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3]
[0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

> I, Ibin := InformationSet(C);
> I;
[ 16, 28, 31, 32 ]
> Ibin;
[ 31, 55, 56, 61, 62, 63, 64 ]
> #PunctureCode(C, {1..32} diff Set(I)) eq #C;
true
> Cbin := GrayMapImage(C);
> V := VectorSpace(GF(2), 7);
> #{V![c[i] : i in Ibin] : c in Cbin} eq #Cbin;
true

> IsInformationSet(C, I);
true false
> IsInformationSet(C, Ibin);
false true

> IsInformationSet(C, [1, 2, 5, 17]);
true false
> IsInformationSet(C, [1, 2, 3, 4, 9, 10, 33]);
false true

> D := LinearCode<Integers(4), 5 | [[2,0,0,2,0],[0,2,0,2,2],[0,0,2,2,0]]>;
> IsInformationSet(D, [1,3,5]);
true true

```

## Syndrome Space and Coset Leaders

### `SyndromeSpace(C): CodeLinRng -> ModTupRng, ModTupFld`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, return the ${\mathbb{Z}}_4$-submodule of ${\mathbb{Z}}_4^{n-\delta}$ isomorphic to ${\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^{n-\gamma-\delta}$ such that the first $\gamma$ coordinates are of order two, that is, the space of syndrome vectors for $C$. The function also returns the $(2n-2\delta-\gamma)$-dimensional binary vector space, which is the space of syndrome vectors for the corresponding binary code $C_{bin}=\Phi(C)$, where $\Phi$ is the Gray map. Note that these spaces are computed by using the function `InformationSpace(C)` applied to the dual code of $C$, produced by function `DualZ4(C)`.

### `Syndrome(u, C): ModTupFldElt, CodeLinRng -> ModTupRngElt`

### `Syndrome(u, C): ModTupRngElt, CodeLinRng -> ModTupRngElt`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$ and type $2^\gamma 4^\delta$, and a vector $u$ from the ambient space $V={\mathbb{Z}}_4^n$ or $V_2={\mathbb{Z}}_2^{2n}$, construct the syndrome of $u$ relative to the code $C$. This will be an element of the syndrome space of $C$, considered as the ${\mathbb{Z}}_4$-submodule of ${\mathbb{Z}}_4^{n-\delta}$ isomorphic to ${\mathbb{Z}}_2^\gamma \times {\mathbb{Z}}_4^{n-\gamma-\delta}$ such that the first $\gamma$ coordinates are of order two.

### `CosetLeaders(C): CodeLinRng -> SetIndx, Map`

Given a code $C$ over ${\mathbb{Z}}_4$ of length $n$, with ambient space $V={\mathbb{Z}}_4^{n}$, return a set of coset leaders (vectors of minimal Lee weight in their cosets) for $C$ in $V$ as an indexed set of vectors from $V$. This function also returns a map from the syndrome space of $C$ onto the coset leaders (mapping a syndrome into its corresponding coset leader). Note that this function is only applicable when $V$ and $C$ are small.

### `Example: Spain Z4 11 (ex-5bce83)`

```magma
> C := LinearCode<Integers(4), 4 | [[2,0,0,2],[0,1,1,3]]>;
> R, V, f, fbin := InformationSpace(C);
> Rs, Vs := SyndromeSpace(C);

> #R * #Rs eq 4^Length(C);
true
> #V * #Vs eq 4^Length(C);
true

> i := R![2,3];
> c := f(i);
> c;
(2 3 3 3)
> u := c;
> u[2] := u[2] + 3;
> u;
(2 2 3 3)

> s := Syndrome(u, C);
> s in Rs;
true
> H := Transpose(MinRowsGeneratorMatrix(Dual(C)));
> s eq u*H;
true

> L, mapCosetLeaders := CosetLeaders(C);
> ev := mapCosetLeaders(s);
> ev;
(0 3 0 0)
> ev in L;
true
> u - ev eq c;
true

```

## Miscellaneous Functions

### `Correlation(v): ModTupRngElt -> RngQuadElt`

Let $v$ be a codeword over ${\mathbb{Z}}_4$. Define $w_j = \#\{k : v[k] = j\}$ for $j = 0,\ldots,3$. Then the *correlation* of $v$ is the Gaussian integer $(w_0 - w_2) + i*(w_1 - w_3)$.