# Invariants of a Code

## Basic Numerical Invariants

### `Length(C): Code -> RngIntElt`

Given an $[n, k]$ code $C$, return the block length $n$ of $C$.

### `Dimension(C): Code -> RngIntElt`

### `NumberOfGenerators(C): Code -> RngIntElt`

The dimension $k$ of the $[n, k]$ linear code $C$.

### `# C: Code -> RngIntElt`

Given a code $C$, return the number of codewords belonging to $C$.

### `InformationRate(C): Code -> FldPrElt`

The information rate of the $[n, k]$ code $C$. This is the ratio $k/n$.

## The Ambient Space and Alphabet

### `AmbientSpace(C): Code -> ModTupRng`

The ambient space of the code $C$, i.e. the generic $R$-space $V$ in which $C$ is contained.

### `RSpace(C): Code -> ModTupRng`

### `VectorSpace(C): Code -> ModTupFld`

Given an $[n, k]$ linear code $C$, defined as a subspace $U$ of the $n$-dimensional space $V$, return $U$ as a subspace of $V$ with basis corresponding to the rows of the generator matrix for $C$.

### `Generic(C): Code -> Code`

Given an $[n, k]$ code $C$, return the generic $[n, n, 1]$ code in which $C$ is contained.

### `Alphabet(C): Code -> Rng`

### `Field(C): Code -> Rng`

The underlying ring (or alphabet) $R$ of the code $C$.

## The Code Space

### `GeneratorMatrix(C): Code -> ModMatFldElt`

### `BasisMatrix(C): Code -> ModMatRngElt`

The generator matrix for the linear code $C$, returned as an element of ${\operatorname{Hom}}(U, V)$ where $U$ is the information space of $C$ and $V$ is the ambient space of $C$.

### `Basis(C): Code -> [ ModTupRngElt ]`

The current vector space basis for the linear code $C$, returned as a sequence of elements of $C$.

### `Generators(C): Code -> { ModTupFldElt }`

The current vector space basis for the linear code $C$, returned as a set of elements of $C$.

### `C . i: Code, RngIntElt -> ModTupFldElt`

Given an $[n, k]$ code $C$ and a positive integer $i$, $1 \le i \le k$, return the $i$-th element of the current basis of $C$.

## The Dual Space

### `Dual(C): Code -> Code`

The code that is dual to the code $C$.

### `ParityCheckMatrix(C): Code -> ModMatFldElt`

The parity check matrix for the code $C$, returned as an element of ${\operatorname{Hom}}(V, U)$.

### `Example: Generator Matrix (ex-7ec540)`

We create a Reed–Muller code and demonstrate some simple relations.

```magma
> R := ReedMullerCode(1, 3);
> R;
[8, 4, 4] Reed-Muller Code (r = 1, m = 3) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0]
[0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1]
> G := GeneratorMatrix(R);
> P := ParityCheckMatrix(R);
> P;
[1 0 0 1 0 1 1 0]
[0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1]
> G * Transpose(P);
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
[0 0 0 0]
> D := LinearCode(P);
> Dual(R) eq D;
true

```

### `Hull(C): Code -> Code`

The Hull of a code is the intersection between itself and its dual.

## The Information Space and Information Sets

### `InformationSpace(C): Code -> ModTupFld`

Given an $[n, k]$ linear code $C$, return the $k$-dimensional $R$-space $U$ which is the space of information vectors for the code $C$.

### `InformationSet(C): Code -> [ RngIntElt ]`

Given an $[n, k]$ linear code $C$ over a finite field, return the current information set for $C$. The information set for $C$ is an ordered set of $k$ linearly independent columns of the generator matrix, such that the generator matrix is the identity matrix when restricted to these columns. The information set is returned as a sequence of $k$ integers, giving the numbers of the columns that correspond to the information set.

### `AllInformationSets(C): Code -> [ [ RngIntElt ] ]`

Given an $[n, k]$ linear code $C$ over a finite field, return all the possible information sets of $C$ as a (sorted) sequence of sequences of column indices. Each inner sequence contains a maximal set of indices of linearly independent columns in the generator matrix of $C$.

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

Given an $[n, k]$ linear code $C$ over a finite field, return the standard form $D$ of $C$. A code is in *standard form* if the first $k$ components of the code words correspond to the information set. Magma returns one of the many codes in standard form which is isomorphic to $C$. (The same code is returned each time.) Thus, the effect of this function is to return a code $D$ whose generators come from the generator matrix of $C$ with its columns permuted, so that the submatrix consisting of the first $k$ columns of the generator matrix for $D$ is the identity matrix. Two values are returned: The standard form code $D$;

**(b)**
An isomorphism from $C$ to $D$.

### `Example: Standard Form (ex-8132b6)`

We construct a Reed–Muller code $C$ and its standard form $S$ and then map a codeword of $C$ into $S$.

```magma
> C := ReedMullerCode(1, 4);
> C;
[16, 5, 8] Reed-Muller Code (r = 1, m = 4) over GF(2)
Generator matrix:
[1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1]
[0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1]
[0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1]
> InformationSet(C);
[ 1, 2, 3, 5, 9 ]
> #AllInformationSets(C);
2688
> S, f := StandardForm(C);
> S;
[16, 5, 8] Linear Code over GF(2)
Generator matrix:
[1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1]
[0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1]
[0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 1]
[0 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1]
[0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1]
> u := C.1;
> u;
(1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1)
> f(u);
(1 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1)

```

## The Syndrome Space

### `SyndromeSpace(C): Code -> ModTupFld`

Given an $[n, k]$ linear code $C$, return the $(n-k)$-dimensional vector space $W$, which is the space of syndrome vectors for the code $C$.

## The Generator Polynomial

The operations in this section are restricted to cyclic codes.

### `GeneratorPolynomial(C): Code -> RngUPolElt`

Given a cyclic code $C$ over a finite field, return the generator polynomial of $C$. The generator polynomial of $C$ is a divisor of $x^n - 1$, where $n$ is the length of $C$.

### `CheckPolynomial(C): Code -> RngUPolElt`

Given a cyclic code $C$ over a finite field, return the check polynomial of $C$ as an element of $K[x]$. If $g(x)$ is the generator polynomial of $C$ and $h(x)$ is the check polynomial of $C$, then $g(x)h(x) = 0$ (mod $x^n - 1$), where $n$ is the length of $C$.

### `Idempotent(C): Code -> RngUPolElt`

Given a cyclic code $C$, return the (polynomial) idempotent of $C$. If $c(x)$ is the idempotent of $C$, then $c(x)^{2} = c(x)$ (mod $x^n - 1$), where $n$ is the length of $C$.

### `Example: Generator Polynomial (ex-889cde)`

We find the generator and check polynomials for the third order Hamming code over GF(2).

```magma
> K<w> := GF(2);
> P<x> := PolynomialRing(K);
> H := HammingCode(K, 3);
> g := GeneratorPolynomial(H);
> g;
x^3 + x + 1
> h := CheckPolynomial(H);
> h;
x^4 + x^2 + x + 1
> g*h mod (x^7 - 1);
0
> forall{ c : c in H | h * P!Eltseq(c) mod (x^7-1) eq 0 };
true
> e := Idempotent(H);
> e;
x^4 + x^2 + x
> e^2;
x^8 + x^4 + x^2

```