Hadamard Matrix In C++

Hadamard matrix was created as a solution to Hadamard’s maximum determinant problem which is to find a matrix with the maximum possible determinant where an element of the matrix, Xij has a value such that |Xij|<=1. Hadamard matrix is a square matrix of order n where the size of the matrix is n x n. This type of matrix is made up elements whose value is either 1 or -1.

Hadamard matrices can be of the order n= 1, 2 or any positive multiple of 4.  Writing a generalized code for creating a Hadamard matrix of the order n for all possible values of n is not possible as they follow different rules. However, we can write a generalized code for creating a Hadamard matrix of the order n, where n=2k(k being a non-negative integer). Therefore, in this tutorial, we’ll only be going over the code for Hadamard matrices of the order n where n=2k.

Hadamard matrix of order 1 contains only one element that has the value 1. Let’s look at Hadamard matrices of order 2 and 4-

Hadamard Matrix In C++

Implementation of Hadamard matrix in C++

#include <iostream>
#include <cmath>
using namespace std;


int main(){
    
    int n;
    cin>>n;
    if(int(log2(n))-log2(n)!=0){
        cout<<"Number is not a power of 2"<<endl;
    }
    else{
    int hadamard[n][n];
    hadamard[0][0]=1;
    for(int x=1;x<n;x+=x){
        for(int i=0;i<x;i++){
            for(int j=0;j<x;j++){
                hadamard[i+x][j]=hadamard[i][j];
                hadamard[i][j+x]=hadamard[i][j];
                hadamard[i+x][j+x]=-hadamard[i][j];
            }
        }
        
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<hadamard[i][j]<< " ";
        }
        cout<<endl;
    }
    
 }
    return 0;
}

 

The if condition first checks if the number provided for n is a perfect power of 2 and executes the code if it is. The outermost for loop runs for log2(n) iterations(x ranging from 1 to n/2)and by the end of every iteration, values for a hadamard matrix of order x have been filled inside the n x n matrix that we are trying to fill in order to create a hadamard matrix of order n. The two nested for loops inside the outermost for loop fill in the values in the matrix according to the rule that we just saw when we observed the relation between hadamard matrices of order 2 and 4.

Let’s take a look at the output for n=8-

Input

8

Output

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

We can clearly notice that the hadamard matrix of order 8 that our code has created shares the same relation with the hadamard matrix of order 4 that the hadamard matrix of order 4 shares with that of order 2.

Find K’th largest element in a stream in C++

Leave a Reply

Your email address will not be published. Required fields are marked *