How to generate all the 3 by 3 matrices ?

I have to generate the matrices based on the following conditions

A=[a b c;d e f;g h i]

How can I generate all the possible 3 by 3 matrices having real entries with the following conditions

2a is less than and equal to both (b+d) and (c+g)

a is less than and equal to both (e) and (i)

(a+d) is less than and equal to (f+g)

(a+g) is less than and equal to (h+d)

Thanks

[Torsten]

Any constraints on the parameters a,b,c,d,e,f,g,h,i (e.g. integers within a certain range) ? Otherwise, there will be infinitly many such matrices, I guess.

[Ammy]

No there is no restriction on the integers.

[Ammy]

But for simplicity you can restrict it from 1 to 20 then is there way to generate it

Answer 1

[Birdman]

One approach:

while true
    A=randi([1 20],3,3);
    if (2*A(1,1)<=(A(1,2)+A(2,1))) && (A(1,1)<=A(2,2) && A(1,1)<=A(3,3)) && (A(1,1)+A(2,1)<=A(2,3)+A(3,1)) && (A(1,1)+A(3,1)<=(A(3,2)+A(2,1)))
        break;
    end
end

[Ammy]

It will generate only one matrix , how can I generate all possible matrices , with the above conditions.

[Birdman]

I guess there are infinitely many matrices satisfying this conditions. Following may give you an idea:

i=1;
while true
    A(:,:,i)=randi([1 20],3,3);
    if (2*A(1,1,i)<=(A(1,2,i)+A(2,1,i))) && (A(1,1,i)<=A(2,2,i) && A(1,1,i)<=A(3,3,i)) && (A(1,1,i)+A(2,1,i)<=A(2,3,i)+A(3,1,i)) && (A(1,1,i)+A(3,1,i)<=(A(3,2,i)+A(2,1,i)))
        i=i+1;
    end
    if i==1001;break;end
end

[Ammy]

Thank you very much.

[John D'Errico]

The solution birdman suggests (i.e., a random rejection scheme) is probably the only feasible solution.

Be careful, in that this solution does not preallocate A. That will significantly slow down the code, because it builds the array A in an incremental fashion. And since the size of A is known in advance, not preallocating A is silly.

Also note that for 1000 such matrices generated, there will be a rejection rate of roughly 31 out of every 32 matrices generated at random. That is probably tolerable, for a set as small as 1000 in total.

Finally, note that the random scheme described does not exclude the possibility that the same matrix may be generated twice in that set. Testing for that possibility will increase the run time of the code. And while it may seem improbable that replicates will occur, anyone who has ever tripped over the birthday paradox will recognize that this can happen. A very rough back of the envelope computation suggests this will still be rare for a sample size as large as only 1000, but replicates can arise.

Answer 2

[John D'Errico]

Essentially, it will be practically impossible to list all solutions.

If the set of matrices allows real numbers for the elements, then of course there will be infinitely many solutions. You cannot generate an infinite set. Well, you can try, but it will take a long time to count to infinity.

A later comment asks: what if a-i are limited to the integers, 1:20.

The simple solution is simply to generate all possible sets of numbers of that form. So if each of a-i are an integer from 1:20, then there are 20^9 possible matrices. So, 512 billion possible matrices. That is a BIG number.

You then list 6 distinct linear constraints:

1. 2a is less than and equal to (b+d)

2. 2a is less than and equal to (c+g)

3. a is less than and equal to (e)

4. a is less than and equal to (i)

5. (a+d) is less than and equal to (f+g)

6. (a+g) is less than and equal to (h+d)

I'll be charitable, and suggest that at best, these constraints reduce the set of possible solutions by 50% for each constraint. Since there are 6 of them, that reduces the candidate set of matrices by a factor of 2^6=32.

So there will potentially be (roughly) 16 billion possible matrices, that satisfy all of the constraints.

You want to create all 16 billion of them. Each matrix is a 3x3 matrix. In the form of a double, that will take up 9*8=72 bytes to store. So the entires set of roughly 16 billion matrices will require something like 1152 gigabytes of memory to store. Yes, I said roughly 1.1 terabytes.

Do you have 1.1 terabytes of RAM on your computer? I don't. I know of very few people who do have that available at this time. So even if you could compute that entire set of matrices in an efficient way, you can't store them in memory.

Your computer is not infinitely large. It does not have infinitely much memory.

Next, how might you try to do this, even if you had sufficient memory? Realistically, the only solution to describe such a subset is by computing the entire set of matrices, all 20^9 of them. Then discard those that fail the requirements.

But that requires you to create 20^9 matrices, each of which requires 72 bytes of RAM to store.

20^9*72
ans =
          36864000000000

Now we are talking 36 terabytes of RAM to generate them all.

Your computer will melt its plastic case down due to the heat generated by that much memory. The lights will dim in your city trying to power the fans that will cool that much memory. (Ok, I'm exaggerating here. But the point is, that is a LOT of RAM.)

Answer 3

[Torsten]

1. Generate all possible arrangements of length 8 of the numbers 1,...,20 with repetition (e.g.using https://de.mathworks.com/matlabcentral/fileexchange/7147-permn-v--n--k-)

This gives you (b,c,d,e,f,g,h,i).

2. For each of these arrangements, calculate m = min((b+d)/2, (c+g)/2, e, i, f+g-d, h+d-g).

3. Delete all arrangements for which m is smaller than 1.

4. For the remaining arrangements, choose all a in the range [1:m] and take (1,b,c,d,e,f,g,h,i), (2,b,c,e,f,g,h,i),...,(m,b,c,d,e,f,g,h,i) as the feasible arrangements corresponding to (b,c,d,e,f,g,h,i).

Best wishes

Torsten.