The code supports reading matrices from an MTX file using ReadMTXE and writing new MTX file using WriteMTXE functions. Below a description of the format is given.
Every finite field is isomorphic to a Galois field \(F=\mathop{\rm GF}(q)\), where \(q\) is a power of a prime, \(q=p^m\).
For a prime field, with \(q=p\) a prime, \(F\) is a prime field, isomorphic to the ring Z\((q)\) of integers modulo \(q\). In such a case, elements of the field are stored directly as integers. After reading, these are taken modulo \(p\), thus, e.g., with \(p=7\), values \(-1\), \(6\), or \(13\) are all equivalent.
When \(q=p^m\) with \(m > 1\), \(F\) is an extension field. Non-zero elements of such a field can be represented as integer powers of a primitive element \(\alpha\), a primitive root of unity in the field. Primitive element is a root of a primitive polynomial \(f(x)\), that is, an irreducible polynomial with coefficients in the corresponding prime field \(\mathop{\rm GF}(p)\), with the property that the smallest integer \(n\) such that \(f(x)\) divides \(x^n-1\) is \(n=p^m-1\). Alternatively, field elements can be represented as \(p\)-ary polynomials modulo the chosen primitive polynomial \(f(x)\).
Either definition requires that the primitive polynomial be specified. By default, GAP uses Conway polynomials to represent field elements. For details, as well as a large collection of Conway polynomials, please see the web page maintained by Frank Luebeck [L\t21].
In the actual file format, three different and mutually exclusive storage options for elements of an extension field can in be used.
First, assuming all elements needed are actually in the corresponding prime field \(\mathop{\rm GF}(p)\), the integer values (mod \(p\)) directly correspond to the values of field elements. This is the case, e.g., with \(0,\pm1\) matrices which obey the orthogonality condition already over integers, and retain orthogonality over Z\((q)\) with any \(q\) (what is more relevant here, the same matrix would work with any prime field). (this is currently not implemented)
Second option, and the only option currently implemented for extension fields, is to store the powers of the primitive element for each non-zero element in the field, and \(-1\) for zero.
Third option, is to take the coefficients of \(p\)-ary polynomial \(a_0+a_1x+a_2x^2+\ldots +a_{m-1}x^{m-1}\) as digits of a \(p\)-ary integer \((a_{m-1}a_{m-2}\ldots a_2a_1)_p\). (this is currently not implemented)
There are two recommended storage formats.
1. For CSS matrices stored in separate files, the MTX header should use the integer type, with matrix elements stored in the usual order.
2. For general stabilizer codes, or to store both CSS matrices in a single file, the MTX header should use the complex type. In this case the block matrix \((A,B)\) is stored as a complex matrix \(A+iB\).
In both format versions, the number of columns specified in the file coincides with the code length.
Two additional matrix format versions supported by ReadMTXE and WriteMTXE are provided for compatibility. Here, the columns \(a_i\) and \(b_i\) in the blocks \(A\) and \(B\) are listed individually, and are either intercalated [the ordering \((a_1, b_1, a_2,b_2,\ldots,a_n,b_n)\)] or are separated into column blocks \((a_1,\ldots,a_n,b_1,\ldots,b_n)\). In both cases the number of columns in the matrix stored is twice the code length.
The ordering of the columns is governed by a parameter pair, optional in the function ReadMTXE and required in WriteMTXE.
With pair=0 the matrix elements are stored in the usual order. In this case the MTX header should use the integer type. This is the defailt storage format for stabilizer generator matrices of CSS codes, and also the internal matrix format for single-block matrices accepted by the function DistRandCSS, see Section 4.1.
With pair=1 the block matrix \((A,B)\) is stored with intercalated columns \((a_1,b_1,\ldots,a_n,b_n)\); the MTX header should use the integer type. This is the internal matrix format for two-block matrices accepted by the functions DistRandStab (4.1) and WriteMTXE (4.2), and returned by ReadMTXE (4.2).
With pair=2 the block matrix \((A,B)\) is stored with separated columns \((a_1,\ldots,a_n, b_1,\ldots,b_n)\); the MTX header should also use the integer type.
With pair=3 the block matrix \((A,B)\) is stored as a complex matrix \(A+iB\), with columns \((a_1 + i b_1,\ldots,a_n + i b_n)\). In this case type=complex, since matrix elements are represented as complex integers.
By default, pair=0 corresponds to type=integer and pair=3 corresponds to type=complex. It is strongly recommended that matrices intended for use by others should only use these two variants of the MTXE format.
For efficiency reasons, the function DistRandStab (4.1) assumes the generator matrix with intercalated columns.
The first line must have the following form:
%%MatrixMarket matrix coordinate `type` general
with type either integer or complex.
The second line is optional and specifies the field, the primitive polynomial used (in the case of an extension field), and the storage format of field elements.
Field: `field` PrimitiveP(x): `polynomial` Format: `format`
Here the records should be separated by one or more spaces; while field, polynomial, and format should not contain any spaces. Any additional records in this line will be silently ignored.
The field option should specify a valid field, GF(q) or GF(p^m), where \(q>1\) should be a power of the prime \(p\).
The polynomial should be a valid expanded monic polynomial with integer coefficients, with a single independent variable x; it should contain no spaces. An error will be signaled if polynomial is not a valid primitive polynomial of the field. This argument is optional; if not specified, one may assume that the Conway polynomial should be used.
The optional format string should be "AdditiveInt" (the default for prime fields), "PowerInt" (currently the default for extension fields with \(m>1\)) or "VectorInt".
AdditiveInt indicates that values listed are expected to be in the corresponding prime field and should be interpreted as integers mod \(p\).
PowerInt indicates that field elements are represented as integers powers of the primitive element, root of the primitive polynomial, or \(-1\) for the zero field element.
VectorInt corresponds to encoding coefficients of a degree-\((m-1)\) \(p\)-ary polynomial representing field elements into a \(p\)-ary integer. In this notation, any negative value will be taken mod \(p\), thus \(-1\) will be interpreted as \(p-1\), the additive inverse of the field \(1\).
The primitive polynomial must be written explicitly as \(x^m+a_{m-1}*x^{m-1}+\ldots+a_1*x+a_0\), where the integer coefficients \(a_i\) will be interpreted modulo p. The primitive polynomial should not contain any spaces.
% Field: GF(`q`) PrimitiveP(x): `polynomial`
For example, with \(q=5^2\), the Conway polynomial \(f_{5,2}(x)=x^2-x+2\), and the second line can read
% Field: GF(25) PrimitiveP(x): x^2-x+2 Format: PowerInt
The following is an equivalent form of the same polynomial and can also be used
% Field: GF(25) PrimitiveP(x): x^2+4*x+2
The field may be left undefined; by default, it is \(\mathop{\rm GF}(2)\), or it can be specified by hand when reading the matrices. If the primitive polynomial is undefined, it will be assumed that the Conway polynomial used internally by GAP should be used.
Next follows the comment section, with each line either empty or starting with the % symbol:
% Example of the comment line
After the comment section, in agreement with MTX format, goes the line giving the dimensions of the matrix and the number of non-zero elements:
rows columns `(number of non-zero elements)`
Then all non-zero elements are listed as three or four integers according to the type:
type=integer:
i j element[i,j]
type=complex:
i j a[i,j] b[i,j]
Notice that column and row numbers must start with 1, as prescribed in the original MTX format.
Neither the WriteMTXE nor ReadMTXE currently support the Format: parameter. Prime field elements are only stored "as is", i.e., as integers to be taken modulo p, while extension field elements are only stored in the PowerInt format, i.e., with the power of the primitive element specified, or "-1" for zero.
The function WriteMTXE can only save field elements with the primitive polynomial used internally by GAP, i.e., the Conway polynomial.
The function ReadMTXE can read matrix elements specified (in the case of an extension field) with any primitive polynomial as specified in the file.
Given the field \(\mathop{\rm GF}(p^m)\) and the primitive polynomial \(p(x)\) specified in the file, the function ReadMTXE first checks that the degree of \(p(x)\) is indeed \(m\) and that it is a primitive polynomial in the corresponding prime field \(\mathop{\rm GF}(p)\). If either of these tests fail, ReadMTXE produces an error. Otherwise, it will attempt to find the conversion coefficient \(c\) such that \(\alpha^c\) is a root of \(p(x)\), starting with \(c=1\). When found, the multiplicative inverse \(s\) such that \(sc\equiv 1\bmod (q-1)\) will be used to convert the elements being read, i.e., for any matrix element \(y\) read, \(y^s\) will be used instead.
Notice that, unless the Conway polynomial was used (in which case \(c=s=1\), and the conversion is trivial), this search can be slow for large fields, as all integer values in \([1,2,\ldots,q-2]\) will be tested sequentially. To help ensure that the correct polynomial is used, it is recommended that orthogonality of matrices be checked.
In this section we give two sample MTXE files storing the stabilizer generator matrix of 5-qubit codes.
First, matrix (with one redundant linearly-dependent row) stored with type=integer and pair=1 (intercalated columns \([a_1,b_1,a_2,b_2,\ldots]\)) is presented. Notice that the number of columns is twice the actual length of the code. Even though the field is specified explicitly, this matrix would work with any prime field.
%%MatrixMarket matrix coordinate integer general % Field: GF(7) % 5-qubit code generator matrix / normal storage with intercalated cols 5 10 20 1 1 1 1 4 1 1 6 -1 1 7 -1 2 3 1 2 6 1 2 8 -1 2 9 -1 3 1 -1 3 5 1 3 8 1 3 10 -1 4 2 -1 4 3 -1 4 7 1 4 10 1 5 2 1 5 4 -1 5 5 -1 5 9 1
This same matrix is stored in the file matrices/n5k1A.mtx. This is how the matrix can be read and distance calculated:
gap> filedir:=DirectoriesPackageLibrary("QDistRnd","matrices");; gap> lis:=ReadMTXE(Filename(filedir,"n5k1A.mtx" ));; gap> Print("field ",lis[1],"\n"); field GF(7) gap> dist:=DistRandStab(lis[3],100,0 : field:=lis[1]); 3
The same matrix can also be stored with type=complex and pair=3 (complex pairs \([a_1+i b_1,a_2+i b_2,\ldots]\)). In this format, the number of columns equals the code length.
%%MatrixMarket matrix coordinate complex general % works with any prime field % 5-qubit code generator matrix / normal storage with intercalated cols % [[5,1,3]]_p 4 5 16 1 1 1 0 1 2 0 1 1 3 0 -1 1 4 -1 0 2 2 1 0 2 3 0 1 2 4 0 -1 2 5 -1 0 3 1 -1 0 3 3 1 0 3 4 0 1 3 5 0 -1 4 1 0 -1 4 2 -1 0 4 4 1 0 4 5 0 1
The matrix above is written in the file matrices/n5k1.mtx. To calculate the distance, we need to specify the field [unless we want to use the default binary field].
gap> lis:=ReadMTXE(Filename(filedir,"n5k1.mtx" ));; gap> Print("field ",lis[1],"\n"); field GF(2) gap> dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]); 3 gap> q:=17;; gap> lis:=ReadMTXE(Filename(filedir,"n5k1.mtx") : field:= GF(q));; gap> Print("field ",lis[1],"\n"); field GF(17) gap> dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]); 3
Finally, the following is an example of a five-qudit code over \(\mathop{\rm GF}(2^3)\) constructed by the script examples/cyclic.g.
%%MatrixMarket matrix coordinate complex general % Field: GF(2^3) PrimitiveP(x): x^3+x+1 % code [[5,1,3]]_8 % cyclic w=4 x^6+Z(2^3)^4*x^5+Z(2^3)^4*x^3+Z(2)^0 % Powers of GF(8) primitive element and -1 for Zero are given 5 5 20 1 1 0 -1 1 2 -1 4 1 3 -1 4 1 4 0 -1 2 2 0 -1 2 3 -1 4 2 4 -1 4 2 5 0 -1 3 1 0 -1 3 3 0 -1 3 4 -1 4 3 5 -1 4 4 1 -1 4 4 2 0 -1 4 4 0 -1 4 5 -1 4 5 1 -1 4 5 2 -1 4 5 3 0 -1 5 5 0 -1
generated by GAPDoc2HTML