Skip to main content
added 284 characters in body
Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

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

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

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

Source Link
Robert Israel
  • 54.2k
  • 1
  • 76
  • 152

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