= Solution
The <rank of a matrix> is the <dimension of a vector space>[dimension] of its <column space>, equivalently the dimension of the <image of a linear map> represented by the matrix. For $A\in\mathcal M_n$, the <rank-nullity theorem> gives
$$
\operatorname{rank}A=n
\iff \ker A=\{0\}
\iff A\text{ is injective}.
$$
An injective endomorphism of a finite-dimensional <vector space> is <surjective function>[surjective], hence <invertible matrix>[invertible]. By the <adjugate matrix> identity
$$
A\operatorname{adj}A=(\det A)I,
$$
$A$ is invertible when $\det A\ne0$; conversely, <multiplicativity of the determinant> shows that an invertible $A$ has nonzero <determinant>. Therefore
$$
\boxed{\operatorname{rank}A=n\iff A\text{ is nonsingular}\iff\det A\ne0}.
$$
Let $E_{ij}$ be the <matrix unit> with its only nonzero entry at $(i,j)$. The following $n^2$ matrices are all nonsingular:
$$
\mathcal B=\{I\}\cup\{I+E_{ij}:(i,j)\ne(n,n)\}.
$$
Indeed, $I+E_{ij}$ is an elementary shear when $i\ne j$, while $I+E_{ii}$ is diagonal with one diagonal entry equal to two. Their <linear span> contains every $E_{ij}$ except initially $E_{nn}$, because $E_{ij}=(I+E_{ij})-I$, and it then contains
$$
E_{nn}=I-\sum_{i=1}^{n-1}E_{ii}.
$$
Thus $\mathcal B$ spans the $n^2$-dimensional space $\mathcal M_n$ and, having $n^2$ members, is a <basis>. This also covers $n=1$, when $\mathcal B=\{I\}$.
Now let $A$ be a nonsingular <zero-one matrix>. If it had fewer than $n-1$ zero entries, at least two rows would contain no zero at all. Those two rows would both be the all-one row, contradicting <linear independence>. Hence every such matrix has at most
$$
\boxed{c_n\le n^2-n+1}
$$
ones. The bound is attained. Let $J$ be the all-one matrix and set
$$
A=J-\operatorname{diag}(1,\ldots,1,0),
$$
where there are $n-1$ initial diagonal ones. If $A\mathbf x=0$ and $S=\sum_jx_j$, the first $n-1$ row equations give $x_i=S$, while the last gives $S=0$. Hence every $x_i=0$, so $A$ is nonsingular and has exactly $n^2-n+1$ ones. Therefore
$$
\boxed{c_n=n^2-n+1}.
$$
Back to article page
