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?

  • 3
    $\begingroup$ 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.) $\endgroup$ Apr 10, 2020 at 13:21
  • 1
    $\begingroup$ 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? $\endgroup$ Apr 11, 2020 at 13:52
  • 3
    $\begingroup$ 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}$. $\endgroup$ Apr 12, 2020 at 1:52

1 Answer 1


I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.

  • $\begingroup$ Mahdi (or anyone else who is able), I would love to see (links to) concrete examples or relevant references. $\endgroup$
    – tigercub97
    Apr 10, 2020 at 23:08
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 11, 2020 at 5:05

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.