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$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.