• Support PF! Buy your school textbooks, materials and every day products Here!

Hadamard matrices question

  • #1

Homework Statement


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 .

Homework Equations




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
 

Attachments

Last edited:

Answers and Replies

  • #2

Homework Statement


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 .

Homework Equations




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.

All I have so far is that the dot product between row i and row j is equal to the product between column i and column j

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?
 
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement


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 .

Homework Equations




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
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.
 

Related Threads on Hadamard matrices question

  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
18
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
8
Views
2K
Replies
2
Views
2K
Top