A071310 -id:A071310

A071302

a(n) = (1/2) * (number of n X n 0..2 matrices M with MM' mod 3 = I, where M' is the transpose of M and I is the n X n identity matrix).

+10
11

1, 4, 24, 576, 51840, 13063680, 9170703360, 19808719257600, 131569513308979200, 2600339861038664908800, 152915585868239728626892800, 27051378802435080953011843891200, 14395932257291877030764312963579904000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also, number of n X n orthogonal matrices over GF(3) with determinant 1. - Max Alekseyev, Nov 06 2022

LINKS

Table of n, a(n) for n=1..13.

Jianing Song, Structure of the group SO(2,Z_n).

László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv:1404.4214 [math.NT], 2014.

László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), #14.11.6.

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

FORMULA

a(2k+1) = 3^k * Product_{i=0..k-1} (3^(2k) - 3^(2i)); a(2k) = (3^k + (-1)^(k+1)) * Product_{i=1..k-1} (3^(2k) - 3^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

a(n+1) = a(n) * A318609(n+1) for n >= 1. - conjectured by Petros Hadjicostas, Dec 18 2019; proved based on the explicit formula by Max Alekseyev, Nov 06 2022

EXAMPLE

From Petros Hadjicostas, Dec 17 2019: (Start)

For n = 2, the 2*a(2) = 8 n X n matrices M with elements in {0, 1, 2} that satisfy MM' mod 3 = I are the following:

(a) With 1 = det(M) mod 3:

[[1,0],[0,1]]; [[0,1],[2,0]]; [[0,2],[1,0]]; [[2,0],[0,2]].

This is the abelian group SO(2, Z_3). See the comments for sequence A060968.

(b) With 2 = det(M) mod 3:

[[0,1],[1,0]]; [[0,2],[2,0]]; [[1,0],[0,2]]; [[2,0],[0,1]].

Note that, for n = 3, we have 2*a(3) = 2*24 = 48 = A264083(3). (End)

PROG

(PARI) { a071302(n) = my(t=n\2); prod(i=0, t-1, 3^(2*t)-3^(2*i)) * if(n%2, 3^t, 1/(3^t+(-1)^t)); } \\ Max Alekseyev, Nov 06 2022

CROSSREFS

Cf. A003053, A003920, A060968, A071303, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(8) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071303

1/2 times the number of n X n 0..3 matrices M with MM' mod 4 = I, where M' is the transpose of M and I is the n X n identity matrix.

+10
9

1, 8, 192, 12288, 1966080, 1509949440, 5411658792960

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

It seems that a(n) = n! * 2^(binomial(n+1,2) - 1) for n = 1, 2, 3, 4, 5, while for n = 6, a(n) is twice this number. The number n! * 2^(binomial(n+1,2) - 1) appears in Proposition 6.1 in Eriksson and Linusson (2000) as an upper bound to the number of three-dimensional permutation arrays of size n (see column k = 3 of A330490). - Petros Hadjicostas, Dec 16 2019

a(7) = 7! * 2^30. - Sean A. Irvine, Jul 11 2024

LINKS

Table of n, a(n) for n=1..7.

Kimmo Eriksson and Svante Linusson, A combinatorial theory of higher-dimensional permutation arrays, Adv. Appl. Math. 25(2) (2000a), 194-211; see Proposition 6.1 (p. 210).

Sean A. Irvinne, Java program (github)

Jianing Song, Structure of the group SO(2,Z_n).

László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv:1404.4214 [math.NT], 2014.

László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), #14.11.6.

EXAMPLE

From Petros Hadjicostas, Dec 16 2019: (Start)

For n = 2, here are the 2*a(2) = 16 2 x 2 matrices M with elements in {0,1,2,3} that satisfy MM' mod 4 = I:

(a) With 1 = det(M) mod 4:

[[1,0],[0,1]]; [[0,1],[3,0]]; [[0,3],[1,0]]; [[1,2],[2,1]];

[[2,1],[3,2]]; [[2,3],[1,2]]; [[3,0],[0,3]]; [[3,2],[2,3]].

These form the abelian group SO(2, Z_n). See the comments for sequence A060968.

(b) With 3 = det(M) mod 4:

[[0,1],[1,0]]; [[0,3],[3,0]]; [[1,0],[0,3]]; [[1,2],[2,3]];

[[2,1],[1,2]]; [[2,3],[3,2]]; [[3,0],[0,1]]; [[3,2],[2,1]].

Note that, for n = 3, we have 2*a(3) = 2*192 = 384 = A264083(4). (End)

CROSSREFS

Cf. A003920, A060968, A071302, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A229136, A264083, A330490.

KEYWORD

nonn,more

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

a(7) from Sean A. Irvine, Jul 11 2024

STATUS

approved

A071304

a(n) = (1/2) * (number of n X n 0..4 matrices M with MM' mod 5 = I, where M' is the transpose of M and I is the n X n identity matrix).

+10
9

1, 4, 120, 14400, 9360000, 29016000000, 457002000000000, 35646156000000000000, 13946558535000000000000000, 27230655539587500000000000000000, 266009466302345390625000000000000000000, 12987912192212013697265625000000000000000000000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also, number of n X n orthogonal matrices over GF(5) with determinant 1. - Max Alekseyev, Nov 06 2022

LINKS

Table of n, a(n) for n=1..12.

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

Jianing Song, Structure of the group SO(2,Z_n).

FORMULA

