1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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?
Draft saved Draft deleted