<p>I don't think parities are the only orthonormal Boolean basis, for example <a href="https://en.wikipedia.org/wiki/Paley_construction" rel="noreferrer">Paley basis</a> provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.</p>

CC BY-SA 4.0
2020-04-10T23:08:42.197Z
Mahdi (or anyone else who is able), I would love to see (links to) concrete examples or relevant references.
tigercub97
CC BY-SA 4.0
2020-04-11T05:05:54.060Z
You can just arrange any orthonormal basis as a $2^n \times 2^n$ matrix (one row per basis function, one column per evaluation point). This is an orthonormal matrix with (normalized) +1/-1 entries, and any such matrix is called a Hadamard matrix (as Emil also pointed out). Parities create Hadamard matrices, but there are other non-parity Hadamard matrices in some cases, such as Paley's construction above.
Mahdi Cheraghchi
CC BY-SA 4.0
2020-04-10T18:03:38.120Z
2020-04-11T05:02:06.730Z
2020-04-11T05:02:06.730Z
Mahdi Cheraghchi
<p>Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can form an orthonormal basis for Boolean functions? </p>

<p>If not, why not?</p>

CC BY-SA 4.0
2020-04-10T13:21:18.520Z
A useful keyword: an orthonormal basis of Boolean functions in $n$ variables is essentially the same thing as an [Hadamard matrix](https://en.wikipedia.org/wiki/Hadamard_matrix) of order $2^n$. (The standard basis of “parity functions” corresponds to the Sylvester/Walsh matrix.)
Emil Jeřábek
CC BY-SA 4.0
2020-04-11T13:52:20.593Z
What @EmilJeřábek wrote and the answer by Mahdi assume that OP is looking for an orthonormal basis of the vector space of (real valued) functions on $\{-1, +1\}$ such that the basis functions themselves are boolean. Is this what the question is asking? Are the basis functions required to be boolean?
Sasho Nikolov
CC BY-SA 4.0
2020-04-12T01:52:49.913Z
If the basis is not required to be Boolean, the question would be trivial: simply take any orthonormal basis for the vector space $\mathbb{R}^{2^n}$.
Mahdi Cheraghchi
<soft-question><boolean-functions><fourier-analysis>
Is the basis of parity functions the only orthonormal basis for Boolean functions?
tigercub97
# Is the basis of parity functions the only orthonormal basis for Boolean functions?

(Asked by: username_0 on 2020-04-08)

Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can form an orthonormal basis for Boolean functions?

If not, why not?

**Tags:** soft-question, boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: A useful keyword: an orthonormal basis of Boolean functions in $n$ variables is essentially the same thing as an [Hadamard matrix](https://en.wikipedia.org/wiki/Hadamard_matrix) of order $2^n$. (The standard basis of “parity functions” corresponds to the Sylvester/Walsh matrix.)  
> **username_2**: What @EmilJeřábek wrote and the answer by Mahdi assume that OP is looking for an orthonormal basis of the vector space of (real valued) functions on $\{-1, +1\}$ such that the basis functions themselves are boolean. Is this what the question is asking? Are the basis functions required to be boolean?  
> **username_3**: If the basis is not required to be Boolean, the question would be trivial: simply take any orthonormal basis for the vector space $\mathbb{R}^{2^n}$.  

---

## 1 answers

### Answer by username_3 on 2020-04-10. Score: 8 | Accepted answer

I don't think parities are the only orthonormal Boolean basis, for example [Paley basis](https://en.wikipedia.org/wiki/Paley_construction) provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.

> **Comments:**
> **username_0**: Mahdi (or anyone else who is able), I would love to see (links to) concrete examples or relevant references.  
> **username_3**: You can just arrange any orthonormal basis as a $2^n \times 2^n$ matrix (one row per basis function, one column per evaluation point). This is an orthonormal matrix with (normalized) +1/-1 entries, and any such matrix is called a Hadamard matrix (as Emil also pointed out). Parities create Hadamard matrices, but there are other non-parity Hadamard matrices in some cases, such as Paley's construction above.  

---

