# Using Mathematica to solve matrix equations

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.

• Are you interested in an answer in terms of general n or a way to compute the number for a given n? – Michael E2 May 31 '17 at 13:06
• @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 :) – user21766 May 31 '17 at 13:09

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}]
]

• 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) – user21766 May 31 '17 at 14:09
• 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? – KennyColnago May 31 '17 at 15:02
• 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. – user21766 May 31 '17 at 15:10

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:

• 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 – user21766 May 31 '17 at 20:40
• It might work. I have to try it at first. – UnchartedWorks May 31 '17 at 20:51
• 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. – UnchartedWorks Jun 1 '17 at 8:07