Return to Question

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})$.

1. How much could the rank $r$ and the maximum eigenvalue $\lambda$ change?

2. Could we find the distribution of ranks and of maximum eigenvalue over all possible injections?

If we consider non-symmetric $M$ will the answers change much?

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

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})$.

1. How much could the rank $r$ and the maximum eigenvalue $\lambda$ change?

2. Could we find the distribution of ranks and of maximum eigenvalue over all possible injections?

If we consider singular values will the answers change much if $M$ is not symmetric?

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})$.

1. How much could the rank $r$ and the maximum eigenvalue $\lambda$ change?

2. Could we find the distribution of ranks and of maximum eigenvalue over all possible injections?

If we consider non-symmetric $M$ will the answers change much?

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 following operation. 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})$.

1. How much could the rank $r$ and the maximum eigenvalue $\lambda$ change?

2. Could we find the distribution of ranks and of maximum eigenvalue over all possible injections?

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})$.

1. How much could the rank $r$ and the maximum eigenvalue $\lambda$ change?

2. Could we find the distribution of ranks and of maximum eigenvalue over all possible injections?

If we consider singular values will the answers change much if $M$ is not symmetric?