1
$\begingroup$

I am curious as to whether it is possible to use Mathematica for counting the number of square matrices $S$ (with non-negative integer entries) of size $n$x$n$ that satisfy: $\sum_{i,j=1}^n S_{ij}=n-1.$ Of course such problem can be solved analytically, but I was wondering whether Mathematica can be used to somehow assist in such counting problems. Look forward to any suggestions.

$\endgroup$
  • 1
    $\begingroup$ Are you interested in an answer in terms of general n or a way to compute the number for a given n? $\endgroup$ – Michael E2 May 31 '17 at 13:06
  • $\begingroup$ @MichaelE2 Thanks for pointing this out. I am interested in the general case of n, but without any loss of generality we can work with a fixed n. I m just trying to learn how to do such things in mathematica, very eager :) $\endgroup$ – user21766 May 31 '17 at 13:09
3
$\begingroup$

Use IntegerPartitions to decompose $n-1$ into $n^2$ non-negative integers. Then count the number of permutations of each such partition.

SpecialMatrixCount[n_] :=
   Block[{partitions = IntegerPartitions[n - 1, {n^2}, Range[0, n - 1]]},
         Sum[
             (n^2)!/Times @@ Factorial[Tally[p][[All, 2]]],
             {p, partitions}]
   ]
$\endgroup$
  • $\begingroup$ Hi, very neat suggestion. But this does not necessarily solve the matrix count problem right? (in this example it does) because not all partitions will correspond to a non-negative integer matrix, to clarify, for example I take $\sum_{i,j=1}^n i*S_{ij}=n-1.$ or do you think it should still work? (because possible in factoring out the i's, from the obtained partitions, the matrix elements will be left non-integer) $\endgroup$ – user21766 May 31 '17 at 14:09
  • $\begingroup$ Perhaps I don't understand your question. Why is the summation over $i$ and $j$ in your question different from the summation in your comment here? $\endgroup$ – KennyColnago May 31 '17 at 15:02
  • $\begingroup$ Because of the added prefactor $i,$ which forces the partitioned integers to be multiples of $i$ as otherwise the matrix would contain real entries. Whereas in the question, the summation is just over the matrix elements, so any found partition can be immediately mapped to a corresponding matrix. $\endgroup$ – user21766 May 31 '17 at 15:10
2
$\begingroup$

This problem can be solved using Frobenius Equation. gives a list of all solutions of the Frobenius equation. FrobeniusSolve

If anyone is interested in FrobeniusSolve, please check Carl Woll's answer. 147124

The sum of entries is n-1, and all of entries are non-negative integers. It means the possible values of entires are Range[0,n-1].

1 y1 + 2 u2 + 3 y3 + 4 y4 + ... + (n-1) y(n-1) == n - 1

It is exactly what Frobenius equation is for.

We can use FrobeniusSolve[Range[n - 1], n - 1] to get all possible {y1,y2,y3,y4,...,y(n-1)}

For instance,

FrobeniusSolve[Range[3-1],3-1]

{{0, 1}, {2, 0}}

{0,1}

{0,1} ==> 1 * 0 + 2 * 1 == 3 - 1;

0 + 1 == 1 (number of positive integer entries)

3^2-1 == 8 (number of zero entries).

{8,0,1} (8 0-entries, 0 1-entries, 1 2-entires)

{0, 0, 0, 0, 0, 0, 0, 0, 2} (Expand it to a flattened matrix.)

{2,0}

{2,0} ==> 2 * 1 + 2 * 0 == 3 - 1;

2 + 0 == 2 (number of positive integer entries)

3^2-2 == 7 (number of zero entries).

{7,2,0} (7 0-entries, 2 1-entries, 0 2-entires)

{0, 0, 0, 0, 0, 0, 0, 1, 1} (Expand it to a flattened matrix.)

In:

frobeniusNumberToMatrix[xs_] := 
  xs // MapIndexed[ConstantArray[First@#2 - 1, #1] &] // Flatten
frobeniusNumber[n_] := 
  FrobeniusSolve[Range[n - 1], n - 1] // Map[Prepend[#, n^2 - Total[#]] &]
specialMatrixTemplate[n_] := 
  frobeniusNumber[n] // Map[frobeniusNumberToMatrix]
countSpecialMatrix[n_] := 
  specialMatrixTemplate[n] // Map[Permutations /* Union /* Length] // Total

(*Generate frobeniusNumber*)
frobeniusNumber[5]

(*Transform frobeniusNumber to Matrix Template*)
specialMatrixTemplate[5]

(*Count*)
countSpecialMatrix[5]

Out:

enter image description here

$\endgroup$
  • $\begingroup$ this is very interesting, had no idea about this. Would you please be so kind to add a tiny bit of explanations to what we re doing, I got a bit lost. Additionally, would this method still work if we changed the equation slightly, say to $\sum_{i,j=1}^n i*S_{ij} =n-1$? Thanks again $\endgroup$ – user21766 May 31 '17 at 20:40
  • $\begingroup$ It might work. I have to try it at first. $\endgroup$ – UnchartedWorks May 31 '17 at 20:51
  • $\begingroup$ I think there is no difference, because 0<= i *Sij < n and 0 <= Sij, if Sij is a non-negative integer and the sums are n-1. $\endgroup$ – UnchartedWorks Jun 1 '17 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy