#C21.txt: Lecture 21
Help21:=proc(): print(`In(n) , An(n), Check1(n), Bn(n), Check2(n), Findx(n,H), Findy(n,H) `):end:

with(linalg):
with(combinat):

#Glue(A): inputs a matrix of matrices given in block
#notation, "glues" them into one matrix
#For example
#Glue([ [[1,2],[1,3]], [[3,5],[1,13]]]]);
Glue:=proc(A) local i,j:
#TO BE CONTINUED IN HOMEWORK

end:

#In(n):n by n identity matrix
In:=proc(n) local L,i:

[seq([0$(i-1),1,0$(n-i)],i=1..n)]:

end:

#An(n): The matrix A_n in Knuth's note about Hunag's proof
An:=proc(n) local L1,L2:
if n=0 then
 RETURN([[0]]):
fi:

L1:=An(n-1):
L2:=In(2^(n-1)):

[
seq([op(L1[i]),op(L2[i])],i=1..nops(L1)),
seq([op(L2[i]),op(-L1[i])],i=1..nops(L1))
]:
end:

#Check1(n): checks that An(n)^2=n*In(2^n) (in Line 1 of the proof)
Check1:=proc(n):
evalb(convert(multiply(An(n),An(n)),list)=n*In(2^n)):
end:

#Bn(n): The 2^n by 2^(n-1) matrix B_n defined in the second paragraph of
#Knuth's note on Hao Huang's proof
Bn:=proc(n) local L1,L2:
L1:=An(n-1):
L2:=In(2^(n-1)):
[seq(L1[i]+sqrt(n)*~L2[i],i=1..nops(L1)), op(L2)]:
end:

#Check2(n):checks that A_n B_n = sqrt(n) B_n
Check2:=proc(n) local L,R,A,B:
A:=An(n):
B:=Bn(n):
L:=multiply(A,B):
R:=[seq(sqrt(n)*~B[i],i=1..nops(B))]:
convert(L,list),R:

end:

#Findx(n,H): inputs a pos. integer n and an arbitrary subset, H,
#of {1,...,2^n} of cardinality 2^(n-1)+1 finds the vector
#2^(n-1)-dimensional vector x such that all the rows of Bn(n) that correspond to those
#that do NOT belong to H in Bn(n)x are 0
#For example
#Findx(3,{1,3,5,6,8});
Findx:=proc(n,H) local B,x,i,var,eq,v,Nv:
if nops(H)<>2^(n-1)+1 then
  RETURN(FAIL):
fi:

B:=Bn(n):

var:={seq(x[i],i=1..2^(n-1))}:
eq:={}:

for i from 1 to 2^n do
 if not member(i,H) then
  eq:=eq union {add(B[i][j]*x[j],j=1..nops(B[i]))}:
 fi:
od:

var:=solve(eq,var):
v:=[seq(subs(var,x[i]),i=1..2^(n-1))]:
#get rid of the symbol
v:=subs({seq(x[i]=1,i=1..2^(n-1))},v):

#Nv is the length of v
Nv:=simplify(sqrt(add(v[i]^2,i=1..nops(v)))):
[seq(v[i]/Nv,i=1..nops(v))]:
end:


#Done after class
#Findy(n,H): The 2^n-dimensinal vector B_n x where x=Findx(n,H) (see above
Findy:=proc(n,H)  local x,y,i:
x:=Findx(n,H):
x:=[seq([x[i]],i=1..nops(x))]:

y:=convert(multiply(Bn(n),x),list):
[seq(y[i][1],i=1..nops(y))]:
end: