#OK to post homework
#Joseph Koutsoutis, 02-11-2024, Assignment 6


read `C6.txt`:
Help:=proc():
print(` SearchLC(q,n,k,K), SF(q,M) `):
end:

#1 done

#2

#Exercise 5.1
#No, the binary (11,24,5)-code is not linear since there is no integer k s.t. 2^k = 24.

#Exercise 5.2
#By exercise 2.4, |E_n| = |(F_2)^(n-1)| = 2^(n-1). We also know that the vector with
#1s in the first two positions is a vector in E_n, and there are no vectors of even weight
#with only one 1, so E_n is a [n,n-1,2] linear code. 
#Next, we know that the standard form of a generator matrix for E_n must have the form
#[I_(n-1) | A_(n-1 x 1)], and since every row must have an even number of 1s, the last column
#must be a column of all 1s. 

#Exercise 5.3
#Suppose x,y in C and a in GF(q). We know that (cx+y)H^(T) = c(xH^T) + yH^T = c(0) + 0 = 0,
#so (cx+y) in C, meaning C is a linear code.

#Exercise 5.5
#We will prove this statement by induction on k, the dimension of binary linear code C

#Case k=1: Let v_1 be our basis vector of C. If v_1 has even weight, then C only contains vectors
#with even weight. If v_1 has odd weight, then since the 0 vector has even weight and v_1 has odd
#weight, exactly half of the code words have even weight.

#Case k=2: Let v_1,v_2,...,v_k be a basis of C. First let's assume that v_1,...,v_k all have even weight.
#Since lemmas 2.5 and 2.6 imply w(x+y) = w(x) + w(y) - 2w(x intersect y), w(c1*v_1 + ... + c_k*v_k) is even 
#for c_1,...,c_k in GF(2), so all codewords of C have even weight. Next, let's assume wlog that v_1 has odd weight. 
#By induction, the code words generated by v_2,...,v_k either all have even weight or exactly half have even weight.
#If all of these codewords have even weight, then w(1*v_1 + (c_2*v_2 + ... + c_k*v_k)) has the same parity as
#w(v_1) + w(c_2*v_2 + ... + c_k*v_k), so w(1*v_1 + (c_2*v_2 + ... + c_k*v_k)) is odd, implying exactly 
#half of the codewords in C are even.
#Otherwise if exactly half of the codewords generated by v_2,...,v_k are even, then since
#w(1*v_1 + (c_2*v_2 + ... + c_k*v_k)) is even iff w(c_2*v_2 + ... + c_k*v_k) is odd and 
#w(0*v_1 + (c_2*v_2 + ... + c_k*v_k)) is even iff w(c_2*v_2 + ... + c_k*v_k) is even, this implies exactly
#half of the vectors in C have even weight.

#3

SearchLC := proc(q,n,k,K) local C, M, d, best_M, best_d, i, j:
 best_M := [seq(RV(q,n), i=1..k)]:
 best_d := MinW(q,best_M):
 for j from 1 to K-1 do:
  M := [seq(RV(q,n), i=1..k)]:
  d := MinW(q,M):
  if d > best_d then:
   best_d := d:
   best_M := M:
  fi:
 od:

 return(best_M):
end:

#This is a function that runs SearchLC(q,n,k,K) for q in q_list, n in n_list, and k in k_list and prints the output.
RunSearchLC := proc(q_list,n_list,k_list,K) local q,n,k:
 for q in q_list do:
  for n in n_list do:
   for k in k_list do:
    print(sprintf(`The largest min weight recorded was %d for q=%d, n=%d, k=%d`, MinW(q,SearchLC(q,n,k,K)), q, n, k)):
   od:
  od:
 od:
end:

#After running RunSearchLC([2,3,5], [4,5,6,7,8,9,10], [3,4,5], 1000) these were the results:

# q    n    k    MinW
# 2    4    3       4
# 2    4    4       2
# 2    4    5       2
# 2    5    3       4
# 2    5    4       3
# 2    5    5       2
# 2    6    3       4
# 2    6    4       4
# 2    6    5       2
# 2    7    3       4
# 2    7    4       4
# 2    7    5       2
# 2    8    3       5
# 2    8    4       4
# 2    8    5       3
# 2    9    3       5
# 2    9    4       4
# 2    9    5       3
# 2   10    3       6
# 2   10    4       4
# 2   10    5       4
# 3    4    3       4
# 3    4    4       3
# 3    4    5       2
# 3    5    3       3
# 3    5    4       2
# 3    5    5       2
# 3    6    3       4
# 3    6    4       3
# 3    6    5       2
# 3    7    3       5
# 3    7    4       3
# 3    7    5       3
# 3    8    3       5
# 3    8    4       4
# 3    8    5       3
# 3    9    3       5
# 3    9    4       4
# 3    9    5       4
# 3   10    3       6
# 3   10    4       5
# 3   10    5       5
# 5    4    3       3
# 5    4    4       3
# 5    4    5       2
# 5    5    3       3
# 5    5    4       3
# 5    5    5       2
# 5    6    3       4
# 5    6    4       3
# 5    6    5       2
# 5    7    3       4
# 5    7    4       4
# 5    7    5       3
# 5    8    3       5
# 5    8    4       4
# 5    8    5       3
# 5    9    3       6
# 5    9    4       5
# 5    9    5       4
# 5   10    3       7
# 5   10    4       6
# 5   10    5       5

#4

#R1op(M,i1,i2) swaps M[i1] and M[i2]
R1op := proc(M,i1,i2)
 local u,v:
 u := M[i1]: v := M[i2]:
 M[i1] := v: M[i2] := u:
end:

#C1op(M,j1,j2,k) swaps column j1 of M with column j2.
C1op := proc(M,j1,j2,k)
 local v, i:
 for i from 1 to k do:
  v := M[i,j1]:
  M[i,j1] := M[i,j2]:
  M[i,j2] := v:
 od:
end:

Step1 := proc(M1,i,g,k,n) local j,g1:
   j := i+1:
   while j <= k do:
    g1 := M1[j,i]:
    if g1 <> 0 then:
     R1op(M1,i,j):
     RETURN(g1):
    fi:
    j += 1:
   od:

   j := i+1:
   while j <= n do:
    g1 := M1[i,j]:
    if g1 <> 0 then:
     C1op(M1,i,j,k):
     RETURN(g1):
    fi:
    j += 1:
   od:
end:

Step2 := proc(M1, q, g, i) local g_inv:
 g_inv := g&^(-1) mod q:
 M1[i] := (M1[i] * g_inv) mod q:
end:

Step3 := proc(M1, q, i, k) local j:
 for j from 1 to k do:
  if j <> i then:
   M1[j] := (M1[j] - M1[j,i] * M1[i]) mod q:
  fi:
 od:
end:

SF := proc(q,M) 
 local k,i,j,n,M1,g,g1,g_inv:
 k := nops(M):
 n := nops(M[1]):
 M1 := M:
 M1 := Array(M1): 
 
 for i from 1 to k do:
  g := M1[i,i]:
  if g = 0 then:
   g := Step1(M1,i,g,k,n):
  fi:
  Step2(M1,q,g,i):
  Step3(M1,q,i,k):
 od:

 convert(M1,list,nested=true):
end: