Monday, June 27, 2022
HomeSoftware DevelopmentGenerate Hadamard matrix of given order

Generate Hadamard matrix of given order


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)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments