(adsbygoogle = window.adsbygoogle || []).push({}); 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 :(

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Hadamard matrix proof-combinatorics

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**