# Matrix column permutation under constraint

Apologize if you've read my question on Mathoverflow, I'm very curious about whether there's an answer to this.

In coding theory, there are parity-check codes whose parity-check matrices H are generated via column permutations. For instance, the LDPC codes constructed in Gallager's 1962 IRE Trans paper uses the following $H$ matrix: $$H = \begin{bmatrix} \text{---} &X_1 &\text{---}\\ \text{---} &X_2 &\text{---}\\ &\vdots &\\ \text{---} &X_n &\text{---}\\ \end{bmatrix}$$ where submatrices $X_2,\ldots,X_n$ are just random column permutations of $X_1$. However, to make the codes efficient in decoding, there is one restriction which requires that any two row vectors in $H$ mustn't have 2 or more overlapping elements. By overlapping, I mean for two different row vectors of $H$, say $V_a$ and $V_b$, there exists an index $i$ s.t. $V_a[i] = V_b[i]$;

I tried to write a program to do that, but so far my effort is not good.

The question is: Is there any known algorithmic way to adjust the permutated submatrices $X_1,\ldots,X_n$ so that the overlapping constraint is satisfied?

• Using Latex will be better. Commented Jun 23, 2011 at 3:04
• I'm fairly sure that you forgot to include the condition that the two or more overlapping elements should be non-zero (i.e. equal to 1, if you're in binary case). That is equivalent to eliminating 4-cycles from the Tanner graph. Commented Jun 23, 2011 at 12:00
• @percusse: The OP hasn't been heard from since June 24th. Wonder whether he is still interested? Commented Aug 24, 2011 at 20:35
• @Jyrki: I have just put the Latex code in place, because it showed up on the frontpage. Took my 2 minutes but I certainly had no intention to revive this. :)
– user13838
Commented Aug 24, 2011 at 20:44

There are several approaches to constructing good LDPC parity check matrices based on, for example blocks, that are various powers of a matrix of the form $$\left(\begin{array}{ccccc} 0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&0\\ 0&0&0&\cdots&1\\ 1&0&0&\cdots&0\end{array}\right),$$ where the ones are one position to the right from the diagonal and then at the bottom left.