0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jul 24 '14 at 12:48
  • $\begingroup$ @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. " $\endgroup$ – hungryfoolish Jul 24 '14 at 15:06
  • $\begingroup$ OK, so you are looking at $n$ vectors, each with $n/2$ components. I think I understand. $\endgroup$ – Gerry Myerson Jul 24 '14 at 23:43
  • $\begingroup$ I posted an answer yesterday. Is it what you had in mind? $\endgroup$ – Gerry Myerson Jul 26 '14 at 4:21
  • $\begingroup$ 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. $\endgroup$ – hungryfoolish Jul 26 '14 at 13:29
1
$\begingroup$

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 -++-.

If that's not what you mean, please post an example to illustrate your meaning.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks, yes, that is what I mean, but I am looking for the minimum, which I forgot to add to the description. $\endgroup$ – hungryfoolish Jul 26 '14 at 13:34
0
$\begingroup$

I recognize this is late, but I have an answer for the minimum number of sign patterns.

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}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.