# Is the basis of parity functions the only orthonormal basis for Boolean functions?

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?

• A useful keyword: an orthonormal basis of Boolean functions in $n$ variables is essentially the same thing as an Hadamard matrix of order $2^n$. (The standard basis of “parity functions” corresponds to the Sylvester/Walsh matrix.) Apr 10 '20 at 13:21
• 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? Apr 11 '20 at 13:52
• 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}$. Apr 12 '20 at 1:52

• 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. Apr 11 '20 at 5:05