find number of different matrices( N) of all size s (no. of elements)?

Question

Note:

1) for s=n we have elements from 1,2,3...,n that are used to fill the matrix

2) two matrices are different if their no. of columns are different or if their no. of rows are different

I tried to find the solution like for s = 1 we can make only 1 matrix

then for s = 2 we have two matrices like [1 2] order 1x2 and another same along the column of order 2x1

for s = 3 , also two matrices [1 2 3] of order 1x3 and another along the column of order 3x1

but for s = 4 we have matrices 1x4,4x1 and 2x2

but I m not able to find any pattern in this for all values of s = 1,2,3,4,5,6...

Need help !

@PankajAnuragi still quite unclear, do you mean when you put input of s=2 you will get two row matrices/vectors each having value of [1 2]? or you actually only have one matrix/vector [1 2] when s=2? — Ian, Dec 16 '15 at 08:05
for s=2, we have elements 1 and 2 , having these two elements we wants to make matrices ,so there is two possibilities here , first a matrix [ 1 2] simple in 1 row and second [1 2] in column ( I'm not able to write the second matrix in two columns) so in total we can make 2 matrices for s= 2 — Pankaj Anuragi, Dec 16 '15 at 08:14
@PankajAnuragi I see, so what you want to find is the number of matrix you can make from the number of element you give, right? Or you want a program to do it for you for a given number? — Ian, Dec 16 '15 at 08:24
yes! I m trying to make a program for it which takes values of S and give the output (no. of different matrices can be form) — Pankaj Anuragi, Dec 16 '15 at 08:31
It is not very clear why you need to talk about 1,2,..,n as matrix elements. Do you consider (1,2) and (2,1) different? If not, why just not use (0,0) or whatever? — n. m. could be an AI, Dec 16 '15 at 08:56
@PankajAnuragi you can read the link given by JohnZwinck for the code to answer — Ian, Dec 16 '15 at 09:12
two matrices are different if their no. of columns are different or if their no. of rows are different ..., so NO (1,2) and (2,1) r not different and S >0 — Pankaj Anuragi, Dec 16 '15 at 09:45

score 1 · Answer 1 · edited May 23 '17 at 12:23

The examples you give, plus the next few, are:

1x1
1x2, 2x1
1x3, 3x1
1x4, 2x2, 4x1
1x5, 5x1
1x6, 2x3, 3x2, 6x1
1x7, 7x1
1x8, 2x4, 4x2, 8x1

So what's the pattern? The solutions are simply the integral divisors of s. Always 1 and s itself, of course, but also every integer which evenly divides s. You can find algorithms to find all the factors of an integer online already, such as here: Algorithm to find all the exact divisors of a given integer or here: Best way to find all factors of a given number in C#

Craig Estey · Answer 2 · 2015-12-16T09:41:04.953

You need the divisible factors [not necessarily prime ones] to get number pairs.

Here's a [working] perl script. I don't write "idiomatic" perl, but, rather more like a C programmer would, so in should be easy enough to treat this as pseudo-code to write a C program:

#!/usr/bin/perl
# mtxcombo -- generate matrix combinations

master(@ARGV);
exit(0);

# master -- master control
sub master
{
    my(@argv) = @_;
    my($lim);
    my($s);

    $lim = shift(@argv);
    $lim //= 1000;

    for ($s = 1;  $s <= $lim;  ++$s) {
        domtx($s);
    }
}

sub domtx
{
    my($s) = @_;
    my($i);
    my($d);

    printf("%d:",$s);

    add(1,$s);

    for ($i = 2;  $i < $s;  ++$i) {
        # up to sqrt
        last if (($i * $i) > $s);

        if (($s % $i) == 0) {
            $d = int($s / $i);
            add($d,$i);
            next;
        }
    }

    printf("\n");
}

sub add
{
    my($x,$y) = @_;

    printf(" %dx%d",$x,$y);

    if ($x != $y) {
        printf(" %dx%d",$y,$x);
    }
}

Here's the program output for <program> 100:

1: 1x1
2: 1x2 2x1
3: 1x3 3x1
4: 1x4 4x1 2x2
5: 1x5 5x1
6: 1x6 6x1 3x2 2x3
7: 1x7 7x1
8: 1x8 8x1 4x2 2x4
9: 1x9 9x1 3x3
10: 1x10 10x1 5x2 2x5
11: 1x11 11x1
12: 1x12 12x1 6x2 2x6 4x3 3x4
13: 1x13 13x1
14: 1x14 14x1 7x2 2x7
15: 1x15 15x1 5x3 3x5
16: 1x16 16x1 8x2 2x8 4x4
17: 1x17 17x1
18: 1x18 18x1 9x2 2x9 6x3 3x6
19: 1x19 19x1
20: 1x20 20x1 10x2 2x10 5x4 4x5
21: 1x21 21x1 7x3 3x7
22: 1x22 22x1 11x2 2x11
23: 1x23 23x1
24: 1x24 24x1 12x2 2x12 8x3 3x8 6x4 4x6
25: 1x25 25x1 5x5
26: 1x26 26x1 13x2 2x13
27: 1x27 27x1 9x3 3x9
28: 1x28 28x1 14x2 2x14 7x4 4x7
29: 1x29 29x1
30: 1x30 30x1 15x2 2x15 10x3 3x10 6x5 5x6
31: 1x31 31x1
32: 1x32 32x1 16x2 2x16 8x4 4x8
33: 1x33 33x1 11x3 3x11
34: 1x34 34x1 17x2 2x17
35: 1x35 35x1 7x5 5x7
36: 1x36 36x1 18x2 2x18 12x3 3x12 9x4 4x9 6x6
37: 1x37 37x1
38: 1x38 38x1 19x2 2x19
39: 1x39 39x1 13x3 3x13
40: 1x40 40x1 20x2 2x20 10x4 4x10 8x5 5x8
41: 1x41 41x1
42: 1x42 42x1 21x2 2x21 14x3 3x14 7x6 6x7
43: 1x43 43x1
44: 1x44 44x1 22x2 2x22 11x4 4x11
45: 1x45 45x1 15x3 3x15 9x5 5x9
46: 1x46 46x1 23x2 2x23
47: 1x47 47x1
48: 1x48 48x1 24x2 2x24 16x3 3x16 12x4 4x12 8x6 6x8
49: 1x49 49x1 7x7
50: 1x50 50x1 25x2 2x25 10x5 5x10
51: 1x51 51x1 17x3 3x17
52: 1x52 52x1 26x2 2x26 13x4 4x13
53: 1x53 53x1
54: 1x54 54x1 27x2 2x27 18x3 3x18 9x6 6x9
55: 1x55 55x1 11x5 5x11
56: 1x56 56x1 28x2 2x28 14x4 4x14 8x7 7x8
57: 1x57 57x1 19x3 3x19
58: 1x58 58x1 29x2 2x29
59: 1x59 59x1
60: 1x60 60x1 30x2 2x30 20x3 3x20 15x4 4x15 12x5 5x12 10x6 6x10
61: 1x61 61x1
62: 1x62 62x1 31x2 2x31
63: 1x63 63x1 21x3 3x21 9x7 7x9
64: 1x64 64x1 32x2 2x32 16x4 4x16 8x8
65: 1x65 65x1 13x5 5x13
66: 1x66 66x1 33x2 2x33 22x3 3x22 11x6 6x11
67: 1x67 67x1
68: 1x68 68x1 34x2 2x34 17x4 4x17
69: 1x69 69x1 23x3 3x23
70: 1x70 70x1 35x2 2x35 14x5 5x14 10x7 7x10
71: 1x71 71x1
72: 1x72 72x1 36x2 2x36 24x3 3x24 18x4 4x18 12x6 6x12 9x8 8x9
73: 1x73 73x1
74: 1x74 74x1 37x2 2x37
75: 1x75 75x1 25x3 3x25 15x5 5x15
76: 1x76 76x1 38x2 2x38 19x4 4x19
77: 1x77 77x1 11x7 7x11
78: 1x78 78x1 39x2 2x39 26x3 3x26 13x6 6x13
79: 1x79 79x1
80: 1x80 80x1 40x2 2x40 20x4 4x20 16x5 5x16 10x8 8x10
81: 1x81 81x1 27x3 3x27 9x9
82: 1x82 82x1 41x2 2x41
83: 1x83 83x1
84: 1x84 84x1 42x2 2x42 28x3 3x28 21x4 4x21 14x6 6x14 12x7 7x12
85: 1x85 85x1 17x5 5x17
86: 1x86 86x1 43x2 2x43
87: 1x87 87x1 29x3 3x29
88: 1x88 88x1 44x2 2x44 22x4 4x22 11x8 8x11
89: 1x89 89x1
90: 1x90 90x1 45x2 2x45 30x3 3x30 18x5 5x18 15x6 6x15 10x9 9x10
91: 1x91 91x1 13x7 7x13
92: 1x92 92x1 46x2 2x46 23x4 4x23
93: 1x93 93x1 31x3 3x31
94: 1x94 94x1 47x2 2x47
95: 1x95 95x1 19x5 5x19
96: 1x96 96x1 48x2 2x48 32x3 3x32 24x4 4x24 16x6 6x16 12x8 8x12
97: 1x97 97x1
98: 1x98 98x1 49x2 2x49 14x7 7x14
99: 1x99 99x1 33x3 3x33 11x9 9x11
100: 1x100 100x1 50x2 2x50 25x4 4x25 20x5 5x20 10x10

find number of different matrices( N) of all size s (no. of elements)?

2 Answers2