Generate Hadamard matrix of given order

Hadamard matrix is a square matrix with the unique property that any two of its rows are orthogonal. In geometric terms that means that the two rows denote two perpendicular vectors and in combinatorial terms, it means that the two rows have matching elements in exactly half places and the other half elements are mismatching.

Some important properties of a Hadamard matrix are:

• The first order Hadamard matrix is {{1}}. 
• A Hadamard matrix contains only +1 and -1 as its elements.
• Any 2^m order Hadamard matrix can be constructed using 2^m-1 order Hadamard matrices in the following way. This facilitates the easy generation of the matrix if we know the lower-order matrices.

H_2m
{ {H_2m-1 ,  H_2m-1}
  {H_2m-1, -H_2m-1}}

Given a non-negative integer M, the task is to generate a Hadamard matrix of order 2^M.

Examples: 

Input: M = 2
Output:
1 1 1 1
1 -1 1 -1
1 1 -1 -1
1 -1 -1 1

Input: M = 3
Output:

Hadamard matrix of order 8

Approach: This is a simple implementation based problem. The idea is to use the above relation and iterate from order 1 to 2^M to generate a Hadamard matrix of order  2^M.

Follow the steps mentioned below to implement the idea.

• Calculate 2^M (say N)and store it. 
• Declare a matrix of order N. 
• Now initializing the 0^th column 0^th row element of the matrix as 1.
• Subsequently, run a loop that copies the top left quarter in the other quarters with a correct sign following the property of the Hadamard matrix as shown earlier in this article. The size of the matrix grows in each iteration and eventually reaches the order N. 
• Finally, display the matrix on the console.

Below is the implementation of the above approach.

1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 

Time Complexity: O(2^M)
Auxiliary Space: O(2^M)