Given a matrix $A \in \{0,1\}^{n \times n}$, let $diag(A)$ be the set of vectors $D \in \{0,1\}^n$ that are the diagonal of one of the $n!$ matrices obtained from $A$ via row permutations.
What is the maximum size of $|diag(A)|$ over all matrices $A \in \{0,1\}^{n \times n}$?
The answer is $2^n -n$.
Let $I$ be the $n \times n$ identity matrix and let $D$ be a diagonal whose non-zero entries are indexed by $S$. Further suppose that $D$ does not have exactly one zero entry. Let $\pi$ be a permutation of the rows of $I$ whose fixed points are exactly $S$. Then the diagonal of $\pi(I)$ is $D$, and there are $2^n-n$ such diagonals.
We finish by showing that $2^n-n$ is the best one can do.
An $n \times n$ bipartite graph is a bipartite graph with bipartition $([n]_r, [n]_c)$, where $[n]_r$ and $[n]_c$ are both copies of $[n]$. Let $G$ be an $n \times n$ bipartite graph. Define $G'$ to be equivalent to $G$, if $G'$ can be obtained from $G$ by complementing the neighbourhoods of some vertices in $[n_r]$. Note that the equivalence class of $G$, denoted $[G]$, has size $2^n$.
It is easy to check that the following lemma proves the tightness of the bound.
Lemma. For any $n \times n$ bipartite graph $G$, at most $2^n-n$ members of $[G]$ have a perfect matching.
Proof. For each $i \in [n]_c$ there is a graph $G^i \in [G]$ such that $i \in [n_c]$ has degree 0 in $G^i$. Just pick the vertices in $[n]_r$ that are adjacent to $i$ in $G$ and complement their neighbourhoods. If all $G^i$ are distinct, then the lemma clearly follows. Otherwise, $G^i=G^j$ for some $i \neq j$. Thus, both $i$ and $j$ have degree 0 in $G^i$. But now, the $n$ graphs obtained from $G^i$ by performing a single complementation each do not have a perfect matching.
