I Transforming a Matrix: Elementary Methods for Finite Fields

[Lapidus]

I want to transform the first matrix below into the second one. The book ( Neutsch, "Coordinates") says this can be done by elementary transformation. I guess he means by some Gaussian elimination. But the entries of the matrix are from the finite field 2, so I can not multiply rows, that would give me just a zero row. Of course, 1 + 1 = 0.

I see when I add row 7 to row 5 in the first matrix, I get the last row in the transformed matrix. Also, when I add row 7 to row 4, I get row 11 in the transformed matrix. But then?

How elementary is that? How should I proceed?

Thank you in advance

 

[Mark44]

I want to transform the first matrix below into the second one. The book ( Neutsch, "Coordinates") says this can be done by elementary transformation. I guess he means by some Gaussian elimination.

Those aren't the same. The elementary transformations consist of three row operations:
1) Exchanging two rows -- R_m ↔ R_n
2) Replacing a row by a nonzero multiple of itself -- R_m ← k * R_m
3) Replacing a row by the sum of itself and a nonzero multiple of another row -- R_m ← R_m + k * R_n

Performing Gaussian elimination means performing some sequence of these row operations in order to transform the matrix into row-echelon form, which is what is shown in the second matrix in your images.

But the entries of the matrix are from the finite field 2, so I can not multiply rows, that would give me just a zero row. Of course, 1 + 1 = 0.

I see when I add row 7 to row 5 in the first matrix, I get the last row in the transformed matrix. Also, when I add row 7 to row 4, I get row 11 in the transformed matrix. But then?

How elementary is that? How should I proceed?

Thank you in advance

View attachment 210851 View attachment 210852

 

[willem2]

It's really no different whatever field you use.
If you use real numbers, and you are trying to create a zero in the first column of row k, you would multiply the first row by ( a_k1/a₁₁) and subtract it from the k^th row. If the pivot a₁₁ happens to be 0 you would permute the first row with another row that has a non-zero value in the first column. If a_k1 is zero, there is already a zero in the first column, and you don't have to do anything with that row.
With members of a finite field, if both a₁₁ and a_k1 are non-zero the only possibility is that they are both equal to 1, so (a_k1/a₁₁) is also 1, so you can just subtract (or add) the first row to the k^th row.

 

[Lapidus]

Thanks for the replies. But still not quite clear.

As I understand multiplying is useless in this case. I can just add rows to get zeroes.

To be concrete , what about the tenth line in the transformed matrix (0000 0000 0011 0011 0011 0011), which rows do I have to add to get this transformed row? Where do start? Is there some mechanism or do I have to look which rows added give this row?

Or do I have to start with the top so that I end up with the new top row (1000 0001 0001 0111 0010 0100) somehow?

 

[I like Serena]

Start by swapping the top row with another row that has a 1 in the leftmost column.
Then add the new top row to any other row that has a 1 in the leftmost column.
As a result the leftmost column will have a 1 at the top, and 0's in all other positions.

Now repeat.

 

[Lapidus]

Start by swapping the top row with another row that has a 1 in the leftmost column.
Then add the new top row to any other row that has a 1 in the leftmost column.
As a result the leftmost column will have a 1 at the top, and 0's in all other positions.

Now repeat.

That sounds good. But that way I will not get the top row given in the transformed matrix. Because the row simply does not appear anywhere in the original matrix, so I can not swap it to the top!

 

[I like Serena]

That sounds good. But that way I will not get the top row given in the transformed matrix. Because the row simply does not appear anywhere in the original matrix, so I can not swap it to the top!

The top row won't stay the same.
In later iterations, we will add a lower row to the top row to eliminate a 1.
Consequently the top row will slowly start to look like the top row in the transformed matrix.
Only one way to find out...

 

[Lapidus]

There does not happen to be some software for such kind of calculations?

Also, is it easier to transform the triangle matrix back into the original form than the other way around?

 

[Mark44]

There does not happen to be some software for such kind of calculations?

There might be, but with this type of problem and what I perceive as your level of knowledge, I would recommend against it. Inasmuch as the field here consists only of 0's and 1's, row reduction is a lot simpler than if the numbers were integers or, worse, real numbers.

Also, is it easier to transform the triangle matrix back into the original form than the other way around?

I think it would be easier to transform the original matrix into triangular form than to go the other way.

As recommended earlier, it's time to bite the bullet and start work on this problem ...