Maximum number of distinct diagonals generated by permutations 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}$?

 A: 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.    
