How can I do Gaussian elimination of a $32 \times 32$ bit matrix?

Question

I have been looking at how to reverse the sigma operation in the sha256 hash and in several places I have seen that you have to make a $32 \times 32$ bit matrix and then solve it with Gaussian elimination.

On this same page I have found this question that is quite well formulated and well answered but I cannot finally understand how it does the elimination. How to solve a system of 32 XOR equations via Gaussian Elimination?

I have spent several days trying to understand and I have been seeing how to solve the elimination and I manage to understand it with a smaller matrix with its unknowns as in this other question how to solve system of linear equations of XOR operation?

In the first link, start with the following matrix.

0:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
1:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
2:  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 1
3:  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 1
4:  0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
5:  0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 | 0
6:  0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 | 0
7:  1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
8:  0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
9:  0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 | 0
10: 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 | 1
11: 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 | 0
12: 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 | 1
13: 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 | 0
14: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 | 0
15: 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 | 0
16: 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 | 0
17: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 | 0
18: 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
19: 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
20: 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 | 0
21: 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 | 1
22: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 | 0
23: 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 | 0
24: 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 | 1
25: 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 | 1
26: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 | 1
27: 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 | 0
28: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 | 0
29: 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 | 1
30: 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 | 1
31: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 | 0

I understand that the bit part on the right 01110001101010000010010011100110, is the output of the sigma operation. But where does the bit 00000000000000100000000001000000 part with which it does the right rotates come from?

The first link is a part of the question owner's total question and if we follow the link it leaves,(Reverse SHA-256 sigma0 function within complexity of O(n)?) it takes us to stack overflow where the answer marked as correct contains a series of hexadecimal numbers called "sigma0 singleton inverses" that I would like know that they are ignored and create new doubts as if they are constant values, or if they are obtained from another operation... If so, I would like to know what operation it is

I mean this part : sigma0_singleton_inverses = [0x185744e9, 0x30ae89d2, 0x615d13a4, 0xdaed63a1, 0x9cd03a8e, 0x08fdcc39, 0x11fb9872, 0x23f730e4, 0x5fb92521, 0xbf724a42, 0x57ee6948, 0xafdcd290, 0x76b358ec, 0xf531f531, 0xc36917ae, 0xb78f9679, 0x4615d13e, 0x947ce695, 0x19a4740f, 0x2b1facf7, 0x4e681d07, 0x84877ee7, 0x385344eb, 0x70a689d6, 0xf91a5745, 0xc36917af, 0xb78f967b, 0x4615d13a, 0x8c2ba274, 0x290afdcd, 0x4a42bf73, 0x94857ee6 ]

What do these "sigma singleton inverse" values mean?

I don't know if I posted the question in the right place since it contains topics about cryptography, mathematics and programming and I didn't know where to post it. If I made a mistake putting it in this section, tell me so I can correct it and publish it in the correct place.

Answer 1

I would like just to illustrate the excellent answer by Joriki by displaying the inverse matrix, illustrating two facts :

1. that indeed the binary (or hexadecimal) codes of the rows have to be read in the backward direction.

2. that constracting with the initial matrix, its inverse (on the right) has a weird structure... The only special feature one can recognize on it is its symmetry with respect to the second diagonal shared with ( = inherited from) the initial matrix.

Fig. 1 : The initial matrix and its inverse.

Check for example that the second row of the inverse is (when read backwards)

$(0011)(0000)(1010)(1110)(1000)(1001)(1101)(0010)$

$ \ \ \ \ \ 3 \ \ \ \ \ \ \ \ \ 0 \ \ \ \ \ \ \ \ \ a \ \ \ \ \ \ \ \ \ e \ \ \ \ \ \ \ \ \ 8 \ \ \ \ \ \ \ \ \ 9 \ \ \ \ \ \ \ \ \ d \ \ \ \ \ \ \ \ \ 2$

Answer 2

The matrix is slightly confusing in that the bits are arranged in reverse order, least significant first, so that the right shift/rotate becomes left shift/rotate. Each row is the result of applying the $\sigma_0$ function to a $32$-bit word with a single bit set. For instance, the first row shows the result of applying it to the word with only the $0$-th bit set. The right rotate by $7$ produces a $1$ in the $25$-th bit, the right rotate by $18$ produces a $1$ in the $14$-th bit, and the right shift by $3$ shifts the $1$ bit beyond the end of the word and thus doesn’t contribute in this case. You can see how it first becomes relevant in row $3$, which is the result of applying $\sigma_0$ to a word with the $3$rd bit set, because here the right shift by $3$ shifts that bit into the $0$-th bit.

The “singleton inverses” are the rows of the inverse matrix; for instance, the $0$-th entry in that array, $185744\mathrm E9_{16}=00011000010101110100010011101001_2$, is the result of applying the inverse operation to a word with only the $0$-th bit set. So they’ve inverted the binary matrix and provided the rows of the inverse, so you can apply the inverse operation as shown in the code there, “adding” (i.e. XORing) up the contributions for the bits, adding in the value in the array whenever the corresponding bit is set in the word to be inverted.