Generate Hadamard matrix of given order | By The Digital Insider






Improve Article


Save Article


Like Article





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 2m order Hadamard matrix can be constructed using 2m-1 order Hadamard matrices in the following way. This facilitates the easy generation of the matrix if we know the lower-order matrices.



H2m
H2m-1 ,  H2m-1
  H2m-1, -H2m-1



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


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

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 2M to generate a Hadamard matrix of order  2M.


Follow the steps mentioned below to implement the idea.



  • Calculate 2M (say N)and store it. 

  • Declare a matrix of order N

  • Now initializing the 0th column 0th 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.



Java














  


import java.util.*;


  


class GFG


  


    public static void generate(int M)


    


        


        


        int n = (int)Math.pow(2, M);


  


        


        int[][] hadamard = new int[n][n];


  


        


        


        hadamard[0][0] = 1;


        for (int k = 1; k < n; k += k)


  


            


            


            for (int i = 0; i < k; i++)


                for (int j = 0; j < k; j++)


                    hadamard[i + k][j]


                        = hadamard[i][j];


                    hadamard[i][j + k]


                        = hadamard[i][j];


                    hadamard[i + k][j + k]


                        = -hadamard[i][j];


                


            


        


  


        


        for (int i = 0; i < n; i++)


            for (int j = 0; j < n; j++)


                System.out.print(hadamard[i][j] + " ");


            


            System.out.println();


        


    


  


    


    public static void main(String[] args)


    


        int M = 2;


  


        


        generate(M);


    










Output
1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 


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




#Article, #Code, #Combinatorial, #Mathematical, #Matrix
Published on The Digital Insider at https://bit.ly/3wWJJ5M.

Comments