cp's OEIS Frontend

A381854 Triangle read by rows: T(n, k) is the number of invertible n X n matrices over GF(2) that can be optimally row-reduced in k steps, n >= 0, k >= 0.

%I A381854 #50 Aug 15 2025 15:54:50
%S A381854 1,1,1,2,2,1,1,6,24,51,60,24,2,1,12,96,542,2058,5316,7530,4058,541,6,
%T A381854 1,20,260,2570,19680,117860,540470,1769710,3571175,3225310,736540,
%U A381854 15740,24,1,30,570,8415,101610,1026852,8747890,61978340,355193925,1561232840,4753747050,8111988473,4866461728,437272014,949902,120
%N A381854 Triangle read by rows: T(n, k) is the number of invertible n X n matrices over GF(2) that can be optimally row-reduced in k steps, n >= 0, k >= 0.
%C A381854 Using transvections as the generating set of the matrix group, this is the number of inequivalent minimal words in k generators; the number of elements at distance k from the identity in the corresponding Cayley graph.
%C A381854 Also the number of different elements that can be represented by minimal quantum circuits of k CNOT gates on n qubits.
%H A381854 Søren Fuglede Jørgensen, <a href="/A381854/b381854.txt">Table of n, a(n) for n = 0..83</a>
%H A381854 Marc Bataille, <a href="https://link.springer.com/article/10.1007/s11128-022-03577-8">Quantum Circuits of CNOT gates: Optimization and Entanglement</a>, Quantum Information Processing, 21(7):269 (2022).
%H A381854 Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, <a href="https://doi.org/10.1007/978-3-031-97063-4_6">On Exact Sizes of Minimal CNOT Circuits</a>, RC 2025, LNCS, vol 15716, pp. 71-88; <a href="https://arxiv.org/abs/2503.01467">arXiv:2503.01467</a> [quant-ph] (2025).
%H A381854 Ketan N. Patel, Igor L. Markov, and John P. Hayes, <a href="https://dlnext.acm.org/doi/10.5555/2011763.2011767">Optimal synthesis of linear reversible circuits</a>, Quantum Info. Comput., 8(3) (2008), pp. 282-294.
%F A381854 T(n, 0) = 1.
%F A381854 T(n, 1) = n^2 - n.
%F A381854 T(n, 2) = (1/2)*(n^4 - 5*n^2 + 4*n).
%F A381854 T(n, 3) = (1/6)*(n^6 + 3*n^5 - 9*n^4 - 63*n^3 + 179*n^2 - 111*n).
%F A381854 Sum_{k>=0} T(n,k) = A002884(n).
%e A381854 Triangle begins:
%e A381854    n\k  0    1    2    3    4    5    6    7    8    9
%e A381854    0:   1
%e A381854    1:   1
%e A381854    2:   1    2    2    1
%e A381854    3:   1    6   24   51   60   24    2
%e A381854    4:   1   12   96  542 2058 5316 7530 4058  541    6
%e A381854    ...
%e A381854 For n = 2, k = 1, the two matrices are [[1, 1], [0, 1]] and [[1, 0], [1, 1]].
%e A381854 For n = 2, k = 2, the two matrices are [[1, 1], [1, 0]] and [[0, 1], [1, 1]].
%e A381854 For n = 2, k = 3, the only matrix is [[0, 1], [1, 0]].
%Y A381854 Cf. A002378 (column 1), A172225 (column 2), A002884 (row sums).
%K A381854 nonn,tabf,hard
%O A381854 0,4
%A A381854 _Søren Fuglede Jørgensen_, Mar 08 2025