Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hadamard matrix proof-combinatorics

  1. Oct 2, 2011 #1
    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


    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)
    (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
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?