#OK to post
#GLORIA LIU, Mar 2 2024, Assignment 13

read `C13.txt`:

#=====================================#
#1. Write a procedure
#CCshopF(N,q,x,K,R,W): that inputs a positive integer N, a prime q, a variable x, a large positive 
#integer K, a number R between 0 and 1, and a positive integer W and outputs the tuples 
#[g,rate,MinWt] (like the members of the output of CCshoop(n,q,x,K) for all n between 2 and N, but 
#for which the rate is ≥ R and the minimum weight is $ge; W.
#What are
#CCshopF(30,2,x,10000,1/2,5)? how many members does it have?
#CCshopF(30,3,x,10000,1/2,5)? how many members does it have?
#CCshopF(30,5,x,10000,1/2,5)? how many members does it have?

CCshopF:=proc(N,q,x,K,R,W) local C,c,result:
C:=CCshop(N,q,x,K):
result:={}:
for c in C do
 if c[2] >= R and c[3] >= W then
  result:=result union {c}:
 fi:
od:
result:
end:

result1:=CCshopF(30,2,x,10000,1/2,5):
nops(result1):
result2:=CCshopF(30,3,x,10000,1/2,5):
nops(result2):
result3:=CCshopF(30,3,x,10000,1/2,5):
nops(result3):

#Maybe I did it wrong but I got 0 members for all three

#=====================================#
#2. Implement theorem 12.15 by writing a procedure
#CtoDual(n,q,x,g): that inputs a positive integer n, a prime q, a variable x, and a polynomial g (a 
#generator of a cyclic code) mod q and outputs the generator matrix for the dual code of CtoL(n,x,g)

CtoDual:=proc(n,q,x,g) local r,L,i,g1,result:
r:=degree(g,x):
L:=[seq(coeff(g,x,i),i=0..r)]:
g1:=add(L[i]*x^(r-i+1), i=1..r+1):
print(g1);
result:=CtoL(n,x,g1):
end:

#Test using the polynomial on pg.153
CtoDual(23, 2, x, x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1):

#=====================================#
#3. Without "peeking", prove that det(V(a,r))=Vd(a,r)
#I looked at the sketch of the solution during class
#This can be proved by induction on r. 
#The base case is r=2. The determinant in this case is clearly (a_2 - a_1).
#Inductive hypothesis: Assume that det(V(a,r-1)) = Vd(a,r-1). 
#Let V = V(a,r).
#Use row operations on V, which preserve the determinant. 
#For each row, subtract a_1*the previous row. 
#At this point, for the i,j entry:
#a_j^{i-1}-a_j^{i-2}*a_1 = a_j^{i-2}*{a_j - a_1} (except 1st row, which is all ones)
#This makes the first column have all zeroes except in the first row. 
#Calculating the determinant by expanding on the first column, which would just be
#1 * det(V_{1,1}), V_{1,1} corresponds to the (r-1)*(r-1) matrix excluding the first row and column.
#Divide each column j=2..r of V by (a_j-a_1), to form V1. 
#The determinant of V will be (\sum_{j=2}^{r} (a_j - a_1))* det(V1_{1,1}).
#At this point, V1_{1,1} = V(a,r-1), except a is indexed from a_2 to a_r instead of a_1 to a_{r-1}.
#Use the inductive hypothesis: det(V1_{1,1}) = \sum_{i=2}^{r-1} \sum_{j=i+1}^{r} (a_j - a_i)
#So, det(V) = (\sum_{j=2}^{r} (a_j - a_1))* \sum_{i=2..r, r>=j>i} (a_j - a_i) 
#= \sum_{i=1}^{r-1} \sum_{j=i+1}^{r} (a_j - a_i) = Vd(a,r)
#We get det(V(a,r-1)) = Vd(a,r-1)

#=====================================#
#4. There are r tennis players, 1, ..., r, and each of the r(r-1)/2 pairs play each other. 
#suppose that at the beggining they were ranked according to ability where 1 is the worst and r is the best. 
$Whenver someone lower-rankded beats someone higher it is an upset. 
#Whenever a player wins one of their games they score a point. 
#Let's look at the collection of all possible 2^(r(r-1)/2) and for each possible outcome 
#let [s[1], ..., s[r]] be the score vector. Define
#Weight(Outcome):=(-1)^NumberOfUpsets*mul(a[i]^s[i],i=1..r)
# 1 Prove that Vd(a,r)=Sum of all Weight(Outcome) over all possible 2^(r(r-1)/2) outcomes.
# 2 An outcome is called transitive if you don't have a cycle i1 beats i2, i2 beats i3, i3 beats i1. Prove that V(a,r) is the sum of the weights of all transitive tournaments.
# 3 Prove that the sum of the weights of all the 2^(r(r-1)/2)-r! non-transitive outcomes is 0
# 4 Conclude that det(V(a,r))=Vd(a,r)

#Skipped

#=====================================#
#5. The code of Example 11.3 (p. 128 in the book) is a subset of given by the 4 by 10 parity check 
#matrix . Write a procedure
#Encode113(x)
#that inputs a vector in {0,1,...,10}^6 representing [x[1],..., x[6]] and completes it to a vector
#x=[x[1],..., x[10]]
#that belongs to the code, i.e. such that the PCM given there times x is the 0 vector.

with(LinearAlgebra):
with(linalg):

Encode113:=proc(x) local H,H1,K,i,j,t,result:
H:=[seq([seq(i^j, i=1..10)], j=0..3)]:
print(Matrix(H));
H1:=[seq([seq(H[i][j], j=7..10)], i=1..4)]:
print(Matrix(H1));
K:=[seq(-1*add(H[i][j]*x[j],j=1..6) mod 11, i=1..4)]:
t:=Linsolve(Matrix(H1),Vector(K)) mod 11:
[op(x), seq(t[i], i=1..4)]:
end:

#Check that the answer is correct, MatrixVectorMultiply(Matrix(H); Vector(c)) should equal 0 vector
H:=[seq([seq(i^j, i=1..10)], j=0..3)]:
c:=Encode113([1,2,3,4,5,6]);
MatrixVectorMultiply(Matrix(H), Vector(c)) mod 11: