#OK to post homework 
#Natalya Ter-Saakov, Feb 11, 2024, Assignment 6
read "C6.txt":

#Problem 2
#5.1: Every binary linear code is a subspace and so must have size a power of 2. Since 24 is not a power of 2, this is not a linear code.

#5.2: The parameters are [n,n-1,2]. The standard form of the generator matrix is I_n with the all 1 vector appended to it.

#5.3: There are two conditions to check and it is just a question of some matrix algebra. Consider x and y in C. (x+y)H^T = xH^T + yH^T = 0 + 0 = 0, so x+y is in C. For some a in F^q, (ax)H^T=a(xH^T) = a(0) = 0, so ax is in C. 

#5.4(i): Suppose C is a binary linear code and x,y are in C. Then, if we consider x' and y', the results of adding a parity check, the sum of x' and y' is the sum of x and y with the correct parity check. Since the code is binary, we do not need to check the multiplication condition.

#5.4(ii): [[10001011],[01001110],[00101101],[00010111]] (This is Example 5.6(ii) with parity bit added.)

#Problem 3

#RM(q,n,k): inputs q,n,k and generates a random basis set in F_q^n with k vectors
RM:=proc(q,n,k) local i,r,K,j,Q:
K:=[]:
r:=rand(q^n):
for i from 1 while nops(K)<k do
	j:=r():
	if not j in K and j>1 then
		K:=[op(K),j]:
	fi:
od:
Q:=Fqn(q,n):
[seq(Q[K[i]], i=1..k)]:
end:

#SearchLC(q,n,k,K): inputs q and n for GF(q)^n, and k (for the dimension of the linear code, a certain subspace of GF(q)^n) and a very large positive integer K (say 1000) and keeps generationg, K times, random lists, M, of k members of GF(q)^n, for each determines MinW(q,M) and outputs the one with the largest minimum weight.

SearchLC:=proc(q,n,k,K) local i, j, bestW, bestM, M, W:
bestW:=0:
for i from 1 to K do
	M:=RM(q,n,k):
	W:=MinW(q,M):
	if W>bestW then 
		bestW:=W:
		bestM:=M:
	fi:
od:
[bestM,bestW]:
end:

