[seqfan] Re: Non-isomorphic semi-magic squares

[Brendan McKay]

The description of A321724 says "row sums and columns all equal to d",
but the example for a(10,5) shows row sums 2.

Should it perhaps be "d rows and d columns"?   Or should it say "a(10,2)"?

Similarly with A321721?

I can find counts of inequivalent semi-magic squares to a decent size (for example
the number of 8x8 nonnegative integer matrices with all row and column sums 4
is 1012456 in one minute, but that number does not appear in OEIS except in
one irrelevant(?) sequence.

About T(n,n/2) below: think of it as a bipartite graph consisting only of even cycles,
including cycles of length 2.  Equivalence is the same as graph isomorphism with
the colour-classes fixed, so all that matters is the number of cycles of each length.

The case T(n,n/3) is much harder and I'd be quite surprised if there is a simple
formula.  It starts 1, 2, 5, 12, 31 and is A232215<https://oeis.org/A232215>.

Brendan.

On 20/2/20 9:02 am, Elijah Beregovsky wrote:

Hello, SeqFans!
I’ve been trying to find new terms for A321724 and A321721.
A321724(n,d) is “the number of nonnegative integer square matrices up to row and column permutations with sum of elements equal to n and no zero rows or columns, with row sums and column sums all equal to d.”
Obviously, T(n,1)=T(n,n)=1. That corresponds to [n] and n*n identity matrix.
I found also the values for T(n,2)=floor(n/4+1) and T(n,n/2)= A000041(n/2) (the number of partitions). The former corresponds to matrices of the form:
[k   n-k]
[n-k   k].
The latter is trickier, but only a little bit. Let’s call a semi-magic square impartible if it doesn’t contain a square region that is also semi-magic with the same row sum (or is isomorphic to an impartible square, but for the purposes of the task we treat isomorphic squares as one square). For instance, this matrix is impartible:
[1 1 0]
[1 0 1]
[0 1 1],
and this one is not:
[2 0 0]
[0 1 1]
[0 1 1].
There is only one impartible semi-magic square with side length m>2 and row sum 2. Let's construct it.
1) It can't contain twos, otherwise it would contain a semi-magic square [2].
2) Without loss of generality we can put a 1 in the top-left corner and two 1 next to it:
[1 1 ...]
[1 ...   ]
...
3) We can't put a 1 in the 2nd cell on a diagonal because in that case we would have a semi-magic subsquare
[1 1]
[1 1],
so in that cell goes a 0 and without loss of generality we can put two 1 next to it:
[1 1 0...]
[1 0 1...]
[0 1 ...  ]
...
4) The third clause repeats until we reach the bottom-right corner. Then we just put a 1 there. That is really an impartible semi-magic square of order m and, as there weren't any "bifurcations" in the construction, it is indeed the only one (example for m=2):
[1 1 0 0]
[1 0 1 0]
[0 1 0 1]
[0 0 1 1].
Every semi-magic square of order m with row sum 2 corresponds to a partition of m, as it can be split into several impartible squares of orders summing up to m and there’s only one impartible square for every order. For example:
[2 0 0 0 0]
[0 1 1 0 0]
[0 1 1 0 0]
[0 0 0 1 1]
[0 0 0 1 1]
can be split into
     [2],    [1 1]     [1 1]
               [1 1],    [1 1],
(sz: 1         2          2)
so corresponds to the partition {1,2,2}.

My question is: can this construction be generalized to squares with row sum 3 to find the formula for T(n, n/3)?

I’ve thought about it and found this (probably) useful fact. There are three “basic” patterns, and all semi-magic squares with row sum 3 appear to be made by combining them in some way.
Those are:
[1 1 1]   [2 1 0]   [2 1 0]
[1 1 1]   [1  1 1]   [1 0 2]
[1 1 1],  [0 1 2],  [0 2 1].
You apparently can make any impartible square just by sticking the “moieties” of them back to back. Like that:
[2 1 0 0 0]
[1 1  1 0 0]
[0 1  1 1 0]
[0 0 1 0 2]
[0 0 0 2 1]
(That is a hybrid of the second and the third patterns.)
With that there are two problems, though.
1) The first pattern is too bulky and doesn’t stick well to others, so there are more of the hybrid squares than expected:
[1 1 1 0 0]  [1 1 1 0 0]
[1 1 1 0 0]  [1 1 0 1 0]
[1 0 0 1 1]  [1 0 1 0 1]
[0 1 0 1 1]  [0 1 0 1 1]
[0 0 1 1 1]  [0 0 1 1 1]
Both of these are combinations of two instances of first pattern.
2) The third pattern is asymmetrical, so new squares can sometimes be produced by flipping it:
[2 1 0 0 0]  [1 2 0 0 0]
[1 0 2 0 0]  [2 0 1 0 0]
[0 2 0 1 0]  [0 1  1 1 0]
[0 0 1 0 2]  [0 0 1 0 2]
[0 0 0 2 1]  [0 0 0 2 1].

I will be grateful for any help.

Best regards,
Elijah

--
Seqfan Mailing list - http://list.seqfan.eu/