# Question:How many matrices of a given type are singular?

## Question:How many matrices of a given type are singular?

Maple

Hi,

Let S(N) the set of all N by N matrices defined this way:

• each element of a matrix M in S(N) is an integer number between 1 and included N^2
• all the elements of M are different

For instance the matrix M = < <1, 2>|<3, 4> > belongs to S(2).

I'm interesting in finding the number of singular matrices of S(N), and more reasonnably of S(N <=3).
It's easy to verify that no matrix in S(2) is singular.
For S(3) now: as S(3) contains only 9! = 362880 elements a brute force approach can still be used. It showed that 2736 matrices were singular (about 0.75%).
But I wonderded if a more elegant approach could be used?
In the attached file I wrote all the relations elements of S(2) (and next S(3)) must verify and solved these equations for integer solutions (I only accounted for singular matrices . The case S(2) is tractable, but not S(3) (at least on my computer).

So my question: do you have any idea of some method to tackle this problem, or are you aware of any theoritical results about this issue?

PS: of course a statistical approach in which elements of S(N) would be generated using random permutations of [\$1..N^2] is still possible to get a crude approximation of the number of singular matrices, but I'm not interested in this kind of approach.

 > restart:
 > alias(det = LinearAlgebra[Determinant])
 (1)

Brute Force

 > S    := 0: p    := 3: PERM := combinat:-permute(p^2): for perm in PERM do   M := Matrix(p, p, perm):   if det(M)=0 then S := S+1; end if: end do: S; evalf(S/9!);
 (2)

A non systematic approach

Case of S(2)

 > M := Matrix(2, 2, symbol=m): iM := {indices(M)}: # set of all relations that define the elements of S(2) rels :=   {     det(M) = 0,     # each term is equal to an integer between 1 and 4 included     mul((M[1, 1]-k), k=1..4)=0,     mul((M[1, 2]-k), k=1..4)=0,     mul((M[2, 1]-k), k=1..4)=0,     mul((M[2, 2]-k), k=1..4)=0,     # the sum of all the terms is equal to 10     # M[1, 1]+M[1, 2]+M[2, 1]+M[2, 2]=10,     # all the terms are different     seq( mul(seq((M[op(im)]-M[op(ij)]), ij in iM minus {im})) <> 0, im in iM)   }
 (3)
 > isolve(rels);  # no solution founds

A non systematic approach

Case of S(3)

 > M := Matrix(3, 3, symbol=m): iM := {indices(M)}: rels :=   {     det(M) = 0,     # each term is equal to an integer between 1 and 9 included     mul((M[1, 1]-k), k=1..9)=0,     mul((M[1, 2]-k), k=1..9)=0,     mul((M[1, 3]-k), k=1..9)=0,     mul((M[2, 1]-k), k=1..9)=0,     mul((M[2, 2]-k), k=1..9)=0,     mul((M[2, 3]-k), k=1..9)=0,     mul((M[3, 1]-k), k=1..9)=0,     mul((M[3, 2]-k), k=1..9)=0,     mul((M[3, 3]-k), k=1..9)=0,     # the sum of all the terms is equal to 10*9/2 = 45     M[1, 1]+M[1, 2]+M[1, 3]+M[2, 1]+M[2, 2]+M[2, 3]+M[3, 1]+M[3, 2]+M[3, 3]=45,     # all the terms are different     seq( mul(seq((M[op(im)]-M[op(ij)]), ij in iM minus {im})) <> 0, im in iM)   }: numelems(rels);
 (4)
 > run_this := false: if run_this then   isolve(rels);  # requires a huge amount of memory and computational time end if;
 >