1

Call a $n \times n$-matrix $A=(a_{i,j})$ with entries only 0 or 1 "cool" in case it has the following properties:

-We have $a_{i,j}=0$ in case $i>j$.

-It has only 1 on the diagonal

-It has only 1 in the first row.

(call it "supercool" if additional it has only 1 on the last column.)

Question: Is there a quick/good way to obtain all cool (an supercool) matrices with GAP?

I know how to do it when filtering out from all 0-1-matrices but that takes very long when $n$ is large. So I am hoping for a very fast way to get those matrices also for large $n$.

Mare
  • 2,332
  • For large $n$ there will be a large number of matrices! Consider the entries with $i<j$. There are at least $n-1$ possibilities for the first row, and 2 for each of the other $\frac{1}{2}(n-2)(n-1)$ entries. So more than $2^{(n-2)(n-1)/2}$ in all. Do you really want a massive list, or do you just want to know how many there are? – almagest Sep 29 '19 at 13:09
  • @almagest No, I want them as a list in GAP. Even when the list is possible only for values for n till n=10 roughly. – Mare Sep 29 '19 at 13:14
  • 1
    At $n=10$ there will still be more than 600 billion of them, each will a minimum of 8 bytes so at least 5TB of memory. That won't fit in RAM on an ordinary desktop and needs a fairly large disk. Why do you need a list? Can't you just iterate through them on the fly if you need to do something with them? – almagest Sep 29 '19 at 13:25
  • @almagest Oh, I guess I have to be satisfied with something like n<=8 then. I need it for some experiments. Even till n=8 it will be good enough to have a guess for something Im interested in. – Mare Sep 29 '19 at 13:28
  • 1
    If you want to run experiments, how about writing a function that constructs a "Random" matrix with your property. (Or write iterated for loops that iterate through your objects without writing all down). – ahulpke Sep 29 '19 at 15:47
  • @ahulpke How to find such a random matrix using GAP? I have btw the list up to n=7 so a program taht lists all for n=8 would also be good since my slow method doesnt seem to end. – Mare Sep 29 '19 at 16:04
  • @Mare You would write a function that gets a parameter $n$ and returns an $n\times n$ matrix in which you set your entries as required for $i\ge j$, then set the other entries by random (with the exception of first row/column, where you select the position of the nonzero entry). – ahulpke Sep 29 '19 at 16:45

0 Answers0