0
$\begingroup$

I have no idea how to get matrix $G$ out of $ H $:

$ HG^T = 0. $

I apologize for such an elementary question, but I have completely forgotten how to solve such problems. Does anybody know anything for a quick revision on solving matrix equations? Thank you in advance.

  • 0
    @JyrkiLahtonen Indeed, its a Hamming code problem. I want to obtain generator matrix from a parity-check matrix.2012-08-30

3 Answers 3

2

The notation suggests (and the OP's comment confirms) that here $H$ is meant to be a parity check matrix of a (presumably binary) linear code, and $G$ a corresponding generator matrix. A quick summary: we are to describe a $k$ dimensional subspace $\mathcal C$ of the $n$-dimensional space $\mathbb{F}_2^n$. A generator matrix $G$ does the job by being a $k\times n$ matrix whose rows form a basis of $\mathcal C$. A parity check matrix does it by giving the matrix $H$ of a linear mapping $\mathbb{F}_2^n\rightarrow \mathbb{F}_2^{n-k}$ carefully designed so that the subspace $\mathcal C$ is the kernel of that mapping. Then, indeed, it follows that $HG^T=0$.

We can perform elementary row operations on either $H$ or $G$ without affecting the subspace $\mathcal C$, so often some kind of a standard form is used. The most common convention (known as systematic encoding) specifies that $G$ be given in the form $ G=(I_k\ \vert\ A), $ where $I_k$ is a $k\times k$ identity matrix and $A$ is a $k\times(n-k)$ matrix. (Because we usually are allowed to permute columns, we can always bring a full rank matrix into this form) Then the matrix $ H=(A^T\ \vert\ I_{n-k}) $ is a matching check matrix (see also the Wikipedia page I linked to). The process is reversible in that the two matrices $H$ and $G$ can switch roles.

So if your matrix $H$ happens to have an identity block at either left or right end, then you can use this recipe. Otherwise you will need to first perform some row operations.

  • 1
    +1 As a minor addendum, in the general case (not in this one where the OP is using a Hamming code), it may be necessary to do some column interchanges as well in order to get an arbitrary $H$ into the form $[A^T\mid I_{n-k}]$. This creates a reversible permutation of the codeword symbols.2012-08-30
0

Just notice how do you multiply matrices:

if $C=AB$, then the $(i,j)$th-entry in $C$ is the inner product of the $i$th row of $A$ and $j$th column of $B$.

If the product satisfies $AB=0$ then you have plenty of orthogonality relations to work with and get the entries of $C$ (modulo scaling of course).

0

Unless you have a constraint on $G$, this equation will not have a unique solution. One possible approach: Assuming $G$ is a $n \times n$ matrix, write $G$ in terms of row vectors. Then $G^T$ consists of $n$ column vectors $g_1, \ldots, g_n$ that satisfy the equation system $H g_1 = 0, \ldots, H g_n = 0$, or equivalently, $g_1, \ldots, g_n \in \ker H$. $G$ is then given by any such set of vectors.