2
$\begingroup$

I am finding references for the following problem:

We call a $n\times n$ 0-1 matrix permutation if there are exactly one $1$ in each row/column. Suppose $A$ is a 0-1 matrix of size $n\times n$ in which there are exactly $n$ $1$s.

Conjecture. There exist permutations $P_i,Q_i$ such that $\sum_{i=1}^n P_iAQ_i = J$, where $J$ denotes the "all-$1$" matrix.

I am sure that we have a famous similar conjecture on non-bipartite graphs, i.e., $K_n$, in which we only consider the case that monochromatic parts are trees. But I just cannot recall its name...

Update. (Mar 21, 2019) The name I forgot is Ringel's Conjecture.

Improve this question
$\endgroup$
2
  • $\begingroup$ For n=6 and A having the six ones be in the upper left corner (I+j < 3), I would like to see the six arrangements of A adding up to J. Gerhard "Not Sure If It's Possible" Paseman, 2019.03.20. $\endgroup$
    – Gerhard Paseman
    Commented Mar 21, 2019 at 4:51
  • $\begingroup$ @GerhardPaseman (a a b) (a c c) (b c b) (a a a) (b b b) (c c c) (Write it as a 3x6 matrix and naturally construct a 6x6 one) $\endgroup$
    – Lwins
    Commented Mar 21, 2019 at 5:53

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .