Let $A$ be an $m \times 2^n$ binary (i.e. with entries from $\{0,1\}$) matrix where $m \gg n$, such that all columns of $A$ are distinct $m$-bit bitwords. Suppose further that by removing any row of $A$ we obtain a $(m-1)\times 2^n$ matrix whose columns are no longer unique in the above sense.
For any such matrix one clearly has the upper bound $m < 2^{n}$. What is the best possible upper bound on $m$ in terms of $n$?
Example for $n = 3, m = 5$:
$$\begin{bmatrix}1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}$$
Edit: This is a very closely related question.
If $A=[c_1,...,c_n]$ where $c_i$ is the $i^{th}$ column of $A$, Let $E_k = \{(i,j): c_i + c_j = e_k \}$. So we have $|E_k| \geq 1$, $\forall k$ since removing $k^{th}$ row will make some two columns same. Further $i$ appears only once in $E_k$, since otherwise $c_i + c_j + c_i + c_l = e_k + e_k$ which implies $c_j = c_l$ contradicting distinctness of columns. If there is a column index $i$ which is not present in any tuple in any set $E_k$ then we can remove that column and tighten the upper bound. Clearly rank$(A) = m$, since we can linearly combine the columns and generate $\{e_1,...,e_{m}\}$. Hence $m > 2^n$ is impossible since $rank(A) = m \leq 2^n$. $m = 2^n-1$ can be attained by matrix, $A=[0,e_1,...,e_m]$.