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 matrices question

  1. Apr 15, 2016 #1
    1. The problem statement, all variables and given/known data
    Hadamard matrices H0, H1, H2, . . . are defined as follows:
    (a) H_0 is the 1 × 1 matrix [1].
    (b) For k > 0, H_k is the 2^k × 2^k matrix.
    \\Attached is the matrix

    (a) Show by induction that (H_k) ^2 = 2^k* I_k, where I_k is the identity matrix of dimension 2^k .
    (b) Note that Hadamard matrices are symmetric, i.e. H_k = Transpose(H_k) . Thus by the above, H_k*Transpose(H_ k) = 2^k* I_k as well. Use this fact for deriving a formula for the dot product between the i-th and j-th row of H_k, for 1 ≤ i, j ≤ 2^k .

    2. Relevant equations

    3. The attempt at a solution
    I already did part a. Just multiply two matrices of entries H_k as it's described in the file and then apply the inductive step to multiply two entries. At the end you get a coefficient of 2^k and the identity matrix on the upper-left and lower-right corner and zero matrices on the remaining places.

    B) My problem is in part B. I already know by definition that the dot product of two rows in a hadamard matrix is zero. I don't know how to derive the requested formula using the given hints. Suggestions?

    All I have is that the product between row i and rowj = dot product of column i and column j

    Half an hour later........

    Hence row i= column i because the matrices are symmetric, we can look for dot products when compute H_k * transpose(H_k)
    I think that the dot product(row i and row j)= ((H_k)^2)_i,j, so it would be 2^k*I_i,j

    Attached Files:

    Last edited: Apr 15, 2016
  2. jcsd
  3. Apr 15, 2016 #2
  4. Apr 15, 2016 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If ##H = H_{K-1}## and ##J = H_K##, then
    [tex] J = \pmatrix{H&H\\H&-H} [/tex]
    Now, it is a important fact that you can multiply partitioned matrices almost as though they had numerical elements instead of matrices as entries---provided that all "dimensions" are consistent with multliplication of the individual partition members. That is, if
    [tex] A = \pmatrix{A_{11}& A_{12}\\A_{21}& A_{22}}, \; B = \pmatrix{B_{11}&B_{12}\\B_{21}&B_{22}}, [/tex]
    are partitioned matrices with appropriate dimensions for the partitions, then
    [tex] A B = \pmatrix{A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\
    A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12}+A_{22}B_{22}} [/tex]
    provided that all the matrix products above are defined, as they would be for correctly-dimensioned partitions. Note that the formula for ##AB## is exactly the same as for the product of ##2 \times 2## matrices with numbers in place of the matrices ##A_{ij}, B_{ij}##.

    You can apply that to get ##J^2## in terms of ##H^2##.

    The result about multiplication of partitioned matrices is well-known and appears in many textbooks and web pages. Proving it from first principles is not very difficult.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted