title: Existence of Hadamard matrix of size NxN
body: <p>You are given an integer N with N &lt;=100. Is there a Hadamard matrix of size NxN, such that:</p>
  
  <ul>
  <li>Each element of the matrix is either 1 or -1. </li>
  <li>The sum of products of corresponding elements of any two rows is zero i.e. for any a &lt;= N and b &lt;= N  M[a][1]*M[b][1] + M[a][2]*M[b][2]...M[a][n]*M[b][n] = 0 (considering 1 based indexing).</li>
  </ul>
  
  <hr>
  
  <p><strong>What I have done:</strong></p>
  
  <p>I have tried a brute force solution. Each element can either be 1 or -1. So there can be at most 2<sup>(n<sup>2</sup>)</sup> matrices. I tried checking all of these matrices but the algorithm is way too slow. O(n<sup>2</sup> * (2<sup>(n<sup>2</sup>)</sup>) actually. My computer did not show any output for n = 5 and I had to terminate the program. </p>
  
  <p>Can anybody suggest a better way to solve this problem?</p>
  
  <p><strong>Edit:</strong> You have to not only answer Yes or No but enumerate one such matrix too. Obviously when N is odd the answer is not possible. N = 1 is a trivial case with answer as 1 or -1.</p>