Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

1 Answer 1

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|improve this answer
2  
This seems to have a slight problem with the case of the configurations with exactly one zero. –  damiano Aug 9 '10 at 12:20
1  
Not with $n=3$ you can't :-) –  Robin Chapman Aug 9 '10 at 12:23
2  
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
2  
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
1  
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
show 1 more comment

Your Answer

 
discard

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.