#q=2
#[[[1, 0, 0, 1], [0, 1, 0, 1], [1, 1, 0, 0]], 2]
#[[[0, 1, 1, 0], [1, 0, 0, 1], [0, 0, 1, 1], [1, 1, 0, 0]], 2]
#[[[0, 1, 1, 0], [0, 1, 0, 1], [1, 1, 0, 0], [1, 0, 0, 1], [0, 0, 1, 1]], 2]
#[[[1, 1, 0, 0, 1], [0, 1, 1, 1, 0], [1, 0, 1, 1, 1]], 3]
#[[[1, 0, 1, 0, 1], [0, 0, 0, 1, 1], [1, 1, 1, 0, 0], [0, 1, 0, 0, 1]], 2]
#[[[1, 1, 1, 0, 1], [1, 0, 1, 1, 1], [1, 0, 1, 0, 0], [1, 1, 0, 1, 1], [1, 0, 0,0, 1]], 2]
#[[[1, 1, 0, 1, 1, 0], [1, 0, 1, 1, 0, 0], [0, 0, 0, 1, 1, 1]], 3]
#[[[1, 0, 1, 0, 0, 1], [1, 1, 0, 0, 1, 1], [0, 1, 1, 0, 1, 0], [1, 1, 0, 1, 0, 0]], 3]
#[[[0, 0, 1, 1, 0, 1], [0, 1, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1], [1, 1, 0, 1, 0, 0], [1, 1, 0, 0, 1, 0]], 2]
#[[[1, 0, 0, 0, 1, 1, 1], [1, 1, 0, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 0]], 4]
#[[[0, 0, 0, 1, 0, 1, 1], [0, 0, 1, 1, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0], [0, 0, 1, 0, 1, 1, 1]], 3]
#[[[0, 1, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 0, 1, 1]], 2]
#[[[1, 1, 1, 0, 1, 0, 0, 1], [1, 1, 0, 1, 0, 1, 1, 1], [0, 0, 1, 1, 1, 1, 1, 0]], 5]
#[[[1, 1, 0, 1, 1, 0, 1, 1], [0, 1, 1, 0, 1, 0, 1, 0], [1, 1, 0, 0, 1, 1, 0, 0],[0, 1, 1, 1, 1, 1, 0, 1]], 4]
#[[[0, 1, 0, 0, 1, 1, 0, 0], [1, 1, 1, 0, 1, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1, 1],[0, 0, 1, 0, 0, 1, 1, 1], [0, 1, 0, 1, 0, 0, 1, 0]], 3]
#[[[1, 0, 0, 1, 1, 1, 1, 0, 1], [1, 1, 1, 0, 0, 1, 0, 0, 1], [0, 1, 1, 1, 1, 0,1, 0, 0]], 5]
#[[[1, 1, 1, 0, 1, 0, 0, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0, 0], [0, 0, 0, 1, 0, 1,1, 0, 1], [1, 0, 0, 0, 1, 1, 0, 1, 1]], 4]
#[[[0, 0, 0, 1, 0, 1, 0, 1, 1], [1, 1, 0, 0, 0, 0, 1, 1, 0], [0, 1, 1, 1, 1, 0,0, 0, 0], [1, 1, 0, 1, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 0, 1, 1, 1]], 4]
#[[[1, 0, 0, 1, 0, 0, 1, 1, 0, 1], [0, 1, 1, 0, 1, 1, 1, 1, 0, 0], [0, 1, 0, 1,0, 1, 1, 0, 1, 0]], 5]
#[[[0, 0, 1, 0, 1, 0, 1, 1, 0, 0], [1, 0, 0, 0, 1, 1, 0, 1, 0, 1], [1, 1, 1, 0,1, 1, 1, 1, 1, 1], [0, 0, 1, 1, 0, 1, 0, 1, 0, 1]], 4]
#[[[1, 0, 1, 0, 0, 0, 0, 0, 1, 1], [1, 0, 0, 1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 1, 1, 1, 0, 1, 0, 1], [1, 0, 1, 1, 1, 0, 1, 0, 0, 0], [0, 0, 1, 0, 1, 1, 1, 0, 1, 0]], 4]

#q=3
#[[[2, 1, 0, 2], [2, 0, 1, 1], [0, 1, 2, 1]], 3]
#[[[1, 1, 1, 2], [0, 0, 1, 1], [2, 0, 2, 0], [1, 2, 2, 2]], 2]
#[[[2, 1, 1, 2], [1, 0, 1, 1], [2, 1, 0, 0], [1, 1, 1, 0], [2, 0, 2, 2]], 2]
#[[[0, 1, 1, 1, 0], [0, 2, 2, 2, 0], [1, 0, 2, 0, 2]], 3]
#[[[1, 1, 2, 0, 0], [2, 2, 2, 1, 2], [0, 2, 0, 2, 0], [2, 1, 0, 2, 2]], 2]
#[[[2, 2, 2, 0, 1], [1, 2, 2, 2, 2], [1, 2, 1, 2, 0], [0, 2, 1, 1, 1], [0, 1, 2, 0, 0]], 2]
#[[[1, 0, 2, 2, 1, 0], [2, 1, 1, 0, 1, 1], [0, 1, 0, 2, 2, 1]], 4]
#[[[2, 0, 1, 0, 2, 0], [2, 2, 1, 2, 2, 2], [1, 2, 0, 0, 2, 0], [2, 1, 2, 2, 0, 2]], 3]
#[[[1, 1, 2, 0, 2, 0], [2, 0, 2, 1, 1, 1], [0, 2, 2, 0, 1, 1], [1, 2, 1, 1, 1, 1], [1, 1, 1, 2, 2, 1]], 2]
#[[[2, 2, 0, 1, 2, 0, 1], [2, 1, 0, 0, 1, 1, 0], [0, 1, 2, 0, 2, 2, 2]], 4]
#[[[0, 0, 1, 1, 0, 2, 2], [0, 1, 2, 0, 1, 2, 0], [0, 1, 1, 2, 1, 0, 1], [2, 2, 2, 1, 1, 2, 1]], 4]
#[[[1, 0, 0, 0, 0, 1, 1], [0, 2, 0, 2, 0, 2, 2], [2, 1, 0, 1, 0, 0, 0], [0, 1, 1, 0, 2, 2, 1], [2, 1, 0, 2, 1, 0, 2]], 3]
#[[[0, 2, 0, 0, 1, 1, 1, 1], [1, 2, 2, 1, 0, 0, 1, 1], [2, 2, 2, 0, 2, 0, 2, 0]], 5]
#[[[0, 0, 2, 1, 1, 0, 0, 2], [0, 1, 1, 1, 2, 1, 0, 0], [2, 1, 1, 1, 0, 0, 2, 2], [2, 0, 2, 0, 1, 0, 1, 1]], 4]
#[[[2, 0, 1, 0, 0, 1, 2, 2], [1, 1, 0, 2, 1, 0, 2, 1], [1, 0, 1, 0, 2, 2, 2, 2], [2, 2, 2, 2, 0, 1, 0, 1], [1, 0, 2, 2, 0, 0, 2, 1]], 3]
#[[[0, 0, 0, 1, 2, 0, 2, 1, 1], [2, 1, 2, 0, 0, 0, 1, 2, 2], [1, 1, 0, 0, 1, 0, 0, 2, 1]], 5]
#[[[0, 2, 2, 1, 2, 2, 1, 1, 1], [2, 2, 2, 2, 2, 1, 1, 1, 0], [2, 0, 2, 1, 2, 1, 0, 1, 1], [2, 2, 2, 0, 1, 2, 0, 0, 2]], 4]
#[[[2, 2, 1, 2, 0, 1, 0, 0, 1], [2, 0, 1, 0, 2, 0, 2, 2, 0], [1, 1, 1, 2, 2, 2, 2, 1, 2], [0, 1, 1, 2, 0, 2, 0, 2, 1], [1, 0, 1, 2, 1, 2, 2, 0, 0]], 3]
#[[[0, 1, 1, 1, 1, 0, 0, 1, 0, 1], [0, 2, 1, 0, 1, 1, 2, 0, 0, 2], [2, 1, 0, 0, 2, 0, 1, 1, 1, 2]], 6]
#[[[1, 1, 0, 1, 1, 2, 1, 0, 2, 1], [0, 0, 1, 1, 1, 1, 0, 1, 0, 0], [0, 2, 1, 0, 0, 1, 1, 0, 2, 2], [0, 1, 0, 2, 0, 1, 2, 0, 2, 0]], 5]
#[[[0, 1, 1, 1, 1, 1, 0, 2, 0, 2], [1, 1, 2, 0, 2, 1, 1, 0, 2, 2], [1, 1, 0, 2, 1, 1, 1, 1, 2, 1], [2, 1, 0, 0, 1, 0, 2, 1, 2, 1], [2, 0, 1, 2, 2, 2, 1, 0, 1, 0]], 4]

#q=5

#Problem 4

#SF(q,M): inputs q (for GF(q)^n) a generating matrix M ( a list of vectors of length n in GF(q)^n), and k=nops(M), and outputs the matrix in statdard form, i.e. of the from [I_k|A] where I_k is the k by k identity matrix and A is k by (n-k) matrix.

#Note that the "standard" procedure for Gaussian elimination turns the matrix into an upper triangular one first and the subtracts rows up. This procedure subtracts the rows both up and down immediately. 

SF:=proc(q,M) local k,n,r1,r2,row,i, M2:
M2:=M:
k:=nops(M):
n:=nops(M[1]):
for r1 from 1 to k do
	row:=ScaleRow(q,M2[r1],r1):
	M2[r1]:=row:
	for r2 from 1 to k do
		if not r2=r1 then
			M2[r2]:=SubtractRow(q,M2[r2],r1,row):
		fi:
	od:
od:
M2:
end:

ScaleRow:=proc(q,row,c) local i:
[seq(row[i]*(row[c]^(-1)) mod q,i=1..nops(row))]:
end:

SubtractRow:=proc(q,row2,c,row) 
row2-row2[c]*row mod q:
end: