Post #93

https://radcliffe.github.io/01matrixpuzzle/ вместо картинок на выходных в этот раз пусть будет такая игра с матрицами «This app explores the group of nonsingular n-by-n matrices over the field of two elements. This group is generated by transvections, i.e. adding one row to another row mod 2. A row swap can be decomposed into three transvections, by the XOR trick. Since any permutation of n elements can be expressed as the product of at most n-1 transpositions, it follows that any permutation matrix can be expressed as the product of at most 3n-3 transvections. It is conjectured¹ that the cyclic permutation matrix of order n requires no fewer than 3n-3 transvections. This has been verified up to n = 8. Starting from a random invertible matrix, the expected number of steps is Θ(n²/log(n)).» ¹ https://arxiv.org/abs/2503.01467