Let $M$ be a Boolean Matrix, i.e. $M \in \{0,1\}^{n\times m}$. I want to figure out a tight lower bound for rank of the matrix $M$. Rank of a matrix is defined here(wikipedia) for your reference. In this particular question, I also have the following constraints that no two rows are same.
There are many algorithms to find rank of the matrix. But I want a bound just by looking at these properties of the given matrix.
Suppose there are $n$ rows and $m$ columns, and no two rows are the same. If the rank is $r$, there are $r$ columns whose entries determine those of the other columns. Thus we must have $n \le 2^r$, or $r \ge \lceil \log_2(n) \rceil$.
This bound is tight, in that as long as $m \ge \lceil \log_2(n) \rceil$ we can find an $n \times m$ matrix with rank $\lceil \log_2(n) \rceil$ and all rows distinct. Namely, if $k = \lceil \log_2(n)\rceil$, there is a $2^k \times k$ matrix whose rows are all members of $\{0,1\}^k$. Take a subset of $n$ of these rows that includes all possible $(k-1)$-tuples in the first $k-1$ columns with $0$ in the $k$'th, and another $n - 2^{k-1}$ distinct rows having $1$ in the $k$'th column. All other columns are all $0$.