Let $A$ be a square matrix of size $n \times n$ whose entries are all $0$ or $1$, and its diagonal entries are all $1$.
Denote the total number of $1$s in the matrix by $|A|$. So $|A|$ is the sum of all entries.
I want to prove the following lower bound on the rank of $A$ over the reals.
$$\mathrm {rank}_\mathbb R(A)\cdot |A|\geq n^2.$$
Thoughts.
If $A$ is the identity matrix or the all-ones matrix then we get equality.
An equivalent interpretation: start with the identity matrix and then try to add more $1$s efficiently to reduce the rank. The claim is that to reduce the rank by $k$ we must add at least
$$\frac {n^2}{n-k}-n = \frac{kn}{n-k}$$ new $1$s. For small $k$ this can be verified manually.
The claim is that the geomtric mean of the rank and the sum is at least $n$. If we replace the geometric mean by arithmetic mean, meaning $\mathrm {rank}_\mathbb R(A) + |A|\geq 2n$, then the claim is immediate from the preceding interpretation, because adding $1$ somewhere can reduce the rank by at most $1$.
Best Answer
Theorem(Ky Fan-Hoffman, 1953)
Let $A=(a_{ij}) \in M_n (\mathbb C)$ be a matrix with rank $r$. Then the following two inequalities hold, where $0/0$ is interpreted as $0$.
$$(1) ~~\sum_{i=1}^n \frac{ |a_{ii}|^2 }{ \sum_{j=1}^n |a_{ij}|^2 } \leq r , ~~~~~~~~(2)~~\sum_{i=1}^n \frac{ |a_{ii}| }{ \sum_{j=1}^n |a_{ij}| } \leq r $$
proof. (taken from original paper of Ky Fan and Hoffman)
(1) Let $A_i$ denote the $i$-th row vector of $A$ and $e_i$ the $i$-th unit vector. The left-hand side of the inequality and the rank of $A$ remain unchanged if we multiply any row of $A$ by nonzero scalar. Hence we may assume that for each $i$, $\Vert A_i \rVert^2 = \sum_{j=1} |a_{ij}|^2 \in \{0, 1\}$. Under this assumption, it suffices to show that $\sum_{i=1}^n|(A_i, e_i)|^2\leq r$. Here $(~,~)$ denotes the Hermitian inner product. As $A$ is of rank $r,$ we can find orthonormal basis $x_1, \dots, x_n$ of $\mathbb C^n$ such that $(A_i, x_j)=0$ for all $1 \leq i \leq n$ and $r < j \leq n$. For each $i$, we have \begin{align} (A_i, e_i) &= (A_i, \sum_{j=1}^n (e_i, x_j)x_j) \\& = \sum_{j=1}^n (A_i, x_j) \overline{(e_i, x_j)} \\&=\sum_{j=1}^r (A_i, x_j) \overline{(e_i, x_j)} \\ & \leq \left( \sum_{j=1}^r |(A_i, x_j)|^2 \right) \left( \sum_{j=1}^r |(e_i, x_j)|^2 \right)\end{align} by the Cauchy-Schwarz inequality. Moreover, $\sum_{j=1}^r |(A_i, x_j)|^2= \Vert A_i \rVert^2 \in \{ 0, 1\}$, so that $$(A_i, e_i) \leq \left( \sum_{j=1}^r |(A_i, x_j)|^2 \right) \left( \sum_{j=1}^r |(e_i, x_j)|^2 \right) \leq \sum_{j=1}^r |(e_i, x_j)|^2$$ Thus $$\sum_{i=1}^n |(A_i, e_i)|^2 \leq \sum_{i=1}^n \sum_{j=1}^r |(e_i, x_j)|^2=\sum_{j=1}^r \sum_{i=1}^n |(e_i, x_j)|^2=\sum_{j=1}^r \lVert x_j \rVert ^2=r$$ (2) As before, we may assume $0 \leq a_{ii} \in \mathbb R$ and $\sum_{j=1}^n |a_{ij}| \in \{0, 1\}$ holds for each $1\leq i \leq n$. It suffices to prove that $\sum_{i=1}^{n} a_{ii} \leq r $. By the Gershgorin circle theorem, all eigenvalues of $A$ have modulus $\leq 1$. On the other hand, $\operatorname{tr}(A)=\sum_{i=1}^{n} a_{ii} $ is the sum of all eigenvalues of $A$. Combined with the triangle inequality, we have $\sum_{i=1}^{n} a_{ii} \leq k$, where $k$ is the number of nonzero eigenvalues of $A$. Now let $T=U^{-1} AU$ be a upper-triangular matrix. Then the number of nonzero eigenvalues of $T$ equals to $k$, and thus $k \leq \operatorname{rank}(T) = \operatorname{rank}(A)=r$. $~\blacksquare$
Now let $A=(a_{ij})$ be a square $(0, 1)$-matrix of size $n \times n$ with all diagonal entries $1$. Put $p_i = \sum_{j=1}^{n} a_{ij}>0$. Then (2) in the above theorem can be rephrased as $$\operatorname{rank}(A) \geq \sum_{i=1}^{n} \frac{1}{p_i}$$ By the Cauchy-Schwarz inequality, $$(p_1 + \dots + p_n) \left( \frac{1}{p_1} + \dots + \frac{1}{p_n} \right) \geq n^2 $$ Now $$\operatorname{rank}(A) \geq \sum_{i=1}^{n} \frac{1}{p_i} \geq \frac{n^2}{p_1 + \dots + p_n}=\frac{n^2}{|A|} $$ as desired. $~\blacksquare$
Note that for a matrix $A$ with real entries its rank over $\mathbb C$ is same as over $\mathbb R$, so there is no ambiguity in the notation $\operatorname{rank}$.
As @Chris H wrote in the comment, this could be viewed as a special case of more general inequality $$ \operatorname{rank}(A) \operatorname{tr}(AA^t) \geq \operatorname{tr}(A)^2$$ In fact, this is true for all $A=(a_{ij}) \in M_n(\mathbb R)$. To see this, put $s_i = \sum_{j=1}^{n} a_{ij}^2 $ for $1 \leq i \leq n$. Assume $A \neq 0$ and let $1\leq i_1 < \dots <i_m \leq n$ be all $i$'s for which $s_i$ is nonzero. Such $i$ exists unless $A$ is the zero matrix. For brevity put $D_i = a_{ii}^2$ and $d_i = a_{ii}$. By Ky Fan-Hoffman we have $$\operatorname{rank}(A) \geq \frac{D_{i_1}}{s_{i_1}} + \dots + \frac{D_{i_m}}{s_{i_m}} $$
Again, $$(s_{i_1} + \dots + s_{i_m} )\left( \frac{D_{i_1}}{s_{i_1}} + \dots + \frac{D_{i_m}}{s_{i_m}} \right) \geq (d_{i_1} + \dots + d_{i_m} )^2 $$ by Cauchy-Schwarz. Now observe that $s_i = 0 $ implies $d_i = 0$. Thus $$\operatorname{rank}(A) \geq \frac{ (d_{i_1} + \dots + d_{i_m} )^2 } {s_{i_1} + \dots + s_{i_m} } = \frac{ \operatorname{tr}(A)^2 }{ \operatorname{tr}(AA^t) }$$ Finally, the inequality is true when $A=0$. $~\blacksquare$
Complex version of the above statement might be the following: if $A=(a_{ij}) \in M_n (\mathbb C)$ is a matrix with rank $r$, then $$\operatorname{rank}(A) \operatorname{tr}(AA^*) \geq |\operatorname{tr}(A)|^2$$ where $A^*$ is the complex conjugate transpose of $A$. As above, put $s_i = \sum_{j=1}^{n} |a_{ij}|^2 $ for $1 \leq i \leq n$. Assume $A \neq 0$ and let $1\leq i_1 < \dots <i_m \leq n$ be all $i$'s for which $s_i$ is nonzero. Let $D_i = |a_{ii}|^2$ and $d_i = |a_{ii}|$. By Ky Fan-Hoffman and Cauchy-Schwarz, we have $$\operatorname{rank}(A) \geq \frac{ (d_{i_1} + \dots + d_{i_m} )^2 } {s_{i_1} + \dots + s_{i_m} } = \frac{(d_1 + \dots + d_n)^2 }{s_1 + \dots + s_n} \geq \frac{ |\operatorname{tr}(A)|^2}{\operatorname{tr}(AA^*)}$$
as wished.