Consider a $2^n \times 2^n$ Walsh-Hadamard matrix (via Sylvester's construction). Fix a set $S \subset [2^n]$ of $k\leq 2^{n-1}$ columns.

Consider the rows in the $2^n \times k$ submatrix $H'$ that's obtained by dropping all columns not in $S$. Then we have $2^n$ many $k$-long row vectors. Consider the equivalence relation defined by multiplication by $-1$: $u \sim v$ iff. $u = \pm v$. There are $2^{k}/2 = 2^{k-1}$ equivalence classes this way. Is it true that the number of rows of $H'$ in each equivalence class is the same?


1 Answer 1


The $2^n \times 2^n$ Walsh-Hadamard matrix is given explicitly by $$ M(u,v) = (-1)^{\langle u,v \rangle}, $$ where $u,v \in \{0,1\}^n$, and the inner product is given by $$ \langle u,v \rangle = \sum_{i=1}^n u_i v_i. $$ To simplify matters, we will assume henceforth that all computations are modulo 2.

If we restrict to columns $v_1,\ldots,v_k$, then we see a row $\beta_1,\ldots,\beta_k$ whenever $$ \langle u, v_i \rangle = \beta_i, \quad i \in [k]. $$ We can think of this as a linear system in $u_1,\ldots,u_n \in \mathbb{F}_2$. If the system has rank $r$, then there are either no solutions, or $2^{n-r}$ solutions.

In your case, you are identifying rows of the forms $\beta_1,\ldots,\beta_k$ and $\beta_1+1,\ldots,\beta_k+1$. A row is of one of these forms whenever $$ \langle u, v_i + v_k \rangle = \beta_i, \quad i \in [k-1]. $$ Again, this system either has no solutions, or $2^{n-r}$ solutions, where $r$ is the rank.

What this means is that every equivalence class of rows which appears at all, appears the same number of times.

In general, not all $2^{k-1}$ will appear. Indeed, there are only $2^n$ many rows, so if $k > n+1$ then this will certainly not be the case.

Another example is $n = 3$ and $S = \{0,\ldots,7\}$. Here only $4$ out of the $8$ possible equivalence classes appear, each of them appearing twice:

$$ \begin{bmatrix} 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 \end{bmatrix} $$

  • $\begingroup$ Thank you, @Yuval Filmus, I actually meant to tag you under my question because I hoped you'll know the answer, but somehow the system wouldn't let me. Thanks again for this informative answer. $\endgroup$
    – gen
    Commented Nov 14, 2021 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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