Instructions: Transform the matrix to the identity matrix in 9 steps. The identity matrix has ones along the main diagonal (top left to bottom right) and zeros elsewhere. A step consists of adding one row to another, then replacing the twos with zeros (i.e. adding mod 2). To perform this operation, click on two of the buttons (R1, R2, R3, R4) to the left of the matrix.
It is believed (but not proved) that 3n − 3 steps are required in general. Can you prove this? Let me know!
Technical discussion: 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 Θ(n2/log(n)).
Created by David Radcliffe. This project is on GitHub.