Creating a set of vectors Suppose we are given a number k, and we have to construct $2^k$ vectors in $2^k$ dimensional space using only the coordinates 1 and -1 so that all the vectors are orthogonal to each other. How can such a construction be made?
For, example, for k=2, a valid construction might be
1,1,-1,-1
1,1,1,1
1,-1,1,-1
1,-1,-1,1

A matrix $A \in M_n(\mathbb{R})$ is called a Hadamard matrix of order $n$ if the entries of $A$ are $\pm 1$ and the columns of $A$ are mutually orthogonal. Using the notion above, you ask how can one construct a Hadamard matrix of order $2^k$. The basic observation is that if $H$ is a Hadamard matrix of order $n$ then the block matrix
$$ \hat{H} := \begin{pmatrix} H & H \\ H & -H \end{pmatrix} $$
is a Hadamard matrix of order $2n$. Starting with the $1 \times 1$ Hadamard matrix $(1)$, one can repeatedly apply this observation to create Hadamard matrices of order $2^k$ for all $k \in \mathbb{N}$.
