<p>I have the following question when I was going through the proof of the following theorem.</p>

<p><strong>Theorem.</strong> 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)$.</p>

<p>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.</p>

<hr>

<p><strong>My question is:</strong> 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)$?</p>

CC BY-SA 3.0
2018-01-05T15:06:31.217Z
In $F(xy)$ in your last equation, presumably $xy$ denotes concatenation?
kodlu
CC BY-SA 3.0
2018-01-05T15:07:48.537Z
Yes, that is correct.
withhighprob
<boolean-functions><fourier-analysis>
Relationship between sparsity and rank of a boolean function
withhighprob
# Relationship between sparsity and rank of a boolean function

(Asked by: username_0 on 2018-01-05)

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)$?

**Tags:** boolean-functions, fourier-analysis
> **Comments:**
> **username_1**: In $F(xy)$ in your last equation, presumably $xy$ denotes concatenation?  
> **username_0**: Yes, that is correct.  

---

## 0 answers

