Given $0/1$ $n\times n$ matrix $M$.

Suppose we have $2$ vectors $\lambda,\mu\in\Bbb R^{1\times n}$ such that both $$\lambda M\in\{0,1\}^{1\times n}$$ $$M\mu'\in\{0,1\}^{n\times 1}$$ holds with $'$ indicating transpose then when does it follow $$\lambda M\mu'\in\{0,1\}?$$

Denote $\mathcal R(M)$ as collection of rows of $M$ and $\mathcal C(M)$ as collection of columns of $M$.

It is clear picking $\begin{bmatrix}\lambda\\\mu\end{bmatrix}\in\Bbb R^{2\times n}$ from the collection $$\mathcal S=\Bigg\{\begin{bmatrix}\lambda\\\mu\end{bmatrix}\in\Bbb R^{2\times n}:\lambda M\subseteq \mathcal R(M),M\mu'\subseteq \mathcal C(M)\Bigg\}$$ suffices. Is there a bigger collection?

How do you characterize $$\mathcal T=\Bigg\{\begin{bmatrix}\lambda\\\mu\end{bmatrix}\in\Bbb R^{2\times n}:\lambda M\not\in \mathcal R(M),M\mu'\not\in\mathcal C(M), \lambda M\mu'\in\{0,1\}\Bigg\}$$ $$\mathcal U=\Bigg\{\begin{bmatrix}\lambda\\\mu\end{bmatrix}\in\mathcal T:\lambda M\in\{0,1\}^{1\times n},M\mu'\in\{0,1\}^{n\times1}\Bigg\}$$ that works?


I think if we pick any minimal subset $\mathcal W\subsetneq U$ such that the collection of $\lambda\otimes\mu$ in $\begin{bmatrix}\lambda\\\mu\end{bmatrix}\in\mathcal W$ spans $\Bbb R^{n^2}$ then maximum of $|\mathcal W|$ among all such subsets satisfy $|\mathcal W|\approx\alpha2^{\beta\sqrt n}$ asymptotically for some fixed $\alpha,\beta>0$


Your Answer

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