Maximizing/Minimizing the Operator norms of 0-1 matrices subject to a constraint

Question

Fix $n$ and let $B, C$ be two $n \times n$ 0-1 matrices of full rank such that $\sum_{i,j} b_{i,j}^2 = \sum_{i,j} c_{i,j}^2$, in other words they have the same number of $0$ entries and the same number of $1$ entries. I want to find $\alpha_n = \max ||B||/||C||$ subject to this constraint as a function of $n$.

Answer 1

Take $B$ to have $1$s on the main diagaonal and the first superdiagonal, then $\|B\|\leq 2$. If we take $C$ to have $1$s on the diagonal and filling the last column, then $\|C\|\geq \sqrt{n}$. (These both have full rank and $2n-1$ $1$'s.) This shows that $\alpha_n\geq \frac{\sqrt{n}}{2}$, though from the examples in Robert Israel's answer this bound is not optimal.

EDIT: For example when $n=5$:

\begin{equation*} B= \begin{pmatrix} 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1& 1 \\ 0 & 0 & 0 & 0 & 1\end{pmatrix} , \quad C= \begin{pmatrix} 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1\end{pmatrix} \end{equation*}

Answer 2

The answer is $\sqrt{n}$. You can argue as follows:

1. We know that $$\| X\| \le \| X \|_2 \le \sqrt{n} \cdot \| X\|,$$ for any $X\in M_n$. The condition on $B$ and $C$ implies that $$\| B\|_2 = \| C\|_2.$$ Hence $$a_n = \max \frac{\| B \|}{\| C\|} \le \max \frac{\| B\|_2}{\| C\|} = \max \frac{\| C\|_2}{\| C\|} \le \sqrt{n}.$$

2. Take $$B =\left( \begin{array}{cccc} 1 & 1& \dots&1 \\ 0&0&\dots&0 \\ \vdots&\vdots&\ddots& \vdots \\ 0&0&\dots&0\end{array}\right), \quad C = \left( \begin{array}{cccc} 1 & 0& \dots&0 \\ 0&1&\dots&0 \\ \vdots&\vdots&\ddots& \vdots \\ 0&0&\dots&1\end{array}\right).$$ Then $$\frac{\| B\|}{\| C\|} = \sqrt{n}.$$

3. Well, you see that the answer is $\sqrt{n}$.

Answer 3

In the case $n=2$, all $2 \times 2$ $0-1$ matrices of full rank are equivalent (under permutation of rows or columns) to either $I$ or $\pmatrix{1 & 1\cr 0 & 1\cr}$, so the answer in that case is $\alpha_2 = 1$.

In the case $n=3$, the calculation is not so trivial. I find that $\alpha_3 = \sqrt{r}/2 \approx 1.123489802$ where $r$ is the largest root of $x^3 - 6 x^2 + 5 x - 1$, obtained for $$ B = \pmatrix{1 & 1 & 1\cr 0 & 1 & 1\cr 0 & 0 & 1\cr},\ C = \pmatrix{0 & 1 & 1\cr 1 & 0 & 1\cr 1 & 1 & 0\cr}$$

At least this indicates that the answer won't be as simple as $\sqrt{n}$.

EDIT: For $n=4$ I find $\alpha_4 \approx 1.195592875$, corresponding to $$ B = \left( \begin {array}{cccc} 1&0&1&1\\ 0&1&0&0 \\ 0&0&1&1\\ 0&0&0&1\end {array} \right),\ C = \left( \begin {array}{cccc} 0&0&1&1\\ 0&1&0&1 \\ 1&0&1&0\\ 1&0&0&0\end {array} \right) $$