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.

1, 1, 1, 2, 2, 1, 1, 6, 24, 51, 60, 24, 2, 1, 12, 96, 542, 2058, 5316, 7530, 4058, 541, 6, 1, 20, 260, 2570, 19680, 117860, 540470, 1769710, 3571175, 3225310, 736540, 15740, 24, 1, 30, 570, 8415, 101610, 1026852, 8747890, 61978340, 355193925, 1561232840, 4753747050, 8111988473, 4866461728, 437272014, 949902, 120

Offset: 0

Author

Søren Fuglede Jørgensen, Mar 08 2025

Keywords

• nonn
• tabf
• hard

Comments

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.

Also the number of different elements that can be represented by minimal quantum circuits of k CNOT gates on n qubits.

Examples

			Triangle begins:
   n\k  0    1    2    3    4    5    6    7    8    9
   0:   1
   1:   1
   2:   1    2    2    1
   3:   1    6   24   51   60   24    2
   4:   1   12   96  542 2058 5316 7530 4058  541    6
   ...
For n = 2, k = 1, the two matrices are [[1, 1], [0, 1]] and [[1, 0], [1, 1]].
For n = 2, k = 2, the two matrices are [[1, 1], [1, 0]] and [[0, 1], [1, 1]].
For n = 2, k = 3, the only matrix is [[0, 1], [1, 0]].
		

Links

• Søren Fuglede Jørgensen, Table of n, a(n) for n = 0..83
• Marc Bataille, Quantum Circuits of CNOT gates: Optimization and Entanglement, Quantum Information Processing, 21(7):269 (2022).
• Jens Emil Christensen, Søren Fuglede Jørgensen, Andreas Pavlogiannis, and Jaco van de Pol, On Exact Sizes of Minimal CNOT Circuits, RC 2025, LNCS, vol 15716, pp. 71-88; arXiv:2503.01467 [quant-ph] (2025).
• Ketan N. Patel, Igor L. Markov, and John P. Hayes, Optimal synthesis of linear reversible circuits, Quantum Info. Comput., 8(3) (2008), pp. 282-294.

Crossrefs

Cf. A002378 (column 1), A172225 (column 2), A002884 (row sums).

Formula

T(n, 0) = 1.

T(n, 1) = n^2 - n.

T(n, 2) = (1/2)*(n^4 - 5*n^2 + 4*n).

T(n, 3) = (1/6)*(n^6 + 3*n^5 - 9*n^4 - 63*n^3 + 179*n^2 - 111*n).

Sum_{k>=0} T(n,k) = A002884(n).