Producing a set of matrices in MAGMA

Question

As part of my work I need to define the set of all $n\times n$ matrices with entries in $\{0,1,\ldots,n\}$ (considered as a subset of $\mathbb{Z}$), such that each row and column of the matrix sums to $n$.

Is there an easy way to do this in MAGMA?

Answer 1

Here is one idea towards a solution. It only works (practically) until $n=3$ on my computer, because with $n=4$ it has to sift through $5^{16}$ different matrices. Perhaps someone can refine my method, or introduce one that is not so crude, ie, one that uses a little more theory than I have used. Essentially, all I've done is defined a function NSumMatrix($m$) which returns true if $m$ has the desired property.

First, define a RowSum($A$,$i$) function as follows:

RowSum:=function(A,i)

return &+[A[i,j]:j in [1..Nrows(A)]];

end function;

Define a function similarly for the column sum. Then, define the following aforementioned function:

NSumMatrix:=function(m)

n:=Nrows(m);

a:=1;

b:=1;

z:=ChangeRing(m,IntegerRing());

while a le n and RowSum(z,a) eq n do

a:=a+1;

end while;

if a le n then

return false;

end if;

while b le n and ColumnSum(z,b) eq n do

b:=b+1;

end while;

if b le n then

return false;

else

return true;

end if;

end function;

Now, define a matrix algebra:

M:=MatrixAlgebra(Integers(n+1),n);

And finally, construct the desired set using the function:

S:={x:x in M|NSumMatrix(x)};

For $n=3$, if you print $S$, you'll find all $55$ matrices whose rows and column sums are all $3$.