a(2k+1) = 5^k * Product_{i=0..k-1} (5^(2k) - 5^(2i)); a(2k) = (5^k - 1) * Product_{i=1..k-1} (5^(2k) - 5^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

From Petros Hadjicostas, Dec 20 2019: (Start)

Let b(n) be the number of solutions to the equation Sum_{i = 1..n} x_i^2 = 1 (mod 5) with x_i in 0..4. We have that b(n) = 5*b(n-1) + 5*b(n-2) - 25*b(n-3) for n >= 3 with b(0) = 0, b(1) = 2, and b(2) = 4.

We have b(n) = A330607(n, k=1) for n >= 0.

We conjecture that a(n+1) = a(n)*b(n+1) for n >= 1. (End)

EXAMPLE

From Petros Hadjicostas, Dec 17 2019: (Start)

For n = 2, the 2*a(2) = 8 n X n matrices M with elements in {0,1,2,3,4} that satisfy MM' mod 5 = I are the following:

(a) those with 1 = det(M) mod 5:

[[1,0],[0,1]]; [[0,4],[1,0]]; [[0,1],[4,0]]; [[4,0],[0,4]].

These form the abelian group SO(2, Z_5). See the comments for sequence A060968.

(b) those with 4 = det(M) mod 5:

[[0,1],[1,0]]; [[0,4],[4,0]]; [[1,0],[0,4]]; [[4,0],[0,1]].

Note that, for n = 3, we have 2*a(3) = 2*120 = 240 = A264083(5). (End)

PROG

(PARI) { a071304(n) = my(t=n\2); prod(i=0, t-1, 5^(2*t)-5^(2*i)) * if(n%2, 5^t, 1/(5^t+1)); } \\ Max Alekseyev, Nov 06 2022

CROSSREFS

Cf. A060968, A071302, A071303, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609, A330607.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(7) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071306

a(n) = (1/2) * (number of n X n 0..6 matrices M with MM' mod 7 = I, where M' is the transpose of M and I is the n X n identity matrix).

+10
9

1, 8, 336, 112896, 276595200, 4662288691200, 546914437209907200, 450219964711195607040000, 2596509480922336727312302080000, 104784757384177668346109081238896640000, 29597339316082819652234687848790174733434880000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also, number of n X n orthogonal matrices over GF(7) with determinant 1. - Max Alekseyev, Nov 06 2022

LINKS

Table of n, a(n) for n=1..11.

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

FORMULA

a(2k+1) = 7^k * Product_{i=0..k-1} (7^(2k) - 7^(2i)); a(2k) = (7^k + (-1)^(k+1)) * Product_{i=1..k-1} (7^(2k) - 7^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

Conjecture: Let b(n) be the number of solutions to the equation Sum_{i = 1..n} x_i^2 = 1 (mod 7) with x_i in 0..6. We conjecture that b(n) = 7*b(n-1) - 7*b(n-2) + 49*b(n-3) for n >= 4 with b(1) = 2, b(2) = 8, and b(3) = 42. We also conjecture that a(n+1) = a(n)*b(n+1) for n >= 1. - Petros Hadjicostas, Dec 19 2019

EXAMPLE

From Petros Hadjicostas, Dec 19 2019: (Start)

For n = 2, the 2*a(2) = 16 n X n matrices M with elements in 0..6 that satisfy MM' = I are the following:

(a) those with 1 = det(M) mod 7:

[[1,0],[0,1]]; [[0,1],[6,0]]; [[0,6],[1,0]]; [[2,2],[5,2]];

[[2,5],[2,2]]; [[5,2],[5,5]]; [[5,5],[2,5]]; [[6,0],[0,6]].

These are the elements of the abelian group SO(2,Z_7). See the comments for sequence A060968.

(b) those with 6 = det(M) mod 7:

[[0,1],[1,0]]; [[0,6],[6,0]]; [[1,0],[0,6]]; [[2,2],[2,5]];

[[2,5],[5,5]]; [[5,2],[2,2]]; [[5,5],[5,2]]; [[6,0],[0,1]].

Note that, for n = 3, we have 2*a(3) = 2*336 = 672 = A264083(7). (End)

PROG

(PARI) { a071306(n) = my(t=n\2); prod(i=0, t-1, 7^(2*t)-7^(2*i)) * if(n%2, 7^t, 1/(7^t+(-1)^t)); } \\ Max Alekseyev, Nov 06 2022

CROSSREFS

Cf. A060968, A071302, A071303, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083, A318609.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(6) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071309

a(n) = (1/2) * (number of n X n 0..10 matrices with MM' mod 11 = I).

+10
9

1, 12, 1320, 1742400, 25721308800, 4145554781913600, 7338585441586912128000, 142998501741091915820267520000, 30655092458961006120118267244605440000, 72283553302207308288060341547889057722286080000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Also, number of n X n orthogonal matrices over GF(11) with determinant 1. - Max Alekseyev, Nov 06 2022

LINKS

Table of n, a(n) for n=1..10.

Jessie MacWilliams, Orthogonal Matrices Over Finite Fields, The American Mathematical Monthly 76:2 (1969), 152-164.

FORMULA

a(2k+1) = 11^k * Product_{i=0..k-1} (11^(2k) - 11^(2i)); a(2k) = (11^k + (-1)^(k+1)) * Product_{i=1..k-1} (11^(2k) - 11^(2i)) (see MacWilliams, 1969). - Max Alekseyev, Nov 06 2022

PROG

(PARI) { a071309(n) = my(t=n\2); prod(i=0, t-1, 11^(2*t)-11^(2*i)) * if(n%2, 11^t, 1/(11^t+(-1)^t)); } \\ Max Alekseyev, Nov 06 2022

CROSSREFS

Cf. A071302, A071303, A071304, A071305, A071306, A071307, A071308, A071310.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(6) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071305

a(n) = (1/2) * (number of n X n 0..5 matrices M with MM' mod 6 = I, where M' is the transpose of M and I is the n X n identity matrix).

+10
8

1, 8, 144, 27648, 37324800, 300987187200, 13311459341107200, 3680352278629318656000, 6233449457837263300853760000, 63077322283364184001573740871680000, 3794639489522011031097665950031114403840000, 1374795579913014967183977466315375129593674465280000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..12.

FORMULA

a(n) = A003053(n) * A071302(n). - Max Alekseyev, Nov 06 2022

EXAMPLE

From Petros Hadjicostas, Dec 16 2019: (Start)

For n = 2, here are the 2*a(2) = 16 2 X 2 matrices M with elements in {0,1,2,3,4,5} that satisfy MM' mod 6 = I:

[[0,1],[1,0]]; [[0,1],[5,0]]; [[0,5],[1,0]]; [[0,5],[5,0]];

[[1,0],[0,1]]; [[1,0],[0,5]]; [[2,3],[3,2]]; [[2,3],[3,4]];

[[3,2],[2,3]]; [[3,2],[4,3]]; [[3,4],[2,3]]; [[3,4],[4,3]];

[[4,3],[3,2]]; [[4,3],[3,4]]; [[5,0],[0,1]]; [[5,0],[0,5]].

(End)

CROSSREFS

Cf. A003053, A071302, A071303, A071304, A071306, A071307, A071308, A071309, A071310.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(7) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071308

a(n) = (1/2) * (number of n X n 0..9 matrices with MM' mod 10 = I).

+10
8

1, 8, 720, 691200, 6739200000, 668528640000000, 663347543040000000000, 6622861869711360000000000000, 660754650163765248000000000000000000, 660543208675712843120640000000000000000000000, 6601093143555139842468151296000000000000000000000000000

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..11.

FORMULA

a(n) = A003053(n) * A071304(n). - Max Alekseyev, Nov 06 2022

CROSSREFS

Cf. A003053, A071302, A071303, A071304, A071305, A071306, A071307, A071309, A071310.

KEYWORD

nonn

AUTHOR

R. H. Hardin, Jun 11 2002

EXTENSIONS

Terms a(6) onward from Max Alekseyev, Nov 06 2022

STATUS

approved

A071900

1/4 times the number of n X n 0..7 matrices with MM' mod 8 = I, where M' is the transpose of M and I is the n X n identity matrix.

+10
6

1, 16, 1536, 786432, 2013265920

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

LINKS

Table of n, a(n) for n=1..5.

Jianing Song, Structure of the group SO(2,Z_n).

László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv:1404.4214 [math.NT], 2014.

László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), #14.11.6.

FORMULA

Conjecture: a(n) = 2^(n*(n-1)/2) * A071303(n) for n >= 1. - Michel Marcus, Nov 08 2022

EXAMPLE

From Petros Hadjicostas, Dec 18 2019: (Start)

For n = 2, the 4*a(2) = 64 n X n matrices M with elements in 0..7 that satisfy MM' mod 8 = I can be classified into four categories:

(a) Matrices M with 1 = det(M) mod 8. These form the abelian group SO(2, Z_8). See the comments for sequence A060968.

(b) Matrices M with 3 = det(M) mod 8. These are the elements of the left coset A*SO(2, Z_8) = {AM: M in SO(2, Z_8)}, where A = [[3,0],[0,1]].

(c) Matrices M with 5 = det(M) mod 8. These are the elements of the left coset B*SO(2, Z_8) = {BM: M in SO(2, Z_8)}, where B = [[5,0],[0,1]].

(d) Matrices M with 7 = det(M) mod 8. These are the elements of the left coset C*SO(2, Z_8) = {CM: M in SO(2, Z_8)}, where C= [[7,0],[0,1]].

All four classes of matrices have the same number of elements, that is, 16 each.

Note that for n = 3 we have 4*a(3) = 4*1536 = 6144 = A264083(8). (End)

CROSSREFS

Cf. A060968, A071302, A071303, A071304, A071305, A071306, A071307, A071308, A071309, A071310, A071900, A087784, A208895, A264083.

KEYWORD

nonn,more

AUTHOR

R. H. Hardin, Jun 12 2002

STATUS

approved