Implement linear codes over finite fields and dual spaces

[kirtsar]

Basically code is just a subspace of some vector space over some finite field F.

abstract type AbstractCode end

struct GenericCode{T} <: AbstractCode
    space :: T
    n :: Int
    k :: Int
end

function Code(V, vs)
    gens = []
    for v in vs
        push!(gens, F.(v))
    end
    gens = Vector{typeof(gens[1])}(gens)
    n = dim(V)
    spc = sub(V, V.(gens))[1]
    k = dim(spc)
    return GenericCode(spc, n, k)
end

function base_ring(c :: GenericCode)
    return base_ring(c.space)
end

function base_space(c :: GenericCode)
    return c.space.m
end

function generators(c :: GenericCode)
    return c.space.gens
end

function gen_mat(c :: GenericCode)
    gens = generators(c)
    gmat = []
    for g in gens
        push!(gmat, g.v)
    end
    return vcat(gmat...)
end

I was trying to implement GenericCode as a wrapper around subspace and found it somewhat tricky to handle.

For example, if I want to obtain dual code, which is basically just the orthogonal complement of original subspace, I must do the following:

function dual_code(c :: GenericCode)
    V = base_space(c)
    gmat = gen_mat(c)
    hmat = nullspace(gmat)[2]'
    spc = sub(V, [V(vec(Matrix(hmat[i, :]))) for i in 1 : size(hmat)[1]])[1]
    n = dim(V)
    k = dim(spc)
    return GenericCode(spc, n, k)
end

The questions are:

1. Why there are no iterators for matrix types? Why I can't get access to some element of matrix (only manually translating as Matrix(..) to the usual matrix)
2. Why is it impossible to create Vector space from matrix element? sub(V, hmat)

[wbhart]

1. I'm not sure what you mean. You can get entry i,j for one of our matrices A using A[i, j], just the same as Julia. Can you give an example which doesn't work?

2. I guess this wasn't implemented. Subspace currently takes a list of elements of a vector space, not a matrix. This is part of our general philosophy that a matrix is a matrix, not an element of a vector space. Everything is supposed to have mathematical meaning. On the other hand, if it proves to be really hard to work with things this way, some convenience functions could be added. Feel free to make a pull request if this is the case.

[kirtsar]

I see, that's my fault:

R = MatrixSpace(ZZ, 2, 2)
m = R([1 2; 3 4])
row1 = m[1, :]
row1[1]             # does not work
row1[1, 1]         # works as expected

It is not so easy to see, because row1 looks like the 1D-vector, but when trying to address by 1 index it crashes.

For example, in Julia:

m = [1 2; 3 4]
row1 = m[1, :]
row1[1]             #  works
row1[1, 1]         #  also works

[wbhart]

Yeah unfortunately we can't implement that because of the difference between Julia's column major and our row major representation. The latter is used much more by C libraries, and the former by Fortran, as I understand it. As we work exclusively with C libraries, we always use the latter.

It's unfortunate, but not implementing this is deliberate, to prevent confusion. Our documentation could be clearer though I guess.

[atx]

@kirtsar I was messing with linear codes myself the other day. An easier way of getting the dual code is by looking at the kernel of the transpose of the generating map (see Axler 3.107). i. e.

F = GF(2)
V = FreeModule(F, 7)
m = map(V ∘ (v -> map(F, v)), [
    [1, 1, 1, 0, 0, 0, 0],
    [1, 0, 0, 1, 1, 0, 0],
    [0, 1, 0, 1, 0, 1, 0],
])
W, f = sub(V, m)
g = ModuleHomomorphism(codomain(f), domain(f), transpose(f.matrix))
D, d = kernel(g)  # <- D should be the annihilator of W

It would be much nicer if AbstractAlgebra had proper support for dual spaces but this is what we get now.

[wbhart]

I'm marking this with the JuliaCommunity tag in case there is someone in the community that wants to take this on. It's out of the range of things we are directly working on ourselves at present, and we don't have a concrete proposal that is compatible with the C libraries we use further downstream (e.g. in Nemo.jl) which use row major instead of column major matrices, and which don't behave quite the same as Julia matrices.