Timeline for Square submatrix
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2013 at 20:37 | comment | added | user27805 | $a_{1(n-1)} = a_{1n} = 0$ $a_{2n} = a_{21} = 0$ $\dots$ $a_{n(n-2)} = a_{n(n-1)} = 0$ So there are $4n^2 - 4n$ $1$s; $4n$ $0$s. Let $x_1,\dots, x_n$ be the row #s of square submatrix. Let $y_1,\dots, y_n$ be the column #s of square submatrix. If we have $x_1, y_1$, then we should remove $2$ of columns that doesn't contain $x_1$. For $x_2, y_1$, then we should remove at least $1$ more columns, \dots After $x_10, y_1$, we should remove at least $11$ columns at total. So for that distribution of $1$s, one can never find a $10\times10$ submatrix. So I think $k>4n^2-4n$. | |
| Mar 11, 2013 at 19:13 | comment | added | Gerhard Paseman | In fact, the diagonal, plus n elements in a row and n corresponding elements in a corresponding column also seems to work. Maybe further tweaking will easily take the number of zeros needed from $4n$ down to $3n$? Gerhard "Ask Me About System Design" Paseman, 2013.03.11 | |
| Mar 11, 2013 at 19:02 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |