why did you say vandermonde matrix 'does not guarantee invertable for every sub matrix'

[templexxx]

/**

• @brief Generate a matrix of coefficients to be used for encoding.
• Vandermonde matrix example of encoding coefficients where high portion of
• matrix is identity matrix I and lower portion is constructed as 2^{i*(j-k+1)}
• i:{0,k-1} j:{k,m-1}. Commonly used method for choosing coefficients in
• erasure encoding but does not guarantee invertable for every sub matrix. For
• large k it is possible to find cases where the decode matrix chosen from
• sources and parity not in erasure are not invertable. Users may want to
• adjust for k > 5.
• @param a [mxk] array to hold coefficients
• @param m number of rows in matrix corresponding to srcs + parity.
• @param k number of columns in matrix corresponding to srcs.
• @returns none */

void gf_gen_rs_matrix(unsigned char *a, int m, int k);

[gbtucker]

Note the function ec_encode_data() works with any encoding matrix you can construct. The above function fills out one possible encoding matrix where the lower portion describing parity production is a Vandermonde matrix following the common RAID sequence {2}^(i*j). When decoding after a set of erasures you typically invert a sub-matrix of the encoding matrix to find the decode matrix. As it states it is possible to find a k x k sub-matrix that is not invertable for large k.

[templexxx]

--- update 01/07/2017 ----

I found the prove of that. It's easy to think about it with the idea of matrix's rank

---- previous commented ---- @gbtucker that's my calculation: as we all know, if we have two same columns in a matrix, the det will be 0, it means the matrix has no inverse. so I need to make a matrix there are two raws in cycle. And I will the coefficient is 2^n, and n = (i (j -k +1)),lets make the 2^(j-k+1) be the baseNum.In galois field,the p(x)'s exp is (j-k+1). (j-k+1) i mod 255 = t, we also need (j-k+1) (i+s) mod 255 = t (s < k). And for two same columns , (j-k+1) s = 510 too. That's my encode matrix: ( k = 16, m = 186) matrix[32]=[1 152 78 10 153 214 68 147 79 146 215 220 221 69 11 1],matrix[185]=[1 215 214 1 215 214 1 215 214 1 215 214 1 215 214 1].

[templexxx]

I'm a beginner in program and math. I write the code through reading the documents but not using the ISA-L code directly( I don't know how to write code in C language). Maybe I made a mistake above. If I'm wrong please tell me. Thank you very much

[gbtucker]

@templexxx I'm not sure I understand the sequence in your encoding matrix. You can always do an exhaustive search to look for non-invertable sub-matrices for the encoding matrix you have created to check. Or you can use another that is guaranteed by other means such as Cauchy.

[templexxx]

@gbtucker Thank you. I will try to learn it. :D

[jasonkresch]

There is a way to generate a systematic encoding matrix that is guaranteed to be invertible in any case. It works as follows:

Step 1. Generate a K by K+M Vandermonde matrix Step 2. Generate a K by K Vandermonde matrix Step 3. Invert the K by K Vandermonde matrix generated in step 2 Step 4. Multiply the matrix generated step 1 by the inverse Vandermonde matrix created in step 3

The matrix resulting from step 4 can serve as an encoding matrix. The first K x K rows will correspond to the identity matrix. The remaining bottom M rows can serve the purposes of encoding redundancy.

For reference, this is how the matrix is generated in other Reed-Solomon libraries, such as zfec: https://github.com/tahoe-lafs/zfec/blob/master/zfec/fec.c#L420