Unable to invert matrix on Galois Field, even though the matrix should be invertible by construction

Question

We are trying to implement a general file recovery algorithm using Galois Fields. We have implemented the operations for Galois Fields GF(2^8) succesfully, but we're are running into a problem for the case with 4 data drives and 4 parity drives. More specifically, the case where data drives 0, 1, and 2, and parity drive 2 are missing.

Following the implementation in this paper, we construct an 8 by 4 matrix:

1   0   0   0 
0   1   0   0
0   0   1   0
0   0   0   1
1   1   1   1
1   2   3   4
1^2 2^2 3^2 4^2
1^3 2^3 3^3 4^3

Since datadrives 0, 1, and 2, and parity drive 2 are compromised, we omit the rows 0, 1, 2, and 6. That leaves

0   0   0   1         0  0  0  1 
1   1   1   1     =   1  1  1  1
1   2   3   4         1  2  3  4
1^3 2^3 3^3 4^3       1  8 15 64

Let's call this matrix A'. If D is the data vector, and E' is the vector corresponding to the data on the drives that did not fail, we should be able to solve A' D = E' for D.

D = A'^{-1} A' D = A'^{-1} E'

However, matrix A' doesn't seem to be invertible. See also this code snippet at sageMath:

SageMath even shows that the matrix can be simplified to

A' =
[0 0 0 1]
[1 1 1 1]
[1 0 1 0]
[1 0 1 0]

which is clearly not invertible. Somehow the parity rows [1^1, 2^1, 3^1, 4^1] and [1^3, 2^3, 3^3, 4^3] are linearly dependent. We thought these rows were constructed to be independent, even with the operations on GF(2^8)

Clearly, we're missing something, but at this point, we're not sure what's happening here.

UPDATE 1

So it turns out the generator matrix in that paper was completely wrong. Following the suggestion by Jyrki in the comments here, we constructed the desired matrix starting from a variant of the Vandermonde matrix. This variant is of the form:

$$G = \left( \begin{array}{ cccc } \alpha_0^0 & \alpha_0^1 & .. & \alpha_0^d \\ \alpha_1^0 & \alpha_1^1 & .. & \alpha_1^d \\ .. & .. & .. & .. & .. \\ \alpha_{d+p}^0 & \alpha_{d+p}^1 & .. & \alpha_{d+p}^d \\ \end{array} \right)$$ where the $d$ is the number of data bits, $p$ is the number of parity bits, and $\alpha_i$ are chosen elements of order $2^8$ in $GF(2^8)$. These alpha can be constructed by taking the Galois Field element with 2 as its integer representation, and raising it to a power that shares no prime factors with $2^8 - 1$. So:

$\alpha_0 = 2^1$,

$\alpha_1 = 2^2$,

$\alpha_2 = 2^4$ (skip $2^3$ because 3 has a prime in common with $2^8-1$),

$\alpha_3 = 2^7$ (skip $2^5$ and $2^6$ because 5 and 6 share prime factors with $2^8-1$),

$\alpha_4 = 2^8$, etc

I must admit that I don't understand this argument completely, but it works for now. For the top $d \times d$ block (let's call it $P$), we compute $P^{-1}$ and calculate $GP^{-1}$ to get it in the desired form.

We also tried the matrix on described in this paper, which uses the same base $\alpha$, which also works as far as we can tell.

We have also looked at multiple other software implementations, where they appear to determine the parity block in one go (so without calculating $GP^{-1}$. The code however is very difficult to understand. Could there be a standard procedure to immediately generate that bottom block or do these software packages only work for a specific order of the field and polynomial?

Answer 1

Even though the OP apparently used Sage incorrectly, the example matrix $A$ is singular, and there is an error in the argument from the article. The weak argument in the source is on page 6. The matrix is constructed by putting an n×n identity block on top of a Vandermonde block of the same size. The author then bluntly claims that because the rows of the Vandermonde block are linearly independent (correct) any collection of $n$ rows of the $(2n)\times n$ matrix is also linearly independent. There is no reason for that to be the case.

In fact, the title page of the linked article contains the disclaimer:

The information dispersal matrix $A$ given in this paper does not have the desired properties. Please see TechnicalReportCS-03-504 for a correction to this problem. This technical report is available at http://www.cs.utk.edu/~plank/papers/CS-03-504.pdf

---

Also see Lubin's comment, you need to use Sage's function for conversion of integers to elements of the field

     F =GF(256)
     MS = MatrixSpace(F, 4, 4)

     M = MS.matrix([0,0,0,1, 1,1,1,1, 1,F.fetch_int(2),F.fetch_int(3),F.fetch_int(4), 1,F.fetch_int(2)^3,F.fetch_int(3)^3,F.fetch_int(4)^3])
     print(M)