I have the following question when I was going through the proof of the following theorem.

Theorem. For XOR function $f \circ XOR$, $rank(M_{f \circ XOR}) = ||\hat f ||_0$ where $M_{f \circ XOR}$ is a matrix such that $M_{f \circ XOR}(x,y) = f(x + y)$.

The proof of this theorem essentially shows that fourier coefficients of $f$ are the eigen values of $M$: $\hat f(S)$ is an eigen value and the corresponding eigen vector is $\chi_S$. And now, using spectral decomposition, one can conclude that the rank is equal to the sparsity.

My question is: Consider any function $F:\{0,1\}^N \rightarrow \{0,1\}$, and let $M_F \in \{0,1\}^{N/2} \times \{0,1\}^{N/2}$ be a $2^{N/2} \times 2^{N/2}$ dimensional matrix whose entries are as follows: $$M_F(x,y) = F(xy).$$ Is there any relationship between $||\hat F||_0$ and $rank(M_F)$?

  • $\begingroup$ In $F(xy)$ in your last equation, presumably $xy$ denotes concatenation? $\endgroup$ – kodlu Jan 5 '18 at 15:06
  • $\begingroup$ Yes, that is correct. $\endgroup$ – sagnik Jan 5 '18 at 15:07

Your Answer

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

Browse other questions tagged or ask your own question.