2
$\begingroup$

A magic square of size $n$ and sum $k$ is a $n\times n$ matrix with non-negative integer elements, whose rows and columns all sum to $k$. A permutation matrix is a magic square of sum $1$. Every magic square can be written as a sum of permutation matrices, in general not uniquely.

What is known about the problem of finding the number of ways a magic square can be written as a sum of permutation matrices? Are there available upper bounds, recurrence relations, algorithms?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Not really an answer to your question, but this is the same as studying integer points in (dilations of) the Birkhoff polytope. $\endgroup$
    – Sam Hopkins
    Commented Apr 22, 2021 at 19:58
  • 3
    $\begingroup$ @SamHopkins: the integer points correspond to the magic squares themselves. I don't see a useful connection with the number of ways to write a particular magic square as a sum of permutation matrices. $\endgroup$
    – Richard Stanley
    Commented Apr 22, 2021 at 20:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .