A071304 -id:A071304 - cp's OEIS frontend

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).

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

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

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

			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)

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.

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

FoldList[Times, 1, LinearRecurrence[{3, -3, 9}, {4, 6, 24}, 12]] (* Amiram Eldar, Jun 22 2025 *)

{ 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

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

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

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.

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jun 11 2002

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

			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)

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.

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

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

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

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

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

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

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

{ 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

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

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

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).

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

			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)

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

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

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

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

Original entry on oeis.org

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

Offset: 1

R. H. Hardin, Jun 11 2002

nonn

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

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

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

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

Original entry on oeis.org

1, 32, 4608, 7077888, 101921587200, 19725496300339200, 49628717475771816345600

Offset: 1

R. H. Hardin, Jun 11 2002

Cf. A003053, A071302, A071303, A071304, A071305, A071306, A071307, A071308, A071309, A071900.

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

a(6) from Max Alekseyev, Nov 06 2022

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

A330607 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 5) with x_i in 0..4, where n >= 0 and 0 <= k <= 4.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 2, 0, 0, 2, 9, 4, 4, 4, 4, 25, 30, 20, 20, 30, 145, 120, 120, 120, 120, 625, 650, 600, 600, 650, 3225, 3100, 3100, 3100, 3100, 15625, 15750, 15500, 15500, 15750, 78625, 78000, 78000, 78000, 78000, 390625, 391250, 390000, 390000, 391250, 1955625, 1952500, 1952500, 1952500, 1952500

Offset: 0

Petros Hadjicostas, Dec 20 2019

Let v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4)]' for n >= 0, where ' denotes transpose, and M = [[1,2,0,0,2], [2,1,2,0,0], [0,2,1,2,0], [0,0,2,1,2], [2,0,0,2,1]]. We claim that v(n+1) = M*v(n) for n >= 0.
To see why this is the case, let j in 0..4, and consider the expressions 0^2 + j, 1^2 + j, 2^2 + j, 3^2 + j, and 4^2 + j modulo 5. It can be easily proved that these five numbers contain M[0,j] 0's, M[1,j] 1's, M[2,j] 2's, M[3,j] 3's, and M[4,j] 4's. (This is how the transfer matrix M was constructed. The idea is similar to Jianing Song's ideas for sequences A101990, A318609, and A318610.)
It follows that v(n) = M^n * v(0), where v(0) = [1,0,0,0,0]'.
The minimal polynomial for M is (z - 5)*(z^2 - 5) = z^3 - 5*z^2 - 5*z + 25. Thus, M^3 - 5*M^2 - 5*M + 25*I = 0, and so M^n*v(0) - 5*M^(n-1)*v(0) - 5*M^(n-2)*v(0) + 25*M^(n-3)*v(0) = 0 for n >= 3. This implies v(n) - 5*v(n-1) - 5*v(n-2) + 25*v(n-3) = 0 for n >= 3. Hence each sequence (T(n,k): n >= 0) satisfies the same recurrence b(n) - 5*b(n-1) - 5*b(n-2) + 25*b(n-3) = 0 for n >= 3.
Clearly, for each k in 0..4, we may find constants c_k, d_k, e_k such that T(n,k) = c_k*sqrt(5)^n + d_k*(-sqrt(5))^n + e_k*5^n for n >= 0. We omit the details.

			Array T(n,k) (with rows n >= 0 and columns 0 <= k <= 4) begins as follows:
     1,    0,    0,    0,    0;
     1,    2,    0,    0,    2;
     9,    4,    4,    4,    4;
    25,   30,   20,   20,   30;
   145,  120,  120,  120,  120;
   625,  650,  600,  600,  650;
  3225, 3100, 3100, 3100, 3100;
  ...
T(n=2,k=0) = 9 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 0 (mod 5) (with x_1, x_2 in 0..4): (0,0), (1,2), (1,3), (2,1), (2,4), (3,1), (3,4), (4,2), and (4,3).
T(n=2,k=1) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 1 (mod 5) (with x_1, x_2 in 0..4): (0,1), (0,4), (1,0), and (4,0).
T(n=2,k=2) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 2 (mod 5) (with x_1, x_2 in 0..4): (1,1), (1,4), (4,1), and (4,4).
T(n=2,k=3) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 3 (mod 5) (with x_1, x_2 in 0..4): (2,2), (2,3), (3,2), and (3,3).
T(n=2,k=4) = 4 because we have the following solutions (x_1, x_2) to the equation x_1^2 + x_2^2 == 4 (mod 5) (with x_1, x_2 in 0..4): (0,2), (0,3), (2,0), and (3,0).

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,5,0,0,0,0,5,0,0,0,0,-25).

Cf. A071304, A101990, A228920, A228921, A229136, A229138, A318609, A318610.

with(LinearAlgebra);
v := proc(n) local M, v0;
   M := Matrix([[1, 2, 0, 0, 2], [2, 1, 2, 0, 0], [0, 2, 1, 2, 0], [0, 0, 2, 1, 2], [2, 0, 0, 2, 1]]); v0 := Matrix([[1], [0], [0], [0], [0]]);
  if n = 0 then v0; else MatrixMatrixMultiply(MatrixPower(M, n), v0); end if;
end proc;
seq(seq(v(n)[k, 1], k = 1 .. 5), n = 0 .. 10);

Vec((1 - 4*x^5 + 2*x^6 + 2*x^9 - x^10 - 6*x^11 + 4*x^12 + 4*x^13 - 6*x^14) / ((1 - 5*x^5)*(1 - 5*x^10)) + O(x^50)) \\ Colin Barker, Dec 21 2019

T(n,k) = 5*T(n-1,k) + 5*T(n-2,k) - 25*T(n-3,k) for n >= 3 with initial conditions for T(0,k), T(1,k), and T(2,k) (for each value of k in 0..4) given in the example below.
T(n,k) = 5*T(n-2,k) + 4*5^(n-2) for n >= 2.
T(n,k=1) = T(n,k=4) and T(n,k=2) = T(n,k=3).
T(n,k) ~ 5^(n-1) for each k in 0..4.
Sum_{k = 0..4} T(n,k) = 5^n.
v(n+1) = M*v(n) and v(n) = M^n * [1,0,0,0,0]' for n >= 0, where M = [[1,2,0,0,2], [2,1,2,0,0], [0,2,1,2,0], [0,0,2,1,2], [2,0,0,2,1]] and v(n) = [T(n,0), T(n,1), T(n,2), T(n,3), T(n,4)]'.
Conjecture: T(n,k=1) = A071304(n)/A071304(n-1) for n >= 2.
From Colin Barker, Dec 21 2019: (Start)
If we consider the array as a single sequence (a(n): n >= 1), then:
G.f.: (1 - 4*x^5 + 2*x^6 + 2*x^9 - x^10 - 6*x^11 + 4*x^12 + 4*x^13 - 6*x^14) / ((1 - 5*x^5)*(1 - 5*x^10)).
a(n) = 5*a(n-5) + 5*a(n-10) - 25*a(n-15) for n > 14. (End)

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.

Original entry on oeis.org

1, 16, 1536, 786432, 2013265920

Offset: 1

R. H. Hardin, Jun 12 2002

			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)

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.

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

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

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Crossrefs

Formula

Extensions

A330607 Array read by rows: T(n,k) is the number of solutions to the equation Sum_{i=1..n} x_i^2 == k (mod 5) with x_i in 0..4, where n >= 0 and 0 <= k <= 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula