Advanced Search

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

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

mmcdara 6740 Maple
matrix singular linear-algebra
July 22 2020
0

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.

Thanks in advance


 

> 

restart:
> 

alias(det = LinearAlgebra[Determinant])

det

 (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!);

2736

  

0.7539682540e-2

 (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)
  }

{(m[1, 1]-1)*(m[1, 1]-2)*(m[1, 1]-3)*(m[1, 1]-4) = 0, (m[1, 2]-1)*(m[1, 2]-2)*(m[1, 2]-3)*(m[1, 2]-4) = 0, (m[2, 1]-1)*(m[2, 1]-2)*(m[2, 1]-3)*(m[2, 1]-4) = 0, (m[2, 2]-1)*(m[2, 2]-2)*(m[2, 2]-3)*(m[2, 2]-4) = 0, m[1, 1]*m[2, 2]-m[1, 2]*m[2, 1] = 0, (m[1, 1]-m[1, 2])*(m[1, 1]-m[2, 1])*(m[1, 1]-m[2, 2]) <> 0, (m[1, 2]-m[1, 1])*(m[1, 2]-m[2, 1])*(m[1, 2]-m[2, 2]) <> 0, (m[2, 1]-m[1, 1])*(m[2, 1]-m[1, 2])*(m[2, 1]-m[2, 2]) <> 0, (m[2, 2]-m[1, 1])*(m[2, 2]-m[1, 2])*(m[2, 2]-m[2, 1]) <> 0}

 (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);

20

 (4)
> 

run_this := false:
if run_this then
  isolve(rels);  # requires a huge amount of memory and computational time
end if;
> 

 


 

Download HowManyMatricesAreSingular.mw
Please Wait...