Return to Answer

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.

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.

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

Edit. 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'$. 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.

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.

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

Edit. 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' \in [G]$ such that $i \in [n_c]$ has degree 0 in $G'$. Just pick the vertices in $[n]_r$ that are adjacent to $i$ in $G$ and complement their neighbourhoods. Clearly $G$' does not have a perfect matching, so the lemma follows.

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

Edit. 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'$. 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.