# Homework Help: Hadamard matrix proof-combinatorics

1. Oct 2, 2011

### jrp131191

1. The problem statement, all variables and given/known data

Suppose H is an n × n matrix in which every entry is either +1 or −1, and that
every entry in the first column is +1. Also, suppose that the Hamming distance
between any pair of different rows of H is at least n/2.
Define T to be the set of triples (i, j, k) for which Hik =/= Hjk and i < j.
(a) Use the definition of H to show that |T| > (1/4)n^2(n − 1).

2. Relevant equations

None.

3. The attempt at a solution

I've figured this much..

Since Hik=/=Hjk, and i<j, if k were to be 1, then Hi1 = Hj1 = +1, so there must be n-1 possible ways to choose k, since k=/=1.

And by definition.. every row or column must be orthogonal with any other row or column, thus they must agree and disagree in the same amount of places.. n/2. Since they already all agree column 1, then in the remaining n-1 columns, there are n-1 remaining entries in each row, and in these rows of size n-1 the number of disagreements is 1 more than the number of agreements.

Also if j = 1 then i must be 0 and therefore not exist.. i dont think this is valid.. which i think means that j cannot be equal to 1 and hence only has n-1 possible arrangements-but im not too sure of this.

Now i just dont know where to go from here.... I can see where the factor of n-1 is coming from.. that is the size of the set k, i just cant figure out this (1/4)n^2 ..

EDIT : an attempt at a solution, probably wrong

Ill assume that k has n-1 possible arrangements, and j also has n-1 possible arrangements..
let a be the entry we choose for j, 1<a<n. This also implies that j now has a set entry, either +/-1, and since Hik=/=Hjk..

i must not only now lie between 1 and a but also must have a different entry to that of j..... ill assume that this column alternates from + to - in each entry so that between 1 and a there are a/2 +1's and a/2 -1's. (i already see problems arising here, particularly if a is odd.. but i guess lets assume its even :X) well then, i now has a/2 possibilities.. so we get

|T| = (a/2)(n-1)(n-1)
we are trying show that |T| > (1/4)n^2(n − 1)
i.e
(a/2)(n-1)(n-1) > (1/4)n^2(n − 1)
if we take the minimal case.. i.e a = 1 then:
(n/2)(n-1)(n-1) > (1/4)n^2(n − 1)

and this is not true for all n.... but yeah this is the type of thing i have been trying and failing at.. please help :(

Last edited: Oct 2, 2011