Maximum number of distinct diagonals generated by permutations

Given an n by $n$ matrix with $0$'s and $1$'s only, consider the $n!$ different permutations generated by permuting the rows, what is the maximum number of different diagonals generated?

-
Is the question for a general upper bound or an upper bound if I know the matrix? –  Daniel Krenn Aug 9 '10 at 11:09
As in, you can choose any n by n 0-1 matrix you want to maximize this number. –  Kamil Aug 9 '10 at 12:12

If I am allowed to choose the matrix, it seems that I can generate all $2^n$ different diagonals.

Edit. Sorry, this approach only generates $2^n -n$ diagonals.

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 perumation 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.

Update. Here is a proof that $2^n-n$ is in fact 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.

-
This seems to have a slight problem with the case of the configurations with exactly one zero. –  damiano Aug 9 '10 at 12:20
Not with $n=3$ you can't :-) –  Robin Chapman Aug 9 '10 at 12:23
I suppose that I cannot generate diagonals that have exactly $n-1$ ones in this way, since if I fix $n-1$ rows, then I automatically fix the last one. But it seems that I can still get $2^n-n$ diagonals. –  Tony Huynh Aug 9 '10 at 12:24
A clever argument! One minor comment: I do not think that the current proof of the lemma deals with the case where more than one vertex in [n]_c have exactly the same set of neighbors, but it can be fixed easily. –  Tsuyoshi Ito Aug 10 '10 at 1:03
just a minor remark, the same without graphs: if two rows (say i-th and j-th) are equal to $r$, then each diagonal has at least two coincidences with $r$ (coincidence means coincidence of one of $n$ coordinate functionals). So, there are at least $n$ forbidden diagonals. If all rows are different, then all their complements are forbidden and we again have $n$ forbidden diagonals. –  Fedor Petrov Aug 10 '10 at 12:17