# What is the minimum number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices?

Given a Hadamard matrix of size $n$, I want to know what is the minimum number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same.

My guess is exactly $\frac n2$. It is true for the Sylvester construction. Does it remain true in general when their columns and rows are permuted? If yes, any clue on how to prove it formally will be helpful.

• Any two columns are orthogonal, right? No vector is orthogonal to itself (not counting the zero vector), so no two columns are the same; all $n$ sign patterns are different. – Gerry Myerson Jul 24 '14 at 12:48
• @GerryMyerson Sorry, it was not clear perhaps. There are $n$ different sign patterns in total. But, how many do you find in $n/2$ columns, composed of $n$ rows? I am counting for each row in those columns. Also, "I count a sign pattern and its negation to be the same. " – hungryfoolish Jul 24 '14 at 15:06
• OK, so you are looking at $n$ vectors, each with $n/2$ components. I think I understand. – Gerry Myerson Jul 24 '14 at 23:43
• I posted an answer yesterday. Is it what you had in mind? – Gerry Myerson Jul 26 '14 at 4:21
• Thanks, yes, I was thinking of this. Only that I forgot to put in a vital word. I was looking for the minimum number of sign patterns. I understand that the maximum is always $n$, since that is the total number of sign patterns in a Hadamard matrix anyway. – hungryfoolish Jul 26 '14 at 13:29

I'm still not sure I understand the question, but consider the Hadamard matrix $$\matrix{+&+&+&+&+&+&+&+\cr-&+&+&+&-&+&-&-\cr-&-&+&+&+&-&+&-\cr-&-&-&+&+&+&-&+\cr-&+&-&-&+&+&+&-\cr-&-&+&-&-&+&+&+\cr-&+&-&+&-&-&+&+\cr-&+&+&-&+&-&-&+\cr}$$ The first 4 columns have the 8 different sign patterns ++++, -+++, --++, ---+, -+--, --+-, -+-+, and -++-.
Suppose you have a matrix $A\in M_M(\mathbb{R})$. To find the number of sign pattern combinations in the first $\frac{n}{2}$ rows, we first count the number of all possible unique sign patterns with length $n$. We can think of this as a 0-1 list of length $n$, so all possible lists is $2^n$. However, since a sign pattern and its negation are equal, and each sign pattern only has one negation, the total number of unique lists is $2^{n-1}$.
Now, since we are looking at the first $\frac{n}{2}$ rows, we merely choose $\frac{n}{2}$ non-equal patterns of our $2^{n-1}$ list. Hence, the minimum number of sign patterns is exactly $2^{n-1} \choose \frac{n}{2}$.