Obtaining parity check matrix for $C$

Question

I have a question about generator and parity matrices. Let's say I have a code $C$ with generator matrix $G$. I want to find $H$, its parity check matrix. I want the parity check matrix of $C$, not of a code equivalent to $C$. To get $G$ in standard form I can perform several operations. I know that those that affect the rows of the matrix won't change the code that the matrix generates, but if I multiply a column by a non-zero scalar, or if I do a permutation of columns, the code my matrix generates will change (although it will be equivalent to $C$, but this is not what I want).

Let's say I perform the required operations and I get my matrix $H$. How can I obtain a parity check matrix for $C$? I know that I must undo the permutations, but what about the multiplication of columns by scalars? How do I reverse that operation?

Answer 1

There is no need to multiply the columns by scalars in order to compute the parity check matrix. You can always bring the generator matrix $G$ to a reduced row echelon form (Wikipedia) by performing row operations only. Then you are left with column permutations only to bring the matrix in systematic form.

If you still want to do column scaling, then do it as follows. To this end, assume that $G$ is a $k\times n$ matrix. You can express the row operations by an invertible matrix $R$ of size $k\times k$, the column permutations by a permutation matrix $P$ and the column scaling by a diagonal matrix $D$ (both have size $n\times n)$. Then, the resulting matrix after all operations is $$ RGPD = G'. $$ Notice that if one writes the matrix this way, the column scaling applies on the permuted columns. If you then compute the parity check matrix $H'$ of the code $G'$, it fulfills $$ RGPD H'^\mathrm{T} = G'H'^\mathrm{T} = 0 $$ Hence, $H^T = PD H'^\mathrm{T}$ is a parity check matrix of $G$ or, equivalently, $H = H'DP^\mathrm{T}$.