Hadamard matrices H0, H1, H2, . . . are defined as follows:
(a) H_0 is the 1 × 1 matrix .
(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 .
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
25.6 KB Views: 321