You are given an integer $N$. ($N \le 100$). Does there exists a matrix $A$ of size $N\times N$ with the following properties?
- Each element of $A$ is either 1 or -1.
- The sum of products of corresponding elements of any two rows is zero. i.e. for any $1 \le i < j \le N$ $$ \sum_{k=1}^N A_{i,k}A_{j,k} = 0. $$ ( I am considering 1 based indexing here)
What I have done: I have tried a brute force solution. Each element can either be 1 or -1. so there can be at most $2^{N^2}$ matrices. I tried checking all of these matrices but the algorithm is way too slow. $O(N^2 2^{N^2})$ actually. My computer did not show any output for $N = 5$ and I had to terminate the program. Can anybody suggest a better way to solve this problem?
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.
Such matrices are called Hadamard matrices. As you can read in the section on the Hadamard conjecture, the problem of their existence is open. What is known is that if a Hadamard matrix for $N$ exists, then $N$ is $1$, $2$ or a multiple of $4$. The smallest order for which existence is currently unknown is $N=668$.
Since you imposed the constraint $N\le100$, the answer is that a Hadamard matrix exists if and only if $N$ is $1$, $2$ or a multiple of $4$.