Cuántos 1 puede regular 0,1-matriz contienen?

Question

Una matriz de orden $n$ tiene todas sus entradas en $\{0,1\}$. ¿Cuál es el número máximo de $1$ en la matriz para la cual la matriz es no singular.

Answer 1

Supongamos que la matriz de $A\in\{0,1\}^{n\times n}$, por la encasillar principio si $A$ ha estrictamente más de $n^2-(n-1)$ cero entradas, entonces al menos dos columnas están llenas de unos y por lo tanto son linealmente dependientes. Se deduce entonces que el $A$ no tiene rango completo (y por lo tanto es singular). Ahora, la matriz $A\in\{0,1\}^{n\times n}$ definido por $$A_{i,j}=\begin{cases} 1 & \text{if } i \neq j \\ 1 & \text{if } i=j=n\\ 0 &\text{else}\end{cases}$$ es nonsingular y por lo tanto el límite usted está buscando es $n^2-(n-1)=n^2-n+1$.

Answer 2

Debería ser $n^2-n+1$. Deje $v=e_1+\cdots+e_n$ donde $\{e_1, \cdots, e_n\}$ es el estándar ortonormales. A continuación, la matriz con los vectores fila $\{v, v-e_1, \cdots, v-e_{n-1}\}$ es una matriz que contiene el número máximo de 1 para que se nonsingular.