Hadamard matrices question

[Sebastian Martinez]

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

 

[Sebastian Martinez]

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?

 

[Ray Vickson]

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
$$J = \pmatrix{H&H\\H&-H}$$
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
$$A = \pmatrix{A_{11}& A_{12}\\A_{21}& A_{22}}, \; B = \pmatrix{B_{11}&B_{12}\\B_{21}&B_{22}},$$
are partitioned matrices with appropriate dimensions for the partitions, then
$$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}}$$
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.