# On the complexity of writing down matrices

Consider families of $0/1$ matrices in $\Bbb B$ where $1+1=1$:

1. $\mathcal M_{1,n,c}$ contains $2^n\times 2^n$ matrices that can be written as Hadamard product of $t=O(2^{(\log n)^c})$ matrices $$(J_n-M_1)\circ\dots\circ (J_n-M_{t})=M$$ where $J_n$ is $2^n\times 2^n$ all $1$ matrix and $M_i$ are rank $1$ matrices.

2. $\mathcal M_{2,n,c}$ contains $2^n\times 2^n$ matrices that can be written as sum of $t=O(2^{(\log n)^c})$ rank at most $1$ matrices $$M_1+\dots+M_{t}=M$$

3. $\mathcal M_{3,n,c}$ contains $2^n\times 2^n$ matrices that can be written as $$(J_n-M_{11})\circ\dots\circ(J_n-M_{1t})+\dots+(J_n-M_{t1})\circ\dots\circ(J_n-M_{tt})=M$$ where $J_n$ is $2^n\times 2^n$ all $1$ matrix and $M_{ij}$ are rank $1$ matrices at some $t=O(2^{(\log n)^c})$.

4. $\mathcal M_{4,n,c}$ contains $2^n\times 2^n$ matrices that can be written as $$(M_{11}+\dots+M_{1t})\circ\dots\circ(M_{t1}+\dots+M_{tt})=M$$ where $M_{ij}$ are rank $1$ matrices at some $t=O(2^{(\log n)^c})$.

How to find a family $\mathcal M_n$ such that for every $c>0$ there is an $n'\in\Bbb N$ such that for all $n>n'$

1. $\mathcal M_n\cap\mathcal M_{1,n,c}=\emptyset$, $\mathcal M_n\cap\mathcal M_{2,n,c}=\emptyset$ however there is a $c'>0$ such that $\mathcal M_n\cap\mathcal M_{3,n,c'}\not=\emptyset$?

How to find a family $\mathcal M_n$ such that for every $c>0$ there is an $n'\in\Bbb N$ such that for all $n>n'$

1. $\mathcal M_n\cap\mathcal M_{1,n,c}=\emptyset$, $\mathcal M_n\cap\mathcal M_{2,n,c}=\emptyset$ however there is a $c'>0$ such that $\mathcal M_n\cap\mathcal M_{4,n,c'}\not=\emptyset$?

How to find a family $\mathcal M_n$ such that for every $c>0$ there is an $n'\in\Bbb N$ such that for all $n>n'$

1. $\mathcal M_n\cap\mathcal M_{1,n,c}=\emptyset$, $\mathcal M_n\cap\mathcal M_{2,n,c}=\emptyset$ however there is a $c'>0$ such that $\mathcal M_n\cap\mathcal M_{3,n,c'}\cap\mathcal M_{4,n,c'}\not=\emptyset$?

Are there any tools to understand this problem?