2
$\begingroup$

Given a symmetric matrix $M\in\Bbb Z^{n\times n}$ or rank $r$ with absolute value of any entry bound by $2^{b^2-1}-1$ and maximum eigenvalue at most $\lambda$.

We consider the set $\mathcal T_b$ of $\pm1$ matrices of size $b\times b$.

We consider an injection $$\sigma:\{-2^{b^2-1}+1,-2^{b^2-1}+2,\dots,-1,0,1,\dots,2^{b^2-1}-2,2^{b^2-1}-1\}\rightarrow\mathcal T_b$$ and with abuse of notation denote $\sigma(M)$ to be $\pm1$ matrix of size $bn\times bn$ such that every $M_{ij}$ is replaced by corresponding $b\times b$ matrix $\sigma(M_{ij})$.

Denote set of $b^2$ submatrices of size $n\times n$ with $ij$th entry coming from $\sigma(M_{ij})$ by $M_\sigma$.

Is there at least one $\sigma^\star$ such that there is $n\times n$ submatrix in $M_{\sigma^\star}$ with rank $\leq r$ and maximum eigenvalue $\leq \lambda$?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.