# OK to post
# HW6, Robert Dougherty-Bliss, 2024-02-11

# 1.

# 5.1
# Every linear code over F(q) has size q^m for some integer m >= 0, so a code
# with 24 = 8 * 3 codewords cannot be linear.

# 5.2

# Clearly n = n, and in a previous exercise we showed that d = 2. (There, I did
# it by saying that E(n) is the result of adding a parity bit to the trivial

#       (n - 1, 2^(n - 1), 1)

# code, which made it an (n, 2^(n - 1), 2) code. Now it's easier, because we
# know that d is the minimum weight of every codeword, which is clearly 2.)

# The only remaining problem is to determine the dimension. Take the standard
# basis vectors for F_2^(n - 1) and append a 1 to the end of each of them.
# These are linearly independent by construction, and given any (x1, x2, ...,
# xn) in E(n), we can express it as a linear combination of these vectors as
# follows:

#   (x1, x2, ..., xn) = (x1, x2, ..., x(n - 1), x1 + x2 + ... + x(n - 1))
#                     = (x1, 0, ..., 0, x1) + (0, x2, 0, ..., 0, x2) + ....

# So k = n - 1.

(*
Here's a matrix for E(6):

    100001
    010001
    001001
    000101
    000011

The pattern continues essentially the same way.

*)

# 5.3

# I believe the question here is to prove that the set of x annihilated by H^T
# is a subspace. If x and y are so annihilated, then for any constants a and b,

#       (a * x + b * y) H^T
#     = a * x H^T + b * y H^T
#     = 0.

# 5.5

# Suppose that we have a k-dimensional subspace, meaning that we have k basis
# vectors. Say that A of them have even weight, and B of them have odd weight.

# Every vector in our subspace is determined by which basis vectors we add
# together. In particular, their weight is determined precisely by how many of
# the B odd-weight vectors we choose; if we pick an even number of them, then
# the result will have even weight, and vice versa. Thus, half of the vectors
# will have odd weight, and half will have even weight. (Unless B = 0, then
# everything has even weight.)

# 4.

# This exercise is really annoying. Let me lay out why.

# Standard form means you get the block matrix [I | M], where I is the identity
# and M is arbitrary. That means that we are doing something *stronger* than
# Gaussian elimination, because we force the k pivots to be in the first k
# columns.

# The below algorithm does something like this:
#       Set k = 1.
#       For k from 1 to n:
#           1. Let j be the column first column >= k which contains a nonzero
#           entry at a row k. Call this nonzero entry the "pivot." Swap
#           columns k and j, so that k is the first column with a nonzero
#           entry, and the pivot occurs at (k, k).

#           2. Eliminate below the first nonzero entry of column k.

#       For k from n to 1:
#           1. Eliminate above the entry in (k, k) so that the pivots are the
#           only nonzero entries in their columns.

#           2. Divide the kth row by the pivot (k, k).

# Swap columns k and j.
swapColumns := proc(in_M, k, j)
    local M, i:
    M := in_M:

    for i from 1 to nops(M) do
        M[i][k], M[i][j] := M[i][j], M[i][k]:
    od:

    M:
end:

# Replace the jth row with (left_mult * kth row + right_mult * jth row) mod q.
linearCombRows := proc(q, in_M, k, j, left_mult, right_mult)
    local M, i:
    M := in_M:

    M[j] := [seq(left_mult * M[k][i] + right_mult * M[j][i] mod q, i=1..nops(M[j]))]:
    M:
end:

SF := proc(q, in_mat)
    local M, n_cols, n_rows, k, j, pivot, pivot_inv, i, mult:
    M := in_mat:
    n_cols := nops(in_mat[1]):
    n_rows := nops(in_mat):

    for k from 1 to n_rows do
        # Find the column which should become the kth column.
        for j from k to n_cols do
            if M[k][j] mod q <> 0 then
                break:
            fi:
        od:

        if j > n_cols then
            error("your matrix is not a basis"):
        fi:

        M := swapColumns(M, k, j):

        # Eliminate below the kth pivot.
        pivot := M[k][k]:
        pivot_inv := pivot &^ (-1) mod q:

        for i from k + 1 to n_rows do
            mult := -M[i][k] * pivot_inv mod q:
            M := linearCombRows(q, M, k, i, mult, 1):
        od:
    od:

    # Eliminate *above* the kth pivot in (k, k).
    for k from n_rows to 1 by -1 do
        pivot_inv := M[k][k] &^ (-1) mod q:
        for i from k - 1 to 1 by -1 do
            mult := -M[i][k] * pivot_inv mod q:
            M := linearCombRows(q, M, k, i, mult, 1):
        od:

        # Set the kth pivot to 1.
        M := linearCombRows(q, M, k, k, pivot_inv, 0):
    od:

    Matrix(M):
end:

# here's a basis for E(6), but in the "wrong" order.
test_basis := [
    [1, 1, 0, 0, 0, 0],
    [1, 0, 1, 0, 0, 0],
    [1, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 0, 1]]:

# Here's a basis over F_7^4:
test_basis_2 := [seq([seq(b &^ k mod 7, k=0..3)], b=2..4)]:

# here's one that fails if you don't swap columns.
test_basis_3 := [
    [0, 1, 0],
    [0, 0, 1]]:

SF(2, test_basis);
SF(7, test_basis_2);
SF(2, test_basis_3);