MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.