Math Problems Vault

Problem 7.2.1

If a matrix $A$ of size $n \times n$ has all entries of absolute value at most $1$ , then $\left|\operatorname {det}\left(A\right)\right| \leq n^{n/2}$ .

A square matrix $H$ is called a Hadamard matrix if all its entries are equal to $\pm 1$ and $H \cdot H^{T} = nE_{n}$ , where $n$ is the order of the matrix $H$ and $E_{n}$ is the identity matrix.

?

Problem 7.2.2

Construct an $n \times n$ Hadamard matrix for

?

(1)

$n = 2$ ;

(2)

$n = 4$ ;

(3)

$n = 8$ ;

(4)

$n = 16$ ;

(5)

$n = 12$ .

Problem 7.2.3

(1)(2)(3)(4)

?

(1)

Any two columns of a Hadamard matrix are orthogonal.

(2)

A matrix is a Hadamard matrix if and only if its entries are equal to $\pm 1$ and any two of its rows are orthogonal.

(3)

Hadamard matrices attain the upper bound in Hadamard's theorem 7.2.1. (Hadamard matrices got their name owing to this result.)

(4)

If there exists an $n \times n$ Hadamard matrix and $n > 2$ , then $n$ is divisible by $4$ .

Remark.

?

Conjecture. An $n \times n$ Hadamard matrix exists for every number $n$ divisible by $4$ .

The conjecture has not been proved even for some numbers less than $1000$ , namely: for $668, 716, 892$ .

Problem 7.2.4

(1)(2)

Solving this problem and the next one (7.2.5) requires the basic properties of quadratic residues; see [GIM, § 9], [Vi, § 5], [ZSS, Sec. 3.3].

For a prime number $p$ , denote $S_{d} = S_{p,d} := \sum \limits_{j \in \mathbb {Z}_{p}} \left(\dfrac {j(j+d)}{p}\right)$ (this is a sum of Legendre symbols).

?

(1)

Prove that $S_{d}$ does not depend on $d \neq 0$ .

(2)

Find $S_{d}$ for each $d \in \mathbb {Z}_{p}$ .

Problem 7.2.5

(1)(2)(3)(4)

Solving this problem (along with the previous one, 7.2.4) requires the basic properties of quadratic residues; see [GIM, § 9], [Vi, § 5], [ZSS, Sec. 3.3].

Construct an $n \times n$ Hadamard matrix for

?

(1)

$n = 2a$ if there exists an $a \times a$ Hadamard matrix;

(2)

$n = ab$ if there exist $a \times a$ and $b \times b$ Hadamard matrices;

(3)

$n = p+1$ , where $p$ is a prime number of the form $4k-1$ ;

(4)

$n = 2p+2$ , where $p$ is a prime number of the form $4k+1$ .

Problem 7.2.6

A Hadamard matrix is called normalized if its first row and first column consist entirely of ones.

Write out all normalized Hadamard matrices of orders $1; 2; 4$ .

?

Problem 7.2.7

(1)(2)

The Hadamard property of a matrix is preserved under the following transformations:

?

(1)

multiplying a row or a column by $-1$ ;

(2)

interchanging rows or columns.

Hadamard matrices obtained from each other by applying some number of transformations (1) and (2) are called equivalent.

Problem 7.2.8

(1)(2)

?

(1)

Which of the matrices from Problem 7.2.6 are equivalent?

(2)

Every Hadamard matrix is equivalent to some normalized one.

The number of equivalence classes: for orders $1, 2, 4, 8, 12$ — $1$ , $16$ — $5$ , $20$ — $3$ , $24$ — $60$ , $28$ — $487$ , $32$ — more than a million.

Problem 7.2.9

Is it true that for any Hadamard matrices $H$ and $H'$ the matrices $H \otimes H'$ and $H' \otimes H$ are equivalent? Here the tensor product $\otimes$ is defined in the hint to Problem 7.2.5 (1, 2).

?

Problem 7.2.10

The Hadamard matrix $H$ built by means of the (Paley) construction from Problem 7.2.5 (4) is equivalent to the matrix $H^{T}$ .

?

Problem 7.2.11

Does there exist a Hadamard matrix $H$ that is not equivalent to the matrix $H^{T}$ ?